Gruntle Software & Testing

Python sortiranje: metode sortiranja i algoritmi u Pythonu

Od strane Stewart TristianObjavljeno Objavljeno u Vodiči

Naučite kako koristiti funkciju Python Sort za sortiranje popisa, nizova, rječnika itd. koristeći različite metode sortiranja i algoritme u Pythonu:

Razvrstavanje je tehnika koja se koristi za sortiranje podatke redoslijedom, bilo uzlaznim ili silaznim redoslijedom.

Većinu vremena podaci velikih projekata nisu raspoređeni ispravnim redoslijedom i to stvara probleme prilikom učinkovitog pristupa i dohvaćanja potrebnih podataka.

Za rješavanje ovog problema koriste se tehnike sortiranja. Python nudi različite tehnike sortiranja na primjer, Bubble sortiranje, sortiranje umetanjem, sortiranje spajanjem, brzo sortiranje, itd.

U ovom ćemo vodiču razumjeti kako sortiranje funkcionira u Pythonu korištenjem različitih algoritama.

Python sortiranje

Sintaksa Python sortiranja

Za obavljanje sortiranja, Python nudi ugrađenu funkciju, tj. funkciju “ sort() ”. Koristi se za sortiranje podatkovnih elemenata popisa uzlaznim ili silaznim redoslijedom.

Razumijmo ovaj koncept na primjeru.

Primjer 1: 

``` a = [ 3, 5, 2, 6, 7, 9, 8, 1, 4 ] a.sort() print( “ List in ascending order: ”, a ) ```

Izlaz:

U ovom primjeru, dani neuređeni popis sortiran je uzlaznim redoslijedom pomoću funkcije “ sort( ) ” .

Primjer 2: 

``` a = [ 3, 5, 2, 6, 7, 9, 8, 1, 4 ] a.sort( reverse = True ) print( “ List in descending order: ”, a ) ```

Izlaz

U gornjem primjeru, dani neuređeni popis sortira se obrnutim redoslijedom pomoću funkcije “ sort( reverse = True ) ”.

Vrijememjesto Razvrstavanje mjehurićima O(n) O(n2) O(n2) O(1) Da Da Razvrstavanje umetanjem O(n) O(n2) O(n2) O(1) Da Da Brzo sortiranje O(n log(n)) O(n log(n)) O(n2) O(N) Ne Da Spoji sortiraj O(n log(n)) O(n log(n)) O(n log(n)) O(N) Da Ne Hop sortiranje O(n log (n)) O(n log(n)) O(n log(n)) O(1) Ne Da

U gornjoj usporednoj tablici “ O “ je oznaka Big Oh objašnjena gore, dok “ n ” i “ N ” znače veličinu ulaza .

Često postavljana pitanja

P #1) Što je sort () u Pythonu?

Odgovor: U Pythonu sort() je funkcija koja se koristi za sortiranje popisa ili polja određenim redoslijedom. Ova funkcija olakšava proces sortiranja tijekom rada na velikim projektima. Vrlo je korisno za programere.

P #2) Kako sortirate u Pythonu?

Odgovor: Python nudi različite tehnike sortiranja koje se koriste za sortiranje elementa. Na primjer, Brzo sortiranje, sortiranje spajanjem, sortiranje mjehurićima, sortiranje umetanjem itd. Sve tehnike sortiranja učinkovite su i jednostavne za razumijevanje.

P #3) Kako Python sortirati () posao?

Odgovor: Sortiranje()funkcija uzima dani niz kao unos od korisnika i sortira ga određenim redoslijedom pomoću algoritma sortiranja. Odabir algoritma ovisi o izboru korisnika. Korisnici mogu koristiti brzo sortiranje, sortiranje spajanjem, sortiranje mjehurićima, sortiranje umetanjem itd., ovisno o potrebama korisnika.

Zaključak

U gornjem vodiču raspravljali smo o tehnici sortiranja u Pythonu zajedno s opće tehnike sortiranja.

  • Razvrstavanje u obliku mjehurića
  • Razvrstavanje umetanjem
  • Brzo sortiranje

Naučili smo o njihovoj vremenskoj složenosti i prednostima & nedostatke. Također smo usporedili sve gore navedene tehnike.

Složenost algoritama za sortiranje

Vremenska složenost je vrijeme koje je računalu potrebno da pokrene određeni algoritam. Ima tri vrste slučajeva vremenske složenosti.

  • Najgori slučaj: Maksimalno vrijeme koje je računalu potrebno za pokretanje programa.
  • Prosječni slučaj: Vrijeme između minimuma i maksimuma koje je računalu potrebno za pokretanje programa.
  • Najbolji slučaj: Minimalno vrijeme koje je računalu potrebno za pokretanje programa. To je najbolji slučaj vremenske složenosti.

Oznake složenosti

Big Oh notacija, O: Big oh notacija službeni je način prenošenja gornje granice vremena rada algoritama. Koristi se za mjerenje najgoreg slučaja vremenske složenosti ili mi kažemo najveće količine vremena potrebnog algoritmu da završi.

Big omega notation, : Big omega notation je službeni način prenošenja najniže granice vremena izvođenja algoritama. Koristi se za mjerenje najboljeg slučaja vremenske složenosti ili mi kažemo izvrsne količine vremena potrebnog algoritmu.

Theta notacija, : Theta notacija je službeni način prenošenja obje granice, tj. donja i gornja vrijednost vremena potrebnog algoritmu za završetak.

Metode sortiranja u Pythonu

Sortiranje u mjehurićima

Sortiranje u mjehurićima je najjednostavniji način sortiranja podataka koji koristi tehniku ​​grube sile. Ponavljat će svaki podatkovni element i usporediti ga s drugim elementimakako bismo korisniku pružili razvrstane podatke.

Uzmimo primjer da bismo razumjeli ovu tehniku:

  • Omogućen nam je niz koji ima elemente “ 10, 40, 7, 3, 15”. Sada moramo rasporediti ovaj niz uzlaznim redoslijedom pomoću tehnike Bubble sortiranja u Pythonu.
    • Prvi korak je raspored niza zadanim redoslijedom.
    • U “ Iteraciji 1 ”, uspoređujemo prvi element niza s ostalim elementima jedan po jedan.
    • Crvene strelice opisuju usporedbu prvih elemenata s ostalim elementima niza.
    • Ako primijetite da je “ 10 ” manji od “ 40 ”, dakle, ostaje isti mjesto, ali je sljedeći element “ 7 ” manji od “ 10 ”. Stoga se zamjenjuje i dolazi na prvo mjesto.
    • Gornji postupak izvodit će se uvijek iznova kako bi se razvrstali elementi.

    • U “ Iteraciji 2 ” drugi element se uspoređuje s ostalim elementima niza.
    • Ako je uspoređivani element mali, tada će zamijeniti, inače će ostati na istom mjestu.

    • U “ Iteracija 3 “ treći element se uspoređuje s ostalim elementima niza.

    • U posljednjem “ Iteracija 4 “ pretposljednji element se uspoređuje s ostalim elementima niza.
    • Uu ovom koraku niz se sortira uzlaznim redoslijedom.

Program za Bubble sortiranje 

``` def Bubble_Sort(unsorted_list): for i in range(0,len(unsorted_list)-1): for j in range(len(unsorted_list)-1): if(unsorted_list[j]>unsorted_list[j+1]): temp_storage = unsorted_list[j] unsorted_list[j] = unsorted_list[j+1] unsorted_list[j+1] = temp_storage return unsorted_list unsorted_list = [5, 3, 8, 6, 7, 2] print("Unsorted List: ", unsorted_list) print("Sorted List using Bubble Sort Technique: ", Bubble_Sort(unsorted_list)) ```

Izlaz

Vremenska složenost Bubble sortiranja

  • Najgori slučaj: Najgora vremenska složenost za sortiranje u obliku mjehurića je O( n 2).
  • Prosječan slučaj: Prosječna složenost vremena za sortiranje u obliku mjehurića je O( n 2).
  • Najbolji slučaj: Najbolja vremenska složenost za mjehuričasto sortiranje je O(n).

Prednosti

  • Uglavnom se koristi i jednostavan je za implementaciju.
  • Podatkovne elemente možemo zamijeniti bez potrošnje kratkoročne pohrane.
  • Zahtijeva manje prostora.

Nedostaci

  • Nije se dobro pokazao pri radu s velikim brojem velikih podatkovnih elemenata.
  • To potrebna su n 2 koraka za svaki “n” broj podatkovnih elemenata da se razvrstaju.
  • Nije baš dobro za aplikacije u stvarnom svijetu.

Umetanje Sortiranje

Sortiranje umetanjem laka je i jednostavna tehnika sortiranja koja funkcionira slično kao sortiranje igraćih karata. Sortiranje umetanjem razvrstava elemente uspoređujući svaki element jedan po jedan s drugim. Elementi se biraju i zamjenjuju s drugim elementom ako je element veći ili manji od drugog.

Uzmimo primjer

  • Omogućeno nam je niz koji ima elemente “ 100, 50, 30, 40, 10 ”.
  • Prvo, rasporedimo niz i počnemo uspoređivatiit.
  • U prvom koraku “ 100 ” se uspoređuje s drugim elementom “ 50 ”. “ 50 ” se zamjenjuje sa “ 100 ” jer je veći.
  • U drugom koraku, ponovo se drugi element “ 100 ” uspoređuje s trećim elementom “ 30 ” i biva zamijenjen.
  • Sada, ako primijetite da “ 30 ” dolazi na prvo mjesto jer je opet manji od “ 50 ”.
  • Usporedba će se odvijati do posljednjeg elementa niza i na kraju ćemo dobiti sortirani podaci.

Program za sortiranje umetanjem 

``` def InsertionSort(array): for i in range(1, len(array)): key_value = array[i] j = i-1 while j >= 0 and key_value  array[j] : array[j + 1] = array[j] j -= 1 array[j + 1] = key_value array = [11, 10, 12, 4, 5] print("The unsorted array: ", array) InsertionSort(array) print ("The sorted array using the Insertion Sort: ") for i in range(len(array)): print (array[i]) ```

Izlaz

Vremenska složenost sortiranja umetanjem

  • Najgori slučaj: Najgora vremenska složenost sortiranja umetanjem je O( n 2).
  • Prosječni slučaj: Prosječna vremenska složenost za sortiranje umetanjem je O( n 2).
  • Najbolji slučaj: Najbolja vremenska složenost za sortiranje umetanjem je O(n).

Prednosti

  • Jednostavno je i jednostavan za implementaciju.
  • Dobro radi dok radi s malim brojem podatkovnih elemenata.
  • Ne treba mu više prostora za implementaciju.

Nedostaci

  • Nije od pomoći sortirati veliki broj podatkovnih elemenata.
  • U usporedbi s drugim tehnikama sortiranja, ne radi dobro.

Sortiranje spajanjem

Ova metoda sortiranja koristi metodu podijeli i vladaj za sortiranje elemenata određenim redoslijedom. Prilikom razvrstavanja uz pomoć merge sort, theelementi se dijele na polovice, a zatim se sortiraju. Nakon razvrstavanja svih polovica, elementi se ponovno spajaju kako bi formirali savršen poredak.

Uzmimo primjer da bismo razumjeli ovu tehniku

  • Na raspolaganju nam je niz “ 7, 3, 40, 10, 20, 15, 6, 5 ”. Niz sadrži 7 elemenata. Ako ga podijelimo na pola ( 0 + 7 / 2 = 3 ).
  • U drugom koraku vidjet ćete da su elementi podijeljeni na dva dijela. Svaki ima 4 elementa u sebi.
  • Nadalje, elementi se ponovno dijele i imaju po 2 elementa.
  • Ovaj proces će se nastaviti sve dok samo jedan element ne bude prisutan u nizu. Pogledajte korak br. 4 na slici.
  • Sada ćemo sortirati elemente i početi ih spajati onako kako smo podijeljeni.
  • U koraku br. 5 ako primijetite da je 7 veće od 3, pa ćemo ih razmijeniti i pridružiti u sljedećem koraku i obrnuto.
  • Na kraju ćete primijetiti da se naš niz sortira uzlaznim redoslijedom.

Program za sortiranje spajanjem 

``` def MergeSort(arr): if len(arr) > 1: middle = len(arr)//2 L = arr[:middle] R = arr[middle:] MergeSort(L) MergeSort(R) i = j = k = 0 while i  len(L) and j  len(R): if L[i]  R[j]: arr[k] = L[i] i += 1 else: arr[k] = R[j] j += 1 k += 1 while i  len(L): arr[k] = L[i] i += 1 k += 1 while j  len(R): arr[k] = R[j] j += 1 k += 1 def PrintSortedList(arr): for i in range(len(arr)): print(arr[i],) print() arr = [12, 11, 13, 5, 6, 7] print("Given array is", end="\n") PrintSortedList(arr) MergeSort(arr) print("Sorted array is: ", end="\n") PrintSortedList(arr) ```

Izlaz

Vremenska složenost sortiranja spajanjem

  • Najgori slučaj: Najgora vremenska složenost sortiranja spajanjem je O( n log( n )).
  • Prosječan slučaj: Prosječna vremenska složenost sortiranja spajanjem je O( n log( n )).
  • Najbolji slučaj: Najbolja vremenska složenost za sortiranje spajanjem je O( n log( n )).

Prednosti

  • Veličina datoteke nije bitna za ovu tehniku ​​sortiranja.
  • Ova je tehnika dobra za podatke kojima se općenito pristupa redoslijedom. Na primjer, povezani popisi, pogon trake, itd.

Nedostaci

  • Zahtijeva više prostora u usporedbi s drugim tehnike sortiranja.
  • Razmjerno je manje učinkovit od drugih.

Brzo sortiranje

Brzo sortiranje ponovno koristi metodu podijeli i vladaj za sortiranje elemenata popisa ili niz. Cilja zaokretne elemente i razvrstava elemente prema odabranom zaokretnom elementu.

Na primjer

  • Omogućen nam je niz koji ima elemente “ 1 ,8,3,9,4,5,7 ”.
  • Pretpostavimo da je “ 7 ” pilot element.
  • Sada ćemo podijeliti niz na takav način da lijeva strana sadrži elemente koji su manji od stožernog elementa “ 7 ”, a desna strana sadrži elemente veće od stožernog elementa “ 7 ”.
  • Sada imamo dva niza “ 1,3,4,5 ” i “ 8, 9 ”.
  • Opet, moramo podijeliti oba niza isto kao što smo učinili gore. Jedina razlika je u tome što se zaokretni elementi mijenjaju.
  • Moramo podijeliti nizove dok ne dobijemo jedan element u nizu.
  • Na kraju sakupite sve zaokretne elemente u redoslijed s lijeva na desno i dobit ćete razvrstanoniz.

Program za brzo sortiranje 

``` def Array_Partition( arr, lowest, highest ): i = ( lowest-1 ) pivot_element = arr[ highest ] for j in range( lowest, highest ): if arr[ j ] = pivot_element: i = i+1 arr[ i ], arr[ j ] = arr[ j ], arr[ i ] arr[ i+1 ], arr[ highest ] = arr[ highest ], arr[ i+1 ] return ( i+1 ) def QuickSort( arr, lowest, highest ): if len( arr ) == 1: return arr if lowest  highest: pi = Array_Partition( arr, lowest, highest ) QuickSort( arr, lowest, pi-1 ) QuickSort( arr, pi+1, highest ) arr = [ 9, 6, 7, 8, 0, 4 ] n = len( arr ) print( " Unsorted array: ", arr ) QuickSort( arr, 0, n-1 ) print( " Sorted array using Quick Sort: " ) for i in range( n ): print( " %d " % arr[ i ] ) ```

Izlaz

Vremenska složenost brzog sortiranja

  • Najgori slučaj: Najgora vremenska složenost za brzo sortiranje je O( n 2).
  • Prosječni slučaj: Prosječna vremenska složenost za brzo sortiranje je O( n log( n ) ).
  • Najbolji slučaj: Najbolja vremenska složenost za brzo sortiranje je O( n log( n )).

Prednosti

  • Poznat je kao najbolji algoritam za sortiranje u Pythonu.
  • Koristan je pri rukovanju velikim količinama podataka.
  • Ne zahtijeva dodatni prostor.

Nedostaci

  • Njegova složenost u najgorem slučaju slična je složenosti sortiranja mjehurića i sortiranje umetanjem.
  • Ova metoda sortiranja nije korisna kada već imamo sortirani popis.

Sortiranje gomile

Sortiranje gomile je napredna verzija stabla binarnog pretraživanja . Kod heap sortiranja, najveći element niza uvijek se postavlja na korijen stabla, a zatim se uspoređuje s korijenom s čvorovima lista.

Na primjer:

  • Dodijeljen nam je niz koji ima elemente “ 40, 100, 30, 50, 10 ”.
  • U “ koraku 1 ” napravili smo stablo prema prisutnost elemenata u nizu.

  • U “ koraku 2 ” izrađujemo maksimalnu hrpu, tj. raspoređujemo elemenata u silaznom redoslijedu. Najveći element ćenalaze se na vrhu (korijen), a najmanji element nalazi se na dnu (čvorovi lista). Zadani niz postaje “ 100, 50, 30, 40, 10 ”.

  • U “ koraku 3 ” , mi stvaraju minimalnu hrpu kako bismo mogli pronaći minimalne elemente niza. Čineći to, dobivamo maksimalne i minimalne elemente.

  • U “ koraku 4 ” izvođenjem istih koraka dobivamo sortirani niz.

Program za Heap sortiranje 

``` def HeapSortify( arr, n, i ): larger_element = i left = 2 * i + 1 right = 2 * i + 2 if left  n and arr[ larger_element ]  arr[ left ]: larger_element = left if right  n and arr[ larger_element ]  arr[ right ]: larger_element = right if larger_element != i: arr[ i ], arr[ larger_element ] = arr[ larger_element ], arr[ i ] HeapSortify( arr, n, larger_element ) def HeapSort( arr ): n = len( arr ) for i in range( n//2 - 1, -1, -1 ): HeapSortify( arr, n, i ) for i in range( n-1, 0, -1 ): arr[ i ], arr[ 0 ] = arr[ 0 ], arr[ i ] HeapSortify( arr, i, 0 ) arr = [ 11, 10, 12, 4, 5, 6 ] print( " The unsorted array is: ", arr ) HeapSort( arr ) n = len( arr ) print( " The sorted array sorted by the Heap Sort: " ) for i in range( n ): print( arr[ i ] ) ```

Izlaz

Vremenska složenost Heap sortiranja

  • Najgori slučaj: Najgora vremenska složenost Heap sortiranja je O( n log( n )).
  • Prosječni slučaj: Prosječna vremenska složenost za Heap sortiranje je O( n log( n )).
  • Najbolji slučaj: Najbolja vremenska složenost za Heap sortiranje je O( n log( n )).

Prednosti

  • Najviše se koristi zbog svoje produktivnosti.
  • Može biti implementiran kao algoritam na mjestu.
  • Ne zahtijeva veliku pohranu.

Nedostaci

  • Potreban je prostor za sortiranje elemenata.
  • Izrađuje stablo za sortiranje elemenata.

Usporedba između tehnika sortiranja

Metoda sortiranja Vremenska složenost u najboljem slučaju Prosječna vremenska složenost slučaja Vremenska složenost u najgorem slučaju Složenost prostora Stabilnost U -
Pomakni se na vrh