Sužinokite, kaip naudoti "Python Sort" funkciją, kad rūšiuotumėte sąrašus, masyvus, žodynus ir t. t., naudodami įvairius rūšiavimo metodus ir algoritmus programoje "Python":
Rūšiavimas - tai metodas, naudojamas duomenims rūšiuoti didėjančia arba mažėjančia tvarka.
Dažniausiai didelių projektų duomenys nėra išdėstyti tinkama tvarka, todėl kyla problemų, kai reikiami duomenys pasiekiami ir gaunami efektyviai.
Šiai problemai išspręsti naudojami rūšiavimo metodai. Python siūlo įvairius rūšiavimo metodus pvz, Burbulinis rūšiavimas, įterpimo rūšiavimas, sujungimo rūšiavimas, greitas rūšiavimas ir t. t.
Šioje pamokoje suprasime, kaip "Python" veikia rūšiavimas naudojant įvairius algoritmus.
Python rūšiavimas
"Python Sort" sintaksė
Rūšiavimui atlikti "Python" turi integruotą funkciją, t. y. funkciją " sort() ". Ji naudojama sąrašo duomenų elementams rūšiuoti didėjimo arba mažėjimo tvarka.
Supraskime šią sąvoką remdamiesi pavyzdžiu.
1 pavyzdys:
```` a = [ 3, 5, 2, 6, 7, 9, 8, 1, 4 ] a.sort() print( " Sąrašas didėjančia tvarka: ", a ) ````
Išvestis:
Šiame pavyzdyje pateiktas nesurūšiuotas sąrašas surūšiuojamas didėjimo tvarka naudojant funkciją " sort( ) ".
2 pavyzdys:
```` a = [ 3, 5, 2, 6, 7, 9, 8, 1, 4 ] a.sort( reverse = True ) print( " Sąrašas mažėjančia tvarka: ", a ) ````
Išėjimas
Pirmiau pateiktame pavyzdyje pateiktas nesurašytas sąrašas surūšiuojamas atvirkštine tvarka naudojant funkciją " sort( reverse = True ) ".
Rūšiavimo algoritmų laiko sudėtingumas
Laiko sudėtingumas - tai laikas, kurį kompiuteris sugaišta tam tikram algoritmui paleisti. Skiriami trys laiko sudėtingumo atvejų tipai.
- Blogiausiu atveju: Maksimalus laikas, per kurį kompiuteris paleidžia programą.
- Vidutinis atvejis: Laikas, kurį kompiuteris užtrunka nuo mažiausio iki didžiausio programos paleidimo laiko.
- Geriausias atvejis: Minimalus laikas, per kurį kompiuteris paleidžia programą. Tai geriausias laiko sudėtingumo atvejis.
Sudėtingumo užrašai
Big Oh Notation, O: Big oh užrašas yra oficialus būdas perteikti viršutinę algoritmų veikimo laiko ribą. Jis naudojamas matuojant blogiausio atvejo laiko sudėtingumą, arba sakome, kad tai didžiausias laikas, per kurį algoritmas įvykdomas.
Didžioji omega užrašas, : Didžiosios omegos užrašas yra oficialus būdas perteikti algoritmų veikimo laiko žemiausią ribą. Jis naudojamas matuojant geriausio atvejo laiko sudėtingumą arba sakome, kad algoritmas užima puikų laiko kiekį.
Theta užrašas, : Theta užrašas yra oficialus būdas abiem riboms, t. y. apatinei ir viršutinei, per kiek laiko algoritmas bus baigtas, perteikti.
Rūšiavimo metodai programoje "Python
Burbulų rūšiavimas
Burbulinis rūšiavimas yra paprasčiausias duomenų rūšiavimo būdas, kuriam naudojamas brutalios jėgos metodas. Jis iteruoja kiekvieną duomenų elementą ir palygina jį su kitais elementais, kad naudotojui pateiktų surūšiuotus duomenis.
Paimkime pavyzdį, kad suprastume šį metodą:
- Turime masyvą su elementais " 10, 40, 7, 3, 15 ". Dabar turime šį masyvą išdėstyti didėjančia tvarka, naudodami Python burbulinio rūšiavimo metodą.
- Pirmasis žingsnis - išdėstyti masyvą nurodyta tvarka.
- Atliekant "1 iteraciją", pirmasis masyvo elementas lyginamas su kitais elementais po vieną.
- Raudonomis rodyklėmis aprašomas pirmųjų elementų palyginimas su kitais masyvo elementais.
- Jei pastebėsite, kad " 10 " yra mažesnis už " 40 ", todėl jis lieka toje pačioje vietoje, bet kitas elementas " 7 " yra mažesnis už " 10 ". Todėl jis pakeičiamas ir atsiduria pirmoje vietoje.
- Pirmiau aprašytas procesas bus atliekamas dar ir dar kartą, kad elementai būtų surūšiuoti.
- Atliekant "2 iteraciją" antrasis elementas lyginamas su kitais masyvo elementais.
- Jei lyginamas elementas yra mažas, jis bus pakeistas, kitu atveju jis liks toje pačioje vietoje.
- "Iteracijos 3" metu trečiasis elementas lyginamas su kitais masyvo elementais.
- Paskutinėje "4 iteracijoje" priešpaskutinis elementas lyginamas su kitais masyvo elementais.
- Šiame etape masyvas surūšiuojamas didėjančia tvarka.
Burbulų rūšiavimo programa
``` 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 unsorted_list = [5, 3, 8, 6, 7, 2] print("Nesurūšiuotas sąrašas: ", unsorted_list) print("Rūšiuotas sąrašas naudojant Bubble SortTechnika: ", Bubble_Sort(unsorted_list)) ````
Išėjimas
Burbulų rūšiavimo laiko sudėtingumas
- Blogiausiu atveju: Blogiausias burbulų rūšiavimo laiko sudėtingumas yra O( n 2).
- Vidutinis atvejis: Vidutinis burbulų rūšiavimo laiko sudėtingumas yra O( n 2).
- Geriausias atvejis: Geriausias burbulų rūšiavimo laiko sudėtingumas yra O(n).
Privalumai
- Jis dažniausiai naudojamas ir jį lengva įdiegti.
- Duomenų elementus galime keisti nenaudodami trumpalaikės saugyklos.
- Jam reikia mažiau vietos.
Trūkumai
- Jis nebuvo veiksmingas, kai reikėjo apdoroti daug didelių duomenų elementų.
- Reikia n 2 veiksmai kiekvienam "n" duomenų elementų skaičiui rūšiuoti.
- Tai nėra labai tinkama realioms programoms.
Įterpimo rūšiavimas
Įterpimo rūšiavimas yra lengvas ir paprastas rūšiavimo metodas, kuris veikia panašiai kaip žaidimo kortų rūšiavimas. Įterpimo rūšiavimas rūšiuoja elementus, kiekvieną elementą po vieną lygindamas su kitu. Elementai atrenkami ir sukeičiami vietomis su kitu elementu, jei elementas yra didesnis arba mažesnis už kitą.
Paimkime pavyzdį
- Turime masyvą su elementais " 100, 50, 30, 40, 10 ".
- Pirmiausia sutvarkome masyvą ir pradedame jį lyginti.
- Pirmajame etape " 100 " lyginamas su antruoju elementu " 50 ". " 50 " sukeičiamas vietomis su " 100 ", nes jis yra didesnis.
- Antrajame etape antrasis elementas " 100 " vėl lyginamas su trečiuoju elementu " 30 " ir sukeičiamas vietomis.
- Dabar, jei pastebėsite, " 30 " yra pirmoje vietoje, nes ji vėl mažesnė už " 50 ".
- Palyginimas vyks iki paskutinio masyvo elemento, o pabaigoje gausime surūšiuotus duomenis.
Įterpimo rūšiavimo programa
``` 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("Nerūšiuotas masyvas: ", array) InsertionSort(array) print ("Rūšiuotas masyvas naudojant Insertion Sort: ") for i in range(len(array)): print (array[i]) ```
Išėjimas
Įterpimo rūšiavimo laiko sudėtingumas
- Blogiausiu atveju: Blogiausias įterpimo rūšiavimo laiko sudėtingumas yra O( n 2).
- Vidutinis atvejis: Vidutinis įterpimo rūšiavimo laiko sudėtingumas yra O( n 2).
- Geriausias atvejis: Geriausias įterpimo rūšiavimo laiko sudėtingumas yra O(n).
Privalumai
- Tai paprasta ir lengva įgyvendinti.
- Jis gerai veikia, kai reikia apdoroti nedidelį duomenų elementų skaičių.
- Jai įgyvendinti nereikia daugiau vietos.
Trūkumai
- Nėra naudinga rūšiuoti daugybę duomenų elementų.
- Lyginant su kitais rūšiavimo būdais, jis veikia prastai.
Sujungti rūšiavimą
Šis rūšiavimo metodas naudoja "skaldyk ir valdyk" metodą, kad elementai būtų surūšiuoti tam tikra tvarka. Atliekant rūšiavimą naudojant "merge sort", elementai padalijami į dalis ir tada surūšiuojami. Surūšiavus visas dalis, elementai vėl sujungiami, kad būtų sudaryta ideali tvarka.
Paimkime pavyzdį, kad suprastume šį metodą
- Turime masyvą " 7, 3, 40, 10, 20, 15, 6, 5 ". Masyvą sudaro 7 elementai. Jei jį padalysime per pusę ( 0 + 7 / 2 = 3 ).
- Antrajame etape pamatysite, kad elementai padalyti į dvi dalis. Kiekvienoje jų yra po 4 elementus.
- Be to, elementai vėl suskirstomi ir turi po 2 elementus.
- Šis procesas tęsis tol, kol masyve bus tik vienas elementas. Žr. 4 žingsnį paveikslėlyje.
- Dabar surūšiuosime elementus ir pradėsime juos jungti taip, kaip buvome suskirstyti.
- 5 žingsnyje, jei pastebėjote, kad 7 yra didesnis už 3, todėl kitame žingsnyje juos pakeisime ir sujungsime, ir atvirkščiai.
- Pabaigoje pastebėsite, kad mūsų masyvas surūšiuojamas didėjimo tvarka.
Programa "Merge sort
``` 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 inrange(len(arr)): print(arr[i],) print() arr = [12, 11, 13, 5, 6, 7] print("Duotas masyvas yra", end="\n") PrintSortedList(arr) MergeSort(arr) print("Rūšiuotas masyvas yra: ", end="\n") PrintSortedList(arr) ````
Išėjimas
Sujungimo rūšiavimo laiko sudėtingumas
- Blogiausiu atveju: Blogiausias suliejimo rūšiavimo laiko sudėtingumas yra O( n log( n )).
- Vidutinis atvejis: Vidutinis suliejimo rūšiavimo laiko sudėtingumas yra O( n log( n )).
- Geriausias atvejis: Geriausias suliejimo rūšiavimo laiko sudėtingumas yra O( n log( n )).
Privalumai
- Šiam rūšiavimo būdui failo dydis neturi reikšmės.
- Šis metodas tinka duomenims, kurie paprastai pasiekiami eilės tvarka. Pavyzdžiui, susieti sąrašai, juostinis diskas ir kt.
Trūkumai
- Palyginti su kitais rūšiavimo būdais, jam reikia daugiau vietos.
- Jis yra palyginti mažiau veiksmingas nei kiti.
Greitas rūšiavimas
Greitasis rūšiavimas vėl naudoja metodą "skaldyk ir valdyk", kad surūšiuotų sąrašo arba masyvo elementus. Jis nukreipia į ašinius elementus ir surūšiuoja elementus pagal pasirinktą ašinį elementą.
Pavyzdžiui.
- Mums pateikiamas masyvas, kurio elementai yra " 1,8,3,9,4,5,7 ".
- Tarkime, kad " 7 " yra bandomasis elementas.
- Dabar padalysime masyvą taip, kad kairėje pusėje būtų elementai, kurie yra mažesni už posūkio elementą " 7 ", o dešinėje pusėje - elementai, didesni už posūkio elementą " 7 ".
- Dabar turime du masyvus " 1,3,4,5 " ir " 8, 9 ".
- Vėl turime padalyti abu masyvus taip pat, kaip ir anksčiau. Skirtumas tik tas, kad keičiasi sukimosi elementai.
- Reikia dalyti masyvus tol, kol gausime vienintelį masyvo elementą.
- Pabaigoje surinkite visus sukamuosius elementus iš eilės iš kairės į dešinę ir gausite surūšiuotą masyvą.
Greito rūšiavimo programa
``` 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, mažiausias, didžiausias ) QuickSort( arr, mažiausias, pi-1 ) QuickSort( arr, pi+1, didžiausias ) arr = [ 9, 6, 7, 8, 0, 4 ] n = len( arr ) print( " Nerūšiuotas masyvas: ", arr ) QuickSort( arr, 0, n-1 ) print( " Rūšiuotas masyvas naudojant Quick Sort: " ) for i in range( n ): print( " %d " % arr[ i ] ) ````
Išėjimas
Greito rūšiavimo laiko sudėtingumas
- Blogiausiu atveju: Blogiausias greitojo rūšiavimo laiko sudėtingumas yra O( n 2).
- Vidutinis atvejis: Vidutinis greitojo rūšiavimo laiko sudėtingumas yra O( n log( n )).
- Geriausias atvejis: Geriausias greitojo rūšiavimo laiko sudėtingumas yra O( n log( n )).
Privalumai
- Jis žinomas kaip geriausias rūšiavimo algoritmas "Python" programoje.
- Tai naudinga tvarkant didelį duomenų kiekį.
- Jam nereikia papildomos vietos.
Trūkumai
- Jos sudėtingumas blogiausiu atveju yra panašus į burbulinio rūšiavimo ir įterpimo rūšiavimo sudėtingumą.
- Šis rūšiavimo metodas nenaudingas, kai jau turime surūšiuotą sąrašą.
Rūšiuoti į krūvą
"Heap sort" yra išplėstinė dvejetainio paieškos medžio versija. "Heap sort" atveju didžiausias masyvo elementas visada dedamas į medžio šaknį, o tada lyginamas su šaknimi su lapų mazgais.
Pavyzdžiui:
- Turime masyvą su elementais " 40, 100, 30, 50, 10 ".
- Svetainėje " 1 žingsnis " sudarėme medį pagal elementų buvimą masyve.
- " 2 žingsnis " sudarome maksimalią krūvą, t. y. elementus išdėstome mažėjančia tvarka. Didžiausias elementas bus viršuje (šaknis), o mažiausias elementas - apačioje (lapų mazgai). Pateiktas masyvas tampa " 100, 50, 30, 40, 10 ".
- Svetainėje " 3 žingsnis " , sudarome mažiausią krūvą, kad galėtume rasti mažiausius masyvo elementus. Tai darydami gauname didžiausius ir mažiausius elementus.
- Svetainėje " 4 žingsnis " atlikdami tuos pačius veiksmus gausime surūšiuotą masyvą.
"Heap sort" programa
``` 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( " Nerūšiuotas masyvas yra: ", arr ) HeapSort( arr ) n = len( arr ) print( " Išrūšiuotas masyvas, surūšiuotas pagal Heap Sort: " ) for i in range( n ): print( arr[ i ] ) ````
Išėjimas
Krūvos rūšiavimo laiko sudėtingumas
- Blogiausiu atveju: Blogiausias krūvos rūšiavimo laiko sudėtingumas yra O( n log( n )).
- Vidutinis atvejis: Vidutinis krūvos rūšiavimo laiko sudėtingumas yra O( n log( n )).
- Geriausias atvejis: Geriausias krūvos rūšiavimo laiko sudėtingumas yraO( n log( n )).
Privalumai
- Jis dažniausiai naudojamas dėl savo našumo.
- Jis gali būti įgyvendintas kaip "in-place" algoritmas.
- Jam nereikia didelės saugyklos.
Trūkumai
- Reikia vietos elementams rūšiuoti.
- Jis sukuria medį, skirtą elementams rūšiuoti.
Rūšiavimo metodų palyginimas
Rūšiavimo metodas | Geriausio atvejo laiko sudėtingumas | Vidutinis bylos laiko sudėtingumas | Blogiausio atvejo laiko sudėtingumas | Erdvės sudėtingumas | Stabilumas | Į - vieta |
---|---|---|---|---|---|---|
Burbulų rūšiavimas | O(n) | O(n2) | O(n2) | O(1) | Taip | Taip |
Įterpimo rūšiavimas | O(n) | O(n2) | O(n2) | O(1) | Taip | Taip |
Greitas rūšiavimas | O(n log(n)) | O(n log(n)) | O(n2) | O(N) | Ne | Taip |
Sujungti rūšiavimą | O(n log(n)) | O(n log(n)) | O(n log(n)) | O(N) | Taip | Ne |
Rūšiuoti į krūvą | O(n log(n)) | O(n log(n)) | O(n log(n)) | O(1) | Ne | Taip |
Pirmiau pateiktoje palyginimo lentelėje " O " - tai pirmiau paaiškintas "Big Oh" užrašas, o " n " ir " N " reiškia įvesties dydį.
Dažnai užduodami klausimai
Klausimas Nr. 1) Kas yra rūšiavimas () programoje "Python"?
Atsakymas: Python sort() - tai funkcija, naudojama sąrašams ar masyvams rūšiuoti tam tikra tvarka. Ši funkcija palengvina rūšiavimo procesą dirbant su dideliais projektais. Ji labai naudinga programuotojams.
2 klausimas) Kaip rūšiuoti "Python" kalba?
Atsakymas: "Python" siūlo įvairius rūšiavimo būdus, kurie naudojami elementams rūšiuoti. Pavyzdžiui, Greitasis rūšiavimas, sujungimo rūšiavimas, burbulinis rūšiavimas, įterpimo rūšiavimas ir t. t. Visi rūšiavimo būdai yra veiksmingi ir lengvai suprantami.
Q #3) Kaip veikia Python sort ()?
Atsakymas: Funkcija sort() priima duotą masyvą kaip naudotojo įvestį ir rūšiuoja jį tam tikra tvarka naudodama rūšiavimo algoritmą. Algoritmo pasirinkimas priklauso nuo naudotojo pasirinkimo. Naudotojai gali naudoti greitąjį rūšiavimą, sujungimo rūšiavimą, burbulinį rūšiavimą, įterpimo rūšiavimą ir t. t., priklausomai nuo naudotojo poreikių.
Išvada
Pirmiau pateiktoje pamokoje aptarėme rūšiavimo būdą Pythone ir bendruosius rūšiavimo būdus.
- Burbulų rūšiavimas
- Įterpimo rūšiavimas
- Greitasis rūšiavimas
Sužinojome apie jų laiko sudėtingumą ir privalumus & amp; trūkumus. Taip pat palyginome visus minėtus metodus.