Greitas rūšiavimas yra rūšiavimo algoritmas, pagrįstas Skaldyk ir valdyk algoritmas kuris pasirenka elementą kaip sukimosi tašką ir suskirsto nurodytą masyvą aplink pasirinktą sukimąsi, padėdamas sukimąsi į teisingą padėtį surūšiuotame masyve.
Kaip veikia „QuickSort“?
Rekomenduojama praktika Greitas rūšiavimas Išbandykite!Pagrindinis procesas greitas rūšiavimas yra skaidinys () . Skirsnių tikslas yra išdėstyti sukimosi tašką (bet kurį elementą galima pasirinkti kaip sukimąsi) į teisingą padėtį surūšiuotame masyve ir visus mažesnius elementus sudėti į kairę nuo sukimosi, o visus didesnius elementus į dešinę nuo sukimosi. .
Perskirstymas atliekamas rekursyviai kiekvienoje sukimosi pusėje po to, kai sukimasis yra įdėtas į teisingą padėtį, ir tai galiausiai surūšiuoja masyvą.
Kaip veikia Quicksort
skaitymas iš csv failo java
„Pivot“ pasirinkimas:
Yra daug skirtingų šarnyrų pasirinkimo galimybių.
- Visada pasirinkite pirmąjį elementą kaip sukimąsi .
- Visada pasirinkite paskutinį elementą kaip sukimąsi (įgyvendinta toliau)
- Pasirinkite atsitiktinį elementą kaip sukimąsi .
- Pasirinkite vidurį kaip ašį.
Padalijimo algoritmas:
Logika paprasta, pradedame nuo kairiojo elemento ir stebime mažesnių (arba lygių) elementų indeksą kaip i . Keliaudami, jei randame mažesnį elementą, esamą elementą keičiame su arr[i]. Kitu atveju ignoruojame dabartinį elementą.
Supraskime skaidinio veikimą ir greitojo rūšiavimo algoritmą naudodami šį pavyzdį:
Apsvarstykite: arr[] = {10, 80, 30, 90, 40}.
- Palyginkite 10 su ašimi ir, kadangi jis yra mažesnis už šarnyrą, sutvarkykite jį atitinkamai.
„QuickSort“ skaidinys: palyginkite sukimąsi su 10
- Palyginkite 80 su ašimi. Jis yra didesnis nei sukimasis.
„QuickSort“ skaidinys: palyginkite sukimąsi su 80
Java pavyzdys
- Palyginkite 30 su ašimi. Jis yra mažesnis nei pasukamas, todėl sutvarkykite jį atitinkamai.
„QuickSort“ skaidinys: palyginkite sukimąsi su 30
- Palyginkite 90 su ašimi. Jis yra didesnis nei ašis.
„QuickSort“ skaidinys: palyginkite sukimąsi su 90
- Sustatykite ašį tinkamoje padėtyje.
Skyrius „QuickSort“: padėkite sukimąsi į tinkamą padėtį
Quicksort iliustracija:
Kadangi skaidymo procesas vykdomas rekursyviai, sukimasis ir toliau nustatomas į tikrąją rūšiuojamo masyvo padėtį. Pakartotinai įvedus sukinius į faktinę padėtį, masyvas surūšiuojamas.
Sekite toliau pateiktus vaizdus, kad suprastumėte, kaip rekursinis skaidinio algoritmo įgyvendinimas padeda rūšiuoti masyvą.
a b c skaičiai
- Pradinis skaidinys pagrindiniame masyve:
Greitasis rūšiavimas: skaidinys
- Pogrupių padalijimas:
Greitasis rūšiavimas: atlieka skaidinį
Greitojo rūšiavimo kodo įdiegimas:
C++ #include using namespace std; int partition(int arr[],int low,int high) { //choose the pivot int pivot=arr[high]; //Index of smaller element and Indicate //the right position of pivot found so far int i=(low-1); for(int j=low;j<=high-1;j++) { //If current element is smaller than the pivot if(arr[j]
C // C program for QuickSort #include // Utility function to swap tp integers void swap(int* p1, int* p2) { int temp; temp = *p1; *p1 = *p2; *p2 = temp; } int partition(int arr[], int low, int high) { // choose the pivot int pivot = arr[high]; // Index of smaller element and Indicate // the right position of pivot found so far int i = (low - 1); for (int j = low; j <= high - 1; j++) { // If current element is smaller than the pivot if (arr[j] < pivot) { // Increment index of smaller element i++; swap(&arr[i], &arr[j]); } } swap(&arr[i + 1], &arr[high]); return (i + 1); } // The Quicksort function Implement void quickSort(int arr[], int low, int high) { // when low is less than high if (low < high) { // pi is the partition return index of pivot int pi = partition(arr, low, high); // Recursion Call // smaller element than pivot goes left and // higher element goes right quickSort(arr, low, pi - 1); quickSort(arr, pi + 1, high); } } int main() { int arr[] = { 10, 7, 8, 9, 1, 5 }; int n = sizeof(arr) / sizeof(arr[0]); // Function call quickSort(arr, 0, n - 1); // Print the sorted array printf('Sorted Array
'); for (int i = 0; i < n; i++) { printf('%d ', arr[i]); } return 0; } // This Code is Contributed By Diwakar Jha>
Java // Java implementation of QuickSort import java.io.*; class GFG { // A utility function to swap two elements static void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } // This function takes last element as pivot, // places the pivot element at its correct position // in sorted array, and places all smaller to left // of pivot and all greater elements to right of pivot static int partition(int[] arr, int low, int high) { // Choosing the pivot int pivot = arr[high]; // Index of smaller element and indicates // the right position of pivot found so far int i = (low - 1); for (int j = low; j <= high - 1; j++) { // If current element is smaller than the pivot if (arr[j] < pivot) { // Increment index of smaller element i++; swap(arr, i, j); } } swap(arr, i + 1, high); return (i + 1); } // The main function that implements QuickSort // arr[] -->Rūšiuotinas masyvas, // žemas --> Pradinis indeksas, // aukštas --> Pabaigos indeksas static void quickSort(int[] arr, int žemas, int aukštas) { if (žemas< high) { // pi is partitioning index, arr[p] // is now at right place int pi = partition(arr, low, high); // Separately sort elements before // partition and after partition quickSort(arr, low, pi - 1); quickSort(arr, pi + 1, high); } } // To print sorted array public static void printArr(int[] arr) { for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + ' '); } } // Driver Code public static void main(String[] args) { int[] arr = { 10, 7, 8, 9, 1, 5 }; int N = arr.length; // Function call quickSort(arr, 0, N - 1); System.out.println('Sorted array:'); printArr(arr); } } // This code is contributed by Ayush Choudhary // Improved by Ajay Virmoti>
Python # Python3 implementation of QuickSort # Function to find the partition position def partition(array, low, high): # Choose the rightmost element as pivot pivot = array[high] # Pointer for greater element i = low - 1 # Traverse through all elements # compare each element with pivot for j in range(low, high): if array[j] <= pivot: # If element smaller than pivot is found # swap it with the greater element pointed by i i = i + 1 # Swapping element at i with element at j (array[i], array[j]) = (array[j], array[i]) # Swap the pivot element with # the greater element specified by i (array[i + 1], array[high]) = (array[high], array[i + 1]) # Return the position from where partition is done return i + 1 # Function to perform quicksort def quicksort(array, low, high): if low < high: # Find pivot element such that # element smaller than pivot are on the left # element greater than pivot are on the right pi = partition(array, low, high) # Recursive call on the left of pivot quicksort(array, low, pi - 1) # Recursive call on the right of pivot quicksort(array, pi + 1, high) # Driver code if __name__ == '__main__': array = [10, 7, 8, 9, 1, 5] N = len(array) # Function call quicksort(array, 0, N - 1) print('Sorted array:') for x in array: print(x, end=' ') # This code is contributed by Adnan Aliakbar>
C# // C# implementation of QuickSort using System; class GFG { // A utility function to swap two elements static void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } // This function takes last element as pivot, // places the pivot element at its correct position // in sorted array, and places all smaller to left // of pivot and all greater elements to right of pivot static int partition(int[] arr, int low, int high) { // Choosing the pivot int pivot = arr[high]; // Index of smaller element and indicates // the right position of pivot found so far int i = (low - 1); for (int j = low; j <= high - 1; j++) { // If current element is smaller than the pivot if (arr[j] < pivot) { // Increment index of smaller element i++; swap(arr, i, j); } } swap(arr, i + 1, high); return (i + 1); } // The main function that implements QuickSort // arr[] -->Rūšiuotinas masyvas, // žemas --> Pradinis indeksas, // aukštas --> Pabaigos indeksas static void quickSort(int[] arr, int žemas, int aukštas) { if (žemas< high) { // pi is partitioning index, arr[p] // is now at right place int pi = partition(arr, low, high); // Separately sort elements before // and after partition index quickSort(arr, low, pi - 1); quickSort(arr, pi + 1, high); } } // Driver Code public static void Main() { int[] arr = { 10, 7, 8, 9, 1, 5 }; int N = arr.Length; // Function call quickSort(arr, 0, N - 1); Console.WriteLine('Sorted array:'); for (int i = 0; i < N; i++) Console.Write(arr[i] + ' '); } } // This code is contributed by gfgking>
JavaScript // Function to partition the array and return the partition index function partition(arr, low, high) { // Choosing the pivot let pivot = arr[high]; // Index of smaller element and indicates the right position of pivot found so far let i = low - 1; for (let j = low; j <= high - 1; j++) { // If current element is smaller than the pivot if (arr[j] < pivot) { // Increment index of smaller element i++; [arr[i], arr[j]] = [arr[j], arr[i]]; // Swap elements } } [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]]; // Swap pivot to its correct position return i + 1; // Return the partition index } // The main function that implements QuickSort function quickSort(arr, low, high) { if (low < high) { // pi is the partitioning index, arr[pi] is now at the right place let pi = partition(arr, low, high); // Separately sort elements before partition and after partition quickSort(arr, low, pi - 1); quickSort(arr, pi + 1, high); } } // Driver code let arr = [10, 7, 8, 9, 1, 5]; let N = arr.length; // Function call quickSort(arr, 0, N - 1); console.log('Sorted array:'); console.log(arr.join(' '));>
PHP // code ?>// Ši funkcija atlieka paskutinį elementą kaip pivot // Suveskite kaip teisingą padėtį // Surūšiuotame masyve ir visus mažesnes į kairę // nuo sukimosi ir visus didesnius elementus į dešinę nuo sukimo funkcijos skaidinio (&$arr, $žemas,$aukštas) { // Pasirinkite sukimosi elementą $pivot= $arr[$high]; // Mažesnio elemento indeksas ir nurodo // Teisingą sukimosi padėtį $i=($low-1); for($j=$low;$j<=$high-1;$j++) { if($arr[$j]<$pivot) { // Increment index of smaller element $i++; list($arr[$i],$arr[$j])=array($arr[$j],$arr[$i]); } } // Pivot element as correct position list($arr[$i+1],$arr[$high])=array($arr[$high],$arr[$i+1]); return ($i+1); } // The main function that implement as QuickSort // arr[]:- Array to be sorted // low:- Starting Index //high:- Ending Index function quickSort(&$arr,$low,$high) { if($low<$high) { // pi is partition $pi= partition($arr,$low,$high); // Sort the array // Before the partition of Element quickSort($arr,$low,$pi-1); // After the partition Element quickSort($arr,$pi+1,$high); } } // Driver Code $arr= array(10,7,8,9,1,5); $N=count($arr); // Function Call quickSort($arr,0,$N-1); echo 'Sorted Array:
'; for($i=0;$i<$N;$i++) { echo $arr[$i]. ' '; } //This code is contributed by Diwakar Jha>
Išvestis
Sorted Array 1 5 7 8 9 10>
Greitojo rūšiavimo sudėtingumo analizė :
Laiko sudėtingumas:
- Geriausias atvejis : Ω (N log (N))
Geriausias greitojo rūšiavimo scenarijus įvyksta, kai kiekviename žingsnyje pasirinktas sukimas padalija masyvą į maždaug lygias dalis.
Tokiu atveju algoritmas subalansuos skaidinius, todėl rūšiavimas bus efektyvus. - Vidutinis atvejis: θ ( N log (N))
„Quicksort“ vidutinis našumas praktikoje paprastai yra labai geras, todėl jis yra vienas greičiausių rūšiavimo algoritmų. - Blogiausias atvejis: O (N2)
Blogiausias „Quicksort“ scenarijus įvyksta, kai kiekvieno žingsnio sukimas nuolat lemia labai nesubalansuotus skaidinius. Kai masyvas jau surūšiuotas, o sukimasis visada pasirenkamas kaip mažiausias arba didžiausias elementas. Siekiant sušvelninti blogiausią scenarijų, naudojami įvairūs metodai, pvz., gero sukimosi vietos pasirinkimas (pvz., vidutinis iš trijų) ir atsitiktinis algoritmas (Randomized Quicksort ), kad elementas būtų sumaišytas prieš rūšiavimą. - Pagalbinė erdvė: O(1), jei neatsižvelgsime į rekursyviąją kamino erdvę. Jei atsižvelgsime į rekursyvią dėklo erdvę, blogiausiu atveju būtų galima greitai rūšiuoti O ( N ).
Greito rūšiavimo pranašumai:
- Tai „skaldyk ir valdyk“ algoritmas, kuris palengvina problemų sprendimą.
- Tai veiksminga dideliuose duomenų rinkiniuose.
- Jis turi mažas pridėtines išlaidas, nes norint veikti, reikia tik nedidelio atminties kiekio.
Greito rūšiavimo trūkumai:
- Blogiausio atvejo laiko sudėtingumas yra O(N2), kuris atsiranda, kai sukimasis pasirenkamas blogai.
- Tai nėra geras pasirinkimas mažiems duomenų rinkiniams.
- Tai nėra stabilus rūšiavimas, tai reiškia, kad jei du elementai turi tą patį raktą, greito rūšiavimo atveju jų santykinė tvarka nebus išsaugota surūšiuotoje išvestyje, nes čia mes keičiame elementus pagal sukimosi vietą (neatsižvelgiant į jų pradinę pozicijos).