QuickSort algoritmus

Ebben az oktatóanyagban megtudhatja, hogyan működik a quicksort. A C, C ++ Pythonban és a Java-ban működő quicksort működő példáit is megtalálja.

A Quicksort egy megosztási és meghódítási megközelítésen alapuló algoritmus, amelyben a tömböt részsávokra osztják, és ezeket az altömböket rekurzívan hívják az elemek rendezésére.

Hogyan működik a QuickSort?

A tömbből egy pivot elemet választanak. A tömbből bármelyik elemet kiválaszthatja pivot elemként.
Itt a tömb jobb szélsőjét (azaz az utolsó elemét) vettük el forgó elemként. Válasszon ki egy pivot elemet
A csuklós elemnél kisebb elemeket balra, a csuklós elemnél nagyobbakat pedig jobbra tesszük. Helyezze az összes kisebb elemet balra, nagyobbat az elfordító elem jobb oldalára.
A fenti elrendezést a következő lépésekkel érjük el.
1. Mutató van rögzítve az elforduló elemnél. A pivot elemet összehasonlítjuk az első indextől kezdődő elemekkel. Ha eléri a forgó elemnél nagyobb elemet, akkor egy második mutatót állítunk be az elemhez.
2. A pivot elemet összehasonlítjuk a többi elemmel (egy harmadik mutatóval). Ha a forgó elemnél kisebb elemet ér el, akkor a kisebb elemet felcseréli a korábban talált nagyobb elemre. A pivot elem összehasonlítása más elemekkel
3. A folyamat addig tart, amíg a második utolsó elemet el nem érik.
  Végül az elforduló elemet felcseréljük a második mutatóval. Cserélje meg az elforduló elemet a második mutatóval
4. Most ennek a pivot elemnek a bal és a jobb alrészét tovább feldolgozzuk az alábbi lépésekben.
A forgatóelemeket ismét külön-külön választjuk a bal és a jobb részhez. Ezen részeken belül a forgóelemek a megfelelő helyzetükbe kerülnek. Ezután a 2. lépést megismételjük. Válassza ki a (z) elem mindkét oldalát, és tegye a megfelelő helyre rekurzióval
Az alrészeket ismét kisebb részekre osztják, amíg mindegyik rész egyetlen elemből nem áll össze.
Ezen a ponton a tömb már rendezve van.

A Quicksort rekurziót használ az alrészek rendezéséhez.

A Divide and Conquer megközelítés alapján a quicksort algoritmus a következőképpen magyarázható:

Divide
A tömb olyan részekre van osztva, amelyeknél a pivot a particionálási pont. A csuklónál kisebb elemeket a csuklótól balra, a csuklónál nagyobb elemeket pedig jobbra.
Hódítás
A bal és a jobb alrész ismét fel van osztva a pivot elemek kiválasztásával. Ezt úgy érhetjük el, hogy rekurzív módon továbbítjuk az alrészeket az algoritmusba.
Kombinálás
Ez a lépés nem játszik jelentős szerepet a quicksortban. A tömb már a hódítási lépés végén rendezve van.

Az alábbi ábrák segítségével megértheti a quicksort működését.

A pivot bal oldalán lévő

elemek rendezése rekurzióval A pivot jobb oldalán lévő elemek rendezése rekurzióval

Gyors rendezési algoritmus

 quickSort (tömb, leftmostIndex, rightmostIndex) if (leftmostIndex <rightmostIndex) pivotIndex <- partíció (tömb, leftmostIndex, rightmostIndex) quickSort (tömb, leftmostIndex, pivotIndex) quickSort (tömb, pivotIndex, bal jobb ) állítsa a rightmostIndex-et pivotIndex-be storeIndex <- leftmostIndex - 1 az i-hez 1

Példák Python, Java és C / C ++

Python Java C C +

 # Quick sort in Python # Function to partition the array on the basis of pivot element def partition(array, low, high): # Select the pivot element pivot = array(high) i = low - 1 # Put the elements smaller than pivot on the left and greater #than pivot on the right of pivot for j in range(low, high): if array(j) <= pivot: i = i + 1 (array(i), array(j)) = (array(j), array(i)) (array(i + 1), array(high)) = (array(high), array(i + 1)) return i + 1 def quickSort(array, low, high): if low < high: # Select pivot position and put all the elements smaller # than pivot on left and greater than pivot on right pi = partition(array, low, high) # Sort the elements on the left of pivot quickSort(array, low, pi - 1) # Sort the elements on the right of pivot quickSort(array, pi + 1, high) data = (8, 7, 2, 1, 0, 9, 6) size = len(data) quickSort(data, 0, size - 1) print('Sorted Array in Ascending Order:') print(data)

 // Quick sort in Java import java.util.Arrays; class QuickSort ( // Function to partition the array on the basis of pivot element int partition(int array(), int low, int high) ( // Select the pivot element int pivot = array(high); int i = (low - 1); // Put the elements smaller than pivot on the left and // greater than pivot on the right of pivot for (int j = low; j < high; j++) ( if (array(j) <= pivot) ( i++; int temp = array(i); array(i) = array(j); array(j) = temp; ) ) int temp = array(i + 1); array(i + 1) = array(high); array(high) = temp; return (i + 1); ) void quickSort(int array(), int low, int high) ( if (low < high) ( // Select pivot position and put all the elements smaller // than pivot on left and greater than pivot on right int pi = partition(array, low, high); // Sort the elements on the left of pivot quickSort(array, low, pi - 1); // Sort the elements on the right of pivot quickSort(array, pi + 1, high); ) ) // Driver code public static void main(String args()) ( int() data = ( 8, 7, 2, 1, 0, 9, 6 ); int size = data.length; QuickSort qs = new QuickSort(); qs.quickSort(data, 0, size - 1); System.out.println("Sorted Array in Ascending Order: "); System.out.println(Arrays.toString(data)); ) )

 // Quick sort in C #include // Function to swap position of elements void swap(int *a, int *b) ( int t = *a; *a = *b; *b = t; ) // Function to partition the array on the basis of pivot element int partition(int array(), int low, int high) ( // Select the pivot element int pivot = array(high); int i = (low - 1); // Put the elements smaller than pivot on the left // and greater than pivot on the right of pivot for (int j = low; j < high; j++) ( if (array(j) <= pivot) ( i++; swap(&array(i), &array(j)); ) ) swap(&array(i + 1), &array(high)); return (i + 1); ) void quickSort(int array(), int low, int high) ( if (low < high) ( // Select pivot position and put all the elements smaller // than pivot on left and greater than pivot on right int pi = partition(array, low, high); // Sort the elements on the left of pivot quickSort(array, low, pi - 1); // Sort the elements on the right of pivot quickSort(array, pi + 1, high); ) ) // Function to print eklements of an array void printArray(int array(), int size) ( for (int i = 0; i < size; ++i) ( printf("%d ", array(i)); ) printf(""); ) // Driver code int main() ( int data() = (8, 7, 2, 1, 0, 9, 6); int n = sizeof(data) / sizeof(data(0)); quickSort(data, 0, n - 1); printf("Sorted array in ascending order: "); printArray(data, n); )

 // Quick sort in C++ #include using namespace std; // Function to swap position of elements void swap(int *a, int *b) ( int t = *a; *a = *b; *b = t; ) // Function to print eklements of an array void printArray(int array(), int size) ( int i; for (i = 0; i < size; i++) cout << array(i) << " "; cout << endl; ) // Function to partition the array on the basis of pivot element int partition(int array(), int low, int high) ( // Select the pivot element int pivot = array(high); int i = (low - 1); // Put the elements smaller than pivot on the left // and greater than pivot on the right of pivot for (int j = low; j < high; j++) ( if (array(j) <= pivot) ( i++; swap(&array(i), &array(j)); ) ) printArray(array, 7); cout << "… "; swap(&array(i + 1), &array(high)); return (i + 1); ) void quickSort(int array(), int low, int high) ( if (low < high) ( // Select pivot position and put all the elements smaller // than pivot on left and greater than pivot on right int pi = partition(array, low, high); // Sort the elements on the left of pivot quickSort(array, low, pi - 1); // Sort the elements on the right of pivot quickSort(array, pi + 1, high); ) ) // Driver code int main() ( int data() = (8, 7, 6, 1, 0, 9, 2); int n = sizeof(data) / sizeof(data(0)); quickSort(data, 0, n - 1); cout << "Sorted array in ascending order: "; printArray(data, n); )

Quicksort komplexitás

Időkomplexumok

Legrosszabb eset komplexitás (Big-O) : Akkor fordul elő, ha a kiválasztott forgatóelem a legnagyobb vagy a legkisebb elem. Ez a feltétel ahhoz az esethez vezet, amikor a forgó elem a rendezett tömb szélső végén fekszik. Az egyik tömb mindig üres, egy másik pedig egy elemet tartalmaz . Így a quicksort csak ezen az altömbön hívható meg. A gyors rendezési algoritmus azonban jobb teljesítményt nyújt a szétszórt pivotok esetében.O(n²)
n - 1
Legjobb eset komplexitás (Big-omega) : O(n*log n)
Akkor fordul elő, amikor a forgó elem mindig a középső elem vagy a középső elem közelében van.
Átlagos eset komplexitás (nagy-theta) : O(n*log n)
Akkor fordul elő, ha a fenti feltételek nem fordulnak elő.