|
paź 28
|
Sortowanie jest jednym z poważnych problemów programowania w każdym języku. Obecnie średnio najwydajniejszym algorytmem sortującym jest Quicksort.
Na początek zajmiemy się jednak stworzeniem własnego algorytmu. Zasada jego działania jest prosta. Program bierze każdy element tabeli po kolei i porównuje go z każdym innym elementem w tabeli. Jeśli napotka jakikolwiek większy element niż znajdujący się na końcu tablicy, zamienia go z tym ostatnim.
-
#include <iostream>
-
-
using namespace std;
-
-
int main() {
-
// deklaracja i wypełnienie tablicy
-
int a[] = {9, 412, 22, 623, 666, 425, 248589789, 124, 4572, 148589789}; // 10 elementów
-
-
//sortowanie
-
//zaczynamy poszukiwanie największej liczby od końca tablicy, dla każdego elementu wykonujemy czynność napisaną dalej
-
//q reprezentuje indeks elementu tablicy
-
for (int q=9; q>0; q–) {
-
// q jest zmniejszane, ponieważ pomijamy w sprawdzaniu liczby które zostały określone jako największe wcześniej, q reprezentuje miejsce gdzie umieścimy największą wartość tego przebiegu
-
// zmienna "najwieksza" przechowuje indeks elementu w tablicy z największą dotychczas znalezioną wartością
-
// zakładamy od początku że jest to 0, by zacząć porównywanie od początku, to właśnie wartość znajdująca się w tym elemencie jest porównywana z każdym następnym
-
int najwieksza=0;
-
-
for(int d=0; d<=q; d++) {
-
// metoda "każda z każdą", dla danego elementu bierzemy każdy inny element tablicy, aż do q, bo w miejsce q ustawimy największą znalezioną wartość
-
if (a[d]>a[najwieksza]) najwieksza=d;
-
// jeśli dany element jest większą od obecnego zapisanego jako największy, poprawiamy indeks największej wartości
-
}
-
// bo wewnętrznym forze, podmieniamy największą znalezioną wartość z ostatnim elementem danego przebiegu (q)
-
int s = a[q];
-
a[q]=a[najwieksza];
-
a[najwieksza] = s;
-
}
-
-
//sprawdzenie
-
// wyrzucamy na wyjście uporządkowane już elementy tablicy
-
for(int n=0; i<10; i++) cout<<a[n]<<endl;
-
-
}
A teraz najszybszy algorytm Quicksort:
Jako argumenty przyjmuje on tablicę, indeks pierwszego elementu oraz indeks ostatniego elementu:
-
void quickSort(int arr[], int left, int right) {
-
int i = left, j = right;
-
int tmp;
-
int pivot = arr[(left + right) / 2];
-
-
/* partition */
-
while (i <= j) {
-
while (arr[i] < pivot) i++;
-
while (arr[j] > pivot) j–;
-
if (i <= j) {
-
tmp = arr[i];
-
arr[i] = arr[j];
-
arr[j] = tmp;
-
i++;
-
j–;
-
}
-
};
-
-
/* recursion */
-
if (left < j) quickSort(arr, left, j);
-
if (i < right) quickSort(arr, i, right);
-
}
Szczegółowy opis algorytmu Quicksort można znaleźć tutaj.