Epätodennäköistä Yhdistä lajittelu , QuickSort on a hajota ja hallitse -algoritmi . Se valitsee elementin pivotiksi ja jakaa annetun taulukon valitun pivotin ympärille.

QuickSortista on monia eri versioita, jotka valitsevat nivelen eri tavoilla.

1. Valitse aina ensimmäinen elementti pivoiksi
2. Valitse aina viimeinen elementti pivoiksi
3. Valitse satunnainen elementti pivotiksi
4. Valitse kääntöpisteeksi mediaani

Tässä valitaan viimeinen elementti pivotiksi. QuickSortin avainprosessi on partition(). Osion kohde on, kun taulukon ja taulukon elementin 'x' pivotiksi annetaan, x asetetaan oikeaan paikkaansa lajiteltuun taulukkoon ja laitetaan kaikki pienemmät elementit (pienemmät kuin x) ennen x:ää ja laitetaan kaikki suuremmat elementit (suuremmat). kuin x) x:n jälkeen. Kaikki tämä tulisi tehdä lineaarisessa ajassa.

jos muuten jos muuten java

Python Rekursiivinen QuickSort toiminto

// low -->Aloitusindeksi, // korkea --> Loppuindeksi quickSort(arr[], matala, korkea) { // Alkuindeksi on pienempi kuin loppuindeksi if (low // pi on osiointiindeksi, // arr[p] on nyt oikeassa paikassa pi = osio(arr, low, high // Ennen pi:tä quickSort(arr, low, pi - 1) // Pi QuickSort(arr, pi + 1, high) jälkeen; 
Python 3
    
 
     
  
 
    
 
     
     
    
 
 
 
 
 
 # Python program for implementation of Quicksort Sort> # This implementation utilizes pivot as the last element in the nums list> # It has a pointer to keep track of the elements smaller than the pivot> # At the very end of partition() function, the pointer is swapped with the pivot> # to come up with a 'sorted' nums relative to the pivot> # 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   # 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) data = [1, 7, 4, 1, 10, 9, -2] print('Unsorted Array') print(data) size = len(data) quickSort(data, 0, size - 1) print('Sorted Array in Ascending Order:') print(data)>
 
 
 
 
    
   
 
>
 
  Lähtö  
java lukee csv
 
Unsorted Array [1, 7, 4, 1, 10, 9, -2] Sorted Array in Ascending Order: [-2, 1, 1, 4, 7, 9, 10]>
 
    Aika monimutkaisuus:    Pahimmassa tapauksessa aika monimutkaisuus on O(N2) ja keskimääräinen tapauksen ajan monimutkaisuus on O(N log N)  
    Aputila:    O(1)
 
    Python Quicksort käyttämällä         listan ymmärtäminen      
 
Pikalajittelu luettelon ymmärtämisen avulla on rekursiivinen algoritmi elementtijoukon lajitteluun. Se toimii valitsemalla pivot-elementin ja osioiden taulukon pivotin ympärille siten, että kaikki pivotia pienemmät elementit siirretään sen vasemmalle ja kaikki pivotia suuremmat elementit siirretään sen oikealle. Sitten se soveltaa rekursiivisesti samaa prosessia vasempaan ja oikeaan alitaulukkoon, kunnes koko taulukko on lajiteltu.
 
    Algoritmi:    
 
1.Jos syötetaulukon pituus on 0 tai 1, palauta matriisi sellaisena kuin se on jo lajiteltuna.  
2.Valitse taulukon ensimmäinen elementti pivot-elementiksi.  
3.Luo kaksi tyhjää listaa, vasen ja oikea.  
4. Jokaista taulukon elementtiä lukuun ottamatta pivotia:  
a. Jos elementti on pienempi kuin pivot, lisää se vasemmanpuoleiseen luetteloon.  
b. Jos elementti on suurempi tai yhtä suuri kuin pivot, lisää se oikeaan luetteloon.  
5. Kutsu pikalajittelua rekursiivisesti vasemmalla ja oikealla olevasta luettelosta.  
6. Liitä lajiteltu vasen luettelo, pivot-elementti ja lajiteltu oikea luettelo.  
7.Palauta ketjutettu luettelo.
 
Python 3
    
 
     
  
 
    
 
     
     
    
 
 
 
 
 
 # Approach 2: Quicksort using list comprehension> def> quicksort(arr):> >if> len>(arr) <>=> 1>:> >return> arr> >else>:> >pivot>=> arr[>0>]> >left>=> [x>for> x>in> arr[>1>:]>if> x   right = [x for x in arr[1:] if x>= pivot] paluu pikalajittelu(vasen) + [pivot] + pikalajittelu(oikea) # Käyttöesimerkki arr = [1, 7, 4, 1, 10, 9, -2] sorted_arr = quicksort(arr) print('Sorted Array nousevassa järjestyksessä:') print(sorted_arr)>
 
 
 
 
    
 
>
 
    
 
>
 
  Lähtö  
teollisuus ja tehdas
 
Sorted Array in Ascending Order: [-2, 1, 1, 4, 7, 9, 10]>
 
Aika monimutkaisuus on O(n log n)
 
Algoritmin tilamonimutkaisuus on O(n)