„QuickSort“ algoritmas

Turinys

Kaip veikia „QuickSort“?
Greito rūšiavimo algoritmas
„Python“, „Java“ ir „C / C ++“ pavyzdžiai
„Quicksort“ sudėtingumas
„Quicksort“ programos

Šioje pamokoje sužinosite, kaip veikia „quicksort“. Taip pat rasite veikiančius „C“, „C ++ Python“ ir „Java“ greito pasirinkimo pavyzdžius.

„Quicksort“ yra padalijimo ir užkariavimo metodu pagrįstas algoritmas, kai masyvas padalijamas į poskyrius, o šie poslinkiai rekursyviai kviečiami rūšiuoti elementus.

Kaip veikia „QuickSort“?

Iš masyvo pasirenkamas sukamasis elementas. Kaip pasukamą elementą galite pasirinkti bet kurį masyvo elementą.
Čia mes pasirinkome dešinįjį (ty paskutinįjį) masyvo elementą kaip sukimo elementą. Pasirinkite pasukamą elementą
Mažesni nei šarnyrinis elementai elementai dedami kairėje, o didesni už šarnyrinį elementą - dešinėje. Visus mažesnius elementus padėkite kairiuoju, o didesnį - pasukamuoju elementu dešinėje.
Aukščiau išdėstyta tvarka pasiekiama atlikus šiuos veiksmus.
1. Ties pasukamuoju elementu fiksuojamas rodyklė. Sujungiamasis elementas lyginamas su elementais, prasidedančiais nuo pirmojo indekso. Jei pasiekiamas didesnis nei sukamasis elementas, šiam elementui nustatomas antrasis rodyklė.
2. Dabar sukamasis elementas lyginamas su kitais elementais (trečiasis rodyklė). Jei pasiekiamas mažesnis nei sukamasis elementas elementas, mažesnis elementas pakeičiamas didesniuoju elementu, rastu anksčiau. Sujungimo elemento palyginimas su kitais elementais
3. Procesas vyksta tol, kol pasiekiamas antrasis paskutinis elementas.
  Galiausiai sukamasis elementas pakeičiamas antruoju rodikliu. Pakeiskite sukimo elementą su antruoju rodikliu
4. Dabar šio sukimo elemento kairysis ir dešinysis poskyriai imami toliau apdoroti atliekant toliau nurodytus veiksmus.
Kairieji ir dešinieji daliniai elementai vėl pasirenkami atskirai. Šiose dalyse šarnyriniai elementai yra tinkamoje padėtyje. Tada pakartojamas 2 žingsnis. Kiekvienoje pusėje pasirinkite posūkio elementą ir įdėkite į reikiamą vietą naudodami rekursiją
Dalys vėl yra padalijamos į mažesnes dalis, kol kiekviena dalis susideda iš vieno elemento.
Šiuo metu masyvas jau yra rūšiuojamas.

„Quicksort“ dalims rūšiuoti naudoja rekursiją.

Remiantis dalijimosi ir užkariavimo požiūriu, „quicksort“ algoritmą galima paaiškinti taip:

Dalyti
Masyvas yra padalintas į poskyrius, kurių pasiskirstymo taškas yra „Pivot“. Mažesni už šarnyrą elementai dedami į kairę nuo šarnyro, o didesni už šarnyrą - į dešinę.
Užkariauti
Kairysis ir dešinysis pogrupiai vėl padalijami naudojant pasirinkdami jiems suvestinius elementus. Tai galima pasiekti rekursyviai perkeliant pogrupius į algoritmą.
Sujungti
Šis žingsnis neturi svarbaus vaidmens pasirinkus greitąjį sportą. Masyvas jau surūšiuotas užkariavimo žingsnio pabaigoje.

Naudodamiesi toliau pateiktomis iliustracijomis, galite suprasti „quicksort“ veikimą.

Elementų, esančių kairiajame šarnyro kairiajame

kampe, naudojimas naudojant rekursiją

Greito rūšiavimo algoritmas

 quickSort (masyvas, leftmostIndex, rightmostIndex) if (leftmostIndex <rightmostIndex) pivotIndex <- skaidinys (masyvas, leftmostIndex, rightmostIndex) quickSort (masyvas, leftmostIndex, pivotIndex) quickSort (masyvas, pivotIndex ) nustatykite „rightmostIndex“ kaip „pivotIndex“ parduotuvę „Index“ <- kairiausia „Index“ - 1 i 1

„Python“, „Java“ ir „C / C ++“ pavyzdžiai

„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“ sudėtingumas

Laiko kompleksiškumas

Blogiausio atvejo sudėtingumas („Big-O“) : jis įvyksta tada, kai pasirinktas šarnyrinis elementas yra didžiausias arba mažiausias. Ši sąlyga lemia atvejį, kai sukamasis elementas yra surūšiuoto masyvo kraštutiniame gale. Vienas poskyris visada yra tuščias, o kitame poskyryje yra elementų. Taigi „quicksort“ iškviečiamas tik šiame poskyryje. Tačiau greito rūšiavimo algoritmas veikia geriau išsibarsčiusius pasukimus.O(n²)
n - 1
Geriausio atvejo sudėtingumas („Big-omega“) : O(n*log n)
jis įvyksta, kai pasisukimo elementas visada yra vidurinis elementas arba arti jo.
Vidutinis atvejų sudėtingumas (didelis-teta) : O(n*log n)
jis įvyksta, kai neįvyksta pirmiau nurodytos sąlygos.