Uzziniet, kā izmantot Python Sort funkciju sarakstu, masīvu, vārdnīcu utt. šķirošanai, izmantojot dažādas šķirošanas metodes un algoritmus Python:
Šķirošana ir metode, ko izmanto datu sakārtošanai secīgā secībā augošā vai dilstošā secībā.
Lielākoties lielo projektu dati nav sakārtoti pareizā secībā, un tas rada problēmas, efektīvi piekļūstot vajadzīgajiem datiem un tos iegūstot.
Lai atrisinātu šo problēmu, tiek izmantoti šķirošanas paņēmieni. Python piedāvā dažādus šķirošanas paņēmienus. piemēram, Burbuļveida šķirošana, Ievietošanas šķirošana, Apvienošanas šķirošana, Ātrā šķirošana u. c.
Šajā pamācībā mēs sapratīsim, kā darbojas šķirošana Python programmā, izmantojot dažādus algoritmus.
Python šķirošana
Python Sort sintakse
Lai veiktu šķirošanu, Python ir iebūvēta funkcija " sort() ". To izmanto, lai saraksta datu elementus sakārtotu augošā vai dilstošā secībā.
Izpratīsim šo jēdzienu ar piemēru.
1. piemērs:
```` a = [ 3, 5, 2, 6, 7, 9, 8, 1, 4 ] a.sort() print( " Saraksts augošā secībā: ", a ) ````
Izvades rezultāts:
Šajā piemērā dotais nesakārtotais saraksts tiek sakārtots augošā secībā, izmantojot funkciju " sort( ) ".
2. piemērs:
```` a = [ 3, 5, 2, 6, 7, 9, 8, 1, 4 ] a.sort( reverse = True ) print( " Saraksts dilstošā secībā: ", a ) ````
Izvades
Iepriekš minētajā piemērā dotais nesakārtotais saraksts tiek sakārtots apgrieztā secībā, izmantojot funkciju " sort( reverse = True ) ".
Šķirošanas algoritmu laika sarežģītība
Laika sarežģītība ir laiks, ko dators patērē, lai izpildītu konkrētu algoritmu. Tai ir trīs laika sarežģītības gadījumu veidi.
- Sliktākais gadījums: Maksimālais laiks, ko dators patērē, lai palaistu programmu.
- Vidējais gadījums: Laiks, kas datoram nepieciešams, lai palaistu programmu no minimālā līdz maksimālajam laikam.
- Labākais gadījums: Minimālais laiks, ko dators patērē programmas izpildei. Tas ir labākais laika sarežģītības gadījums.
Sarežģītības apzīmējumi
Big Oh Notation, O: Big oh apzīmējums ir oficiāls veids, kā izteikt algoritmu darbības laika augšējo robežu. To izmanto, lai izmērītu sliktākā gadījuma laika sarežģītību jeb mēs sakām, lielāko laika daudzumu, kas nepieciešams algoritma izpildei.
Lielā omega Notācija, : Lielā omega notācija ir oficiāls veids, kā izteikt algoritmu darbības laika zemāko robežu. To izmanto, lai izmērītu labākā gadījuma laika sarežģītību jeb mēs sakām, ka algoritms aizņem lielisku laiku.
Theta notācija, : Theta apzīmējums ir oficiāls veids, kā izteikt abas robežas, t. i., algoritma izpildes laika apakšējo un augšējo robežu.
Šķirošanas metodes programmā Python
Burbuļu šķirošana
Burbuļveida šķirošana ir vienkāršākais datu šķirošanas veids, kas izmanto brutālā spēka tehniku. Tā iterē katru datu elementu un salīdzina to ar citiem elementiem, lai sniegtu lietotājam sakārtotus datus.
Lai izprastu šo metodi, aplūkosim piemēru:
- Mums ir dots masīvs ar elementiem " 10, 40, 7, 3, 15 ". Tagad mums šis masīvs jāsakārto augošā secībā, izmantojot Python burbuļveida šķirošanas metodi.
- Pirmais solis ir sakārtot masīvu dotajā secībā.
- "Iterācijā 1" mēs salīdzinām masīva pirmo elementu ar pārējiem elementiem pa vienam.
- Sarkanās bultas apraksta pirmo elementu salīdzināšanu ar citiem masīva elementiem.
- Ja pamanāt, ka " 10 " ir mazāks par " 40 ", tas paliek tajā pašā vietā, bet nākamais elements " 7 " ir mazāks par " 10 ". Tādējādi tas tiek aizstāts un ieņem pirmo vietu.
- Iepriekš minētais process tiks veikts atkal un atkal, lai sakārtotu elementus.
- " 2. iterācijā " otrais elements tiek salīdzināts ar citiem masīva elementiem.
- Ja salīdzinātais elements ir mazs, tas tiks nomainīts, pretējā gadījumā tas paliks tajā pašā vietā.
- " 3. iterācijā " trešais elements tiek salīdzināts ar citiem masīva elementiem.
- Pēdējā " Iterācija 4 " priekšpēdējais elements tiek salīdzināts ar citiem masīva elementiem.
- Šajā solī masīvs tiek sakārtots augošā secībā.
Programma burbuļu šķirošanai
``` 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("Nesortificēts saraksts: ", unsorted_list) print("Sarindots saraksts ar Bubble SortTehnika: ", Bubble_Sort(unsorted_list)) ````
Izvades
Burbuļu šķirošanas laika sarežģītība
- Sliktākais gadījums: Burbuļveida šķirošanas sliktākā laika sarežģītība ir O( n 2).
- Vidējais gadījums: Burbuļveida šķirošanas vidējā laika sarežģītība ir O( n 2).
- Labākais gadījums: Labākā burbuļu šķirošanas laika sarežģītība ir O(n).
Priekšrocības
- To izmanto visbiežāk, un to ir viegli ieviest.
- Mēs varam apmainīt datu elementus, neizmantojot īstermiņa atmiņu.
- Tam nepieciešams mazāk vietas.
Trūkumi
- Tā nedarbojās labi, strādājot ar lielu skaitu lielu datu elementu.
- Tam ir nepieciešams n 2 soļi katram "n" sakārtojamo datu elementu skaitam.
- Tas nav īsti piemērots reālās pasaules lietojumiem.
Ievietošanas šķirošana
Ievietošanas šķirošana ir viegla un vienkārša šķirošanas metode, kas darbojas līdzīgi kā spēļu kāršu šķirošana. Ievietošanas šķirošana šķiro elementus, salīdzinot katru elementu pa vienam ar otru. Elementi tiek atlasīti un apmainīti ar citu elementu, ja šis elements ir lielāks vai mazāks par citu.
Pieņemsim piemēru
- Mums ir dots masīvs ar elementiem " 100, 50, 30, 30, 40, 10 ".
- Vispirms sakārtojam masīvu un sākam to salīdzināšanu.
- Pirmajā solī " 100 " salīdzina ar otro elementu " 50 ". " 50 " nomaina ar " 100 ", jo tas ir lielāks.
- Otrajā solī atkal tiek salīdzināts otrais elements " 100 " ar trešo elementu " 30 " un tiek apmainīts.
- Tagad, ja pamanāt, " 30 " ir pirmajā vietā, jo tas atkal ir mazāks par " 50 ".
- Salīdzināšana notiks līdz masīva pēdējam elementam, un beigās mēs iegūsim sakārtotus datus.
Ievietošanas šķirošanas programma
```` 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("Nesašķirots masīvs: ", array) InsertionSort(array) print ("Sakārtots masīvs, izmantojot Insertion Sort: ") for i in range(len(array)): print (array[i]) ````
Izvades
Ievietošanas šķirošanas laika sarežģītība
- Sliktākais gadījums: Visnelabākā laika sarežģītība iestarpināšanas šķirošanai ir O( n 2).
- Vidējais gadījums: Ievietošanas šķirošanas vidējā laika sarežģītība ir O( n 2).
- Labākais gadījums: Vislabākā laika sarežģītība Insertion sort ir O(n).
Priekšrocības
- Tas ir vienkārši un viegli īstenojams.
- Tā labi darbojas, strādājot ar nelielu datu elementu skaitu.
- Tās īstenošanai nav nepieciešams vairāk vietas.
Trūkumi
- Nav lietderīgi šķirot lielu datu elementu skaitu.
- Salīdzinot ar citiem šķirošanas paņēmieniem, tā darbojas slikti.
Apvienot šķirošana
Šī šķirošanas metode izmanto metodi "sadali un valdi", lai sakārtotu elementus noteiktā secībā. Šķirojot ar apvienošanas šķirošanas metodi, elementi tiek sadalīti uz pusēm un pēc tam tie tiek sakārtoti. Pēc visu pušu sakārtošanas elementi atkal tiek apvienoti, lai izveidotu perfektu secību.
Lai izprastu šo paņēmienu, aplūkosim piemēru.
- Mums ir dots masīvs " 7, 3, 40, 10, 20, 15, 6, 5 ". Masīvā ir 7 elementi. Ja mēs to sadalām uz pusēm ( 0 + 7 / 2 = 3 ).
- Otrajā solī redzēsiet, ka elementi ir sadalīti divās daļās. Katrā no tām ir 4 elementi.
- Tālāk elementi atkal ir sadalīti, un katram ir 2 elementi.
- Šis process turpināsies, līdz masīvā būs tikai viens elements. Skat. 4. soli attēlā.
- Tagad mēs sašķirosim elementus un sāksim tos savienot, kā mēs bijām sadalīti.
- 5. solī, ja pamanāt, ka 7 ir lielāks par 3, tāpēc nākamajā solī mēs tos apmainīsim un apvienosim, un otrādi.
- Beigās redzēsiet, ka mūsu masīvs tiek sakārtots augošā secībā.
Programma apvienošanas šķirošanai
``` 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("Dotais masīvs ir", end="\n") PrintSortedList(arr) MergeSort(arr) print("Sarindotais masīvs ir: ", end="\n") PrintSortedList(arr) ````
Izvades
Apvienošanas šķirošanas laika sarežģītība
- Sliktākais gadījums: Sarežģītākā apvienošanas šķirošanas laika sarežģītība ir O( n log( n )).
- Vidējais gadījums: Vidējā apvienošanas šķirošanas laika sarežģītība ir O( n log( n )).
- Labākais gadījums: Labākā apvienošanas šķirošanas laika sarežģītība ir O( n log( n )).
Priekšrocības
- Šai šķirošanas metodei nav nozīmes faila lielumam.
- Šī metode ir piemērota datiem, kuriem parasti piekļūst secīgā secībā. Piemēram, saistītie saraksti, lentes disks utt.
Trūkumi
- Salīdzinot ar citām šķirošanas metodēm, tas prasa vairāk vietas.
- Tas ir salīdzinoši mazāk efektīvs nekā citi.
Ātrā šķirošana
Lai sakārtotu saraksta vai masīva elementus, atkal tiek izmantota metode "sadali un valdi". Tā ir vērsta uz šarnīra elementiem un sakārto elementus atbilstoši izvēlētajam šarnīra elementam.
Piemēram.
- Mums ir dots masīvs ar elementiem " 1,8,3,9,4,5,7 ".
- Pieņemsim, ka " 7 " ir izmēģinājuma elements.
- Tagad mēs sadalīsim masīvu tā, lai kreisajā pusē būtu elementi, kas ir mazāki par šarnīra elementu " 7 ", bet labajā pusē būtu elementi, kas ir lielāki par šarnīra elementu " 7 ".
- Tagad mums ir divi masīvi " 1,3,4,5 " un " 8, 9 ".
- Atkal mums ir jāsadala abi masīvi tāpat kā iepriekš. Vienīgā atšķirība ir tā, ka mainās šarnīra elementi.
- Mums ir jādala masīvi, līdz iegūstam vienu elementu masīvā.
- Beigās savāc visus šarnīra elementus secīgi no kreisās uz labo pusi, un iegūsi sakārtotu masīvu.
Ātrās šķirošanas programma
``` 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, zemākais, augstākais ) QuickSort( arr, zemākais, pi-1 ) QuickSort( arr, pi+1, augstākais ) arr = [ 9, 6, 6, 7, 8, 0, 4 ] n = len( arr ) print( " Nešķirots masīvs: ", arr ) QuickSort( arr, 0, n-1 ) print( " Šķirots masīvs, izmantojot Quick Sort: " ) for i in range( n ): print( " %d " % arr[ i ] ) ````
Izvades
Ātrās šķirošanas laika sarežģītība
- Sliktākais gadījums: Ātrās šķirošanas sliktākā laika sarežģītība ir O( n 2).
- Vidējais gadījums: Ātrās šķirošanas vidējā laika sarežģītība ir O( n log( n )).
- Labākais gadījums: Labākā ātrās šķirošanas laika sarežģītība ir O( n log( n )).
Priekšrocības
- Tas ir pazīstams kā labākais šķirošanas algoritms Python.
- Tas ir noderīgs, apstrādājot lielu datu apjomu.
- Tam nav nepieciešama papildu vieta.
Trūkumi
- Tās sarežģītība sliktākajā gadījumā ir līdzīga burbuļveida šķirošanas un ievietošanas šķirošanas sarežģītībai.
- Šī šķirošanas metode nav lietderīga, ja mums jau ir sakārtots saraksts.
Kūdu šķirošana
Heap sort ir uzlabota bināro meklēšanas koku versija. Heap sort gadījumā lielākais masīva elements vienmēr tiek novietots koka saknē, un pēc tam tas tiek salīdzināts ar sakni ar lapu mezgliem.
Piemēram:
- Mums ir dots masīvs ar elementiem " 40, 100, 30, 50, 10 ".
- In " 1. solis " mēs izveidojām koku pēc elementu klātbūtnes masīvā.
- In " 2. solis " mēs veidojam maksimālo kaudzi, t. i., sakārtojam elementus dilstošā secībā. Lielākais elements atradīsies augšā (sakne), bet mazākais elements - apakšā (lapu mezgli). Dotais masīvs kļūst " 100, 50, 30, 40, 10 ".
- In " 3. solis " , mēs veidojam minimālo kaudzi, lai varētu atrast masīva minimālos elementus. Šādi rīkojoties, mēs iegūstam maksimālo un minimālo elementu.
- In " 4. solis " veicot tos pašus soļus, mēs iegūstam sakārtotu masīvu.
Programma kaudzes šķirošanai
``` 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( " Nešķirots masīvs ir: ", arr ) HeapSort( arr ) n = len( arr ) print( " Šķirots masīvs, sakārtots ar Heap Sort: " ) for i in range( n ): print( arr[ i ] )``
Izvades
Kravas kārtu šķirošanas laika sarežģītība
- Sliktākais gadījums: Visnelabākā laika sarežģītība Heap sort ir O( n log( n )).
- Vidējais gadījums: Heap šķirošanas vidējā laika sarežģītība ir O( n log( n )).
- Labākais gadījums: Labākā kaudzes šķirošanas laika sarežģītība irO( n log( n )).
Priekšrocības
- To galvenokārt izmanto tā produktivitātes dēļ.
- To var īstenot kā algoritmu, kas darbojas uz vietas.
- Tam nav nepieciešama liela uzglabāšana.
Trūkumi
- Nepieciešama vieta elementu šķirošanai.
- Tas veido elementu šķirošanas koku.
Šķirošanas metožu salīdzinājums
Šķirošanas metode | Labākā gadījuma laika sarežģītība | Vidējā lietas laika sarežģītība | Sliktākā gadījuma laika sarežģītība | Kosmosa sarežģītība | Stabilitāte | In - vietā |
---|---|---|---|---|---|---|
Burbuļu šķirošana | O(n) | O(n2) | O(n2) | O(1) | Jā | Jā |
Ievietošanas šķirošana | O(n) | O(n2) | O(n2) | O(1) | Jā | Jā |
Ātrā šķirošana | O(n log(n)) | O(n log(n)) | O(n2) | O(N) | Nē | Jā |
Apvienot šķirošana | O(n log(n)) | O(n log(n)) | O(n log(n)) | O(N) | Jā | Nē |
Kūdu šķirošana | O(n log(n)) | O(n log(n)) | O(n log(n)) | O(1) | Nē | Jā |
Iepriekš minētajā salīdzinājuma tabulā " O " ir iepriekš izskaidrotais Big Oh apzīmējums, savukārt " n " un " N " nozīmē ievades lielumu.
Biežāk uzdotie jautājumi
Q #1) Kas ir sort () Python valodā?
Atbilde: Python sort() ir funkcija, ko izmanto, lai sakārtotu sarakstus vai masīvus noteiktā secībā. Šī funkcija atvieglo šķirošanas procesu, strādājot pie lieliem projektiem. Tā ir ļoti noderīga izstrādātājiem.
2. jautājums) Kā jūs šķirojat Python programmā?
Atbilde: Python piedāvā dažādas šķirošanas metodes, kas tiek izmantotas elementu šķirošanai. Piemēram, Ātrā šķirošana, apvienošanas šķirošana, burbuļveida šķirošana, ievietošanas šķirošana u. c. Visas šķirošanas metodes ir efektīvas un viegli saprotamas.
Q #3) Kā darbojas Python sort ()?
Atbilde: Funkcija sort() no lietotāja kā ievadi ņem doto masīvu un sakārto to noteiktā secībā, izmantojot šķirošanas algoritmu. Algoritma izvēle ir atkarīga no lietotāja izvēles. Lietotāji var izmantot Quick sort, Merge sort, Bubble sort, Insertion sort utt. atkarībā no lietotāja vajadzībām.
Secinājums
Iepriekš minētajā pamācībā mēs aplūkojām šķirošanas paņēmienu Python valodā kopā ar vispārējiem šķirošanas paņēmieniem.
- Burbuļu šķirošana
- Ievietošanas šķirošana
- Ātrā šķirošana
Mēs uzzinājām par to laika sarežģītību un priekšrocībām & amp; trūkumiem. Mēs arī salīdzinājām visas iepriekš minētās metodes.