Naučite kako koristiti funkciju Python Sort za sortiranje lista, nizova, rječnika, itd. koristeći različite metode i algoritame sortiranja u Pythonu:
Sortiranje je tehnika koja se koristi za sortiranje podaci u nizu u uzlaznom ili opadajućem redoslijedu.
Većinu vremena podaci velikih projekata nisu raspoređeni u ispravnom redoslijedu i to stvara probleme prilikom efikasnog pristupa i dohvaćanja potrebnih podataka.
Tehnike sortiranja se koriste za rješavanje ovog problema. Python nudi različite tehnike sortiranja na primjer, Bubble sort, Insertion sort, Merge sort, Quicksort, itd.
U ovom vodiču ćemo razumjeti kako sortiranje funkcionira u Pythonu korištenjem različitih algoritama.
Python sortiranje
Sintaksa sortiranja Python
Za obavljanje sortiranja, Python pruža ugrađenu funkciju, tj. funkciju “ sort() ”. Koristi se za sortiranje elemenata podataka liste u rastućem ili opadajućem redoslijedu.
Shvatimo 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, data neuređena lista je sortirana u rastućem redoslijedu korištenjem 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, data neuređena lista se sortira obrnutim redoslijedom pomoću funkcije “ sort( reverse = True ) ”.
Vrijememjesto Razvrstavanje mehurića 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 Razvrstavanje hrpe O(n log (n)) O(n log(n)) O(n log(n)) O(1) Ne Da
U gornjoj tablici poređenja “O” je oznaka Velikog Oha objašnjena iznad, dok “n” i “N” znače veličinu ulaza .
Često postavljana pitanja
P #1) Šta je sort () u Pythonu?
Odgovor: U Pythonu sort() je funkcija koja se koristi za sortiranje lista ili nizova određenim redoslijedom. Ova funkcija olakšava proces sortiranja dok radite na velikim projektima. Veoma 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 oblačićima, sortiranje umetanjem, itd. Sve tehnike sortiranja su efikasne i lako razumljive.
P #3) Kako Python sortirati () posao?
Odgovor: Razvrstavanje()funkcija uzima dati niz kao ulaz od korisnika i sortira ga određenim redoslijedom koristeći algoritam sortiranja. Odabir algoritma ovisi o izboru korisnika. Korisnici mogu koristiti brzo sortiranje, sortiranje spajanjem, sortiranje oblačićima, sortiranje umetanjem, itd. ovisno o potrebama korisnika.
Zaključak
U gornjem tutorijalu, raspravljali smo o tehnici sortiranja u Pythonu zajedno sa opće tehnike sortiranja.
- Mjehurić sortiranje
- Umetanje sortiranje
- Brzo sortiranje
Učili smo o njihovoj vremenskoj složenosti i prednostima & nedostatke. Također smo uporedili sve gore navedene tehnike.
Složenost algoritama za sortiranjeVremenska složenost je količina vremena potrebnog računaru da pokrene određeni algoritam. Ima tri tipa slučajeva vremenske složenosti.
- Najgori slučaj: Maksimalno vrijeme potrebno računaru da pokrene program.
- Prosječni slučaj: Vrijeme potrebno između minimuma i maksimuma računaru da pokrene program.
- Najbolji slučaj: Minimalno vrijeme potrebno računaru da pokrene program. To je najbolji slučaj vremenske složenosti.
Notacije složenosti
Big Oh notation, O: Big oh notacija je službeni način za prenošenje gornje granice vremena rada algoritama. Koristi se za mjerenje vremenske složenosti u najgorem slučaju ili kažemo najveću količinu vremena potrebnog algoritmu da završi.
Velika omega notacija, : Velika omega notacija je službeni način da se prenese najniža granica vremena rada algoritama. Koristi se za mjerenje vremenske složenosti najboljeg slučaja ili kažemo odličnu količinu vremena potrebnog algoritmu.
Theta notacija, : Theta notacija je službeni način prenošenja obje granice, tj. donja i gornja granica vremena potrebnog algoritmu da završi.
Metode sortiranja u Pythonu
Sortiranje oblačićima
Sortiranje oblačićima je najjednostavniji način za sortiranje podataka koji koristi tehniku grube sile. On će ponoviti svaki element podataka i uporediti ga sa drugim elementimada pružimo korisniku sortirane podatke.
Uzmimo primjer kako bismo razumjeli ovu tehniku:
- Dobili smo niz koji ima elemente “ 10, 40, 7, 3, 15 ”. Sada, trebamo urediti ovaj niz u rastućem redoslijedu koristeći tehniku Bubble sortiranja u Pythonu.
- Prvi korak je sređivanje niza prema datom redoslijedu.
- U “Iteraciji 1” uspoređujemo prvi element niza sa ostalim elementima jedan po jedan.
- Crvene strelice opisuju poređenje prvih elemenata sa ostalim elementima niza.
- Ako primijetite da je “10” manje od “40” tako da ostaje isto mjesto, ali sljedeći element “7” je manji od “10”. Stoga se zamjenjuje i dolazi na prvo mjesto.
- Navedeni proces će se izvoditi iznova i iznova kako bi se elementi sortirali.
-
- U “ Iteraciji 2 ” drugi element se uspoređuje s ostalim elementima niza.
- Ako je upoređeni element tada mali, on će zamijenite, inače će ostati na istom mjestu.
-
- U “ Iteraciji 3 “ treći element se uspoređuje s ostalim elementima niza.
-
- U posljednjem “ Iteracija 4 “ drugi posljednji element se upoređuje s ostalim elementima niza.
- Uu ovom koraku niz se sortira uzlaznim redoslijedom.
Program za sortiranje oblačićima
``` 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 sortiranja mehurića
- Najgori slučaj: Najgora vremenska složenost za mjehurić sortiranje je O( n 2).
- Prosječni slučaj: Prosječna vremenska složenost za mjehurić sortiranje je O( n 2).
- Najbolji slučaj: Najbolja vremenska složenost za mehurasto sortiranje je O(n).
Prednosti
- Uglavnom se koristi i lako je implementirati.
- Možemo mijenjati elemente podataka bez potrošnje kratkoročne memorije.
- Zahtijeva manje prostor.
Nedostaci
- Nije dobro funkcionirao dok se bavio velikim brojem velikih elemenata podataka.
- To je potrebno je n 2 koraka za svaki “n” broj elemenata podataka da bi se sortirao.
- Nije baš dobro za aplikacije u stvarnom svijetu.
Umetanje Sortiraj
Razvrstavanje umetanjem je laka i jednostavna tehnika sortiranja koja funkcionira slično sortiranju igraćih karata. Sortiranje umetanjem sortira elemente upoređ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, sređujemo niz i počinjemo poreditiit.
- U prvom koraku “100” se poredi sa drugim elementom “50”. “ 50 ” se zamjenjuje sa “ 100 ” jer je veće.
- U drugom koraku, opet se drugi element “100” upoređuje s trećim elementom “30” i zamjenjuje se.
- Sada, ako primijetite da je “30” na prvom mjestu jer je opet manje od “50”.
- Poređenje će se dogoditi 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 za sortiranje 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 se bavi malim brojem elemenata podataka.
- Ne treba mu više prostora za implementaciju.
Nedostaci
- Nije od pomoći sortirati ogroman broj elemenata podataka.
- U poređenju s drugim tehnikama sortiranja, ne radi dobro.
Sortiranje spajanjem
Ova metoda sortiranja koristi metodu podijeli pa vladaj za sortiranje elemenata određenim redoslijedom. Prilikom sortiranja uz pomoć sortiranja spajanjem,elementi se dijele na polovine i potom se sortiraju. Nakon sortiranja svih polovica, elementi se ponovo spajaju kako bi formirali savršeni red.
Uzmimo primjer da bismo razumjeli ovu tehniku
- Dobili smo 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.
- Dalje, elementi su ponovo podijeljeni 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 kako smo bili podijeljeni.
- U koraku br. 5 ako primijetite da je 7 veće od 3, pa ćemo ih razmijeniti i pridružiti mu 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 za sortiranje spajanjem je O( n log( n )).
- Prosječni slučaj: Prosječna vremenska složenost za sortiranje 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 tehnika je dobra za podatke kojima se generalno pristupa u redoslijedu. Na primjer, povezane liste, traka, itd.
Nedostaci
- Zahtijeva više prostora u odnosu na druge tehnike sortiranja.
- Relativno je manje efikasan od ostalih.
Brzo sortiranje
Brzo sortiranje ponovo koristi metodu podijeli pa vladaj za sortiranje elemenata liste ili niz. Cilja na zaokretne elemente i sortira elemente prema odabranom pivot elementu.
Na primjer
- Pruža nam se 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 pivot elementa “ 7 ”, a desna sadrži elemente veće od pivot elementa “ 7 ”.
- Sada imamo dva niza “ 1,3,4,5 ” i “ 8, 9 ”.
- Opet, moramo podijeliti oba niza na isti način kao što smo učinili gore. Jedina razlika je u tome što se pivot elementi mijenjaju.
- Moramo podijeliti nizove dok ne dobijemo jedan element u nizu.
- Na kraju sakupite sve pivot elemente u niz s lijeva na desno i dobićete sortiranoniz.
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.
- Korisan je pri rukovanju velikom količinom podataka.
- Ne zahtijeva dodatni prostor.
Nedostaci
- Njegova složenost u najgorem slučaju slična je složenosti sortiranja mehurića i sortiranje umetanjem.
- Ova metoda sortiranja nije korisna kada već imamo sortiranu listu.
Sortiranje hrpe
Sortiranje hrpe je napredna verzija binarnog stabla pretraživanja . U sortiranju hrpe, najveći element niza se uvijek postavlja na korijen stabla, a zatim se upoređuje s korijenom sa lisnim čvorovima.
Na primjer:
- Omogućen 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 ” pravimo maksimalnu hrpu, tj. elemenata u opadajućem redosledu. Najveći element ćenalaze se na vrhu (korijen), a najmanji element se nalazi na dnu (listni čvorovi). Dati niz postaje “ 100, 50, 30, 40, 10 ”.
- U “ koraku 3 ” , mi prave minimalnu hrpu tako da možemo pronaći minimalne elemente niza. Na taj način dobijamo maksimalne i minimalne elemente.
- U “ korak 4 ” izvođenjem istih koraka dobijamo sortirani niz.
Program za sortiranje hrpe
``` 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 sortiranja hrpe
- Najgori slučaj: Najgora vremenska složenost za sortiranje hrpe je O( n log( n )).
- Prosječni slučaj: Prosječna vremenska složenost za sortiranje hrpe je O( n log( n )).
- Najbolji slučaj: Najbolja vremenska složenost za sortiranje hrpe je O( n log( n )).
Prednosti
- Uglavnom se koristi zbog svoje produktivnosti.
- Može biti implementiran kao algoritam na mjestu.
- Ne zahtijeva veliku pohranu.
Nedostaci
- Potreban je prostor za sortiranje elemenata.
- Pravi stablo za sortiranje elemenata.
Poređenje između tehnika sortiranja
Metoda sortiranja | Vremenska složenost najboljeg slučaja | Prosječna vremenska složenost slučaja | Vremenska složenost najgoreg slučaja | Složenost prostora | Stabilnost | U - |
---|