Gruntle Software & Testing

Urut Python: Métode Asihan sareng Algoritma Dina Python

Oleh Stewart TristianDiposting pada Diposting dalam Panungtun

Diajar kumaha ngagunakeun pungsi Python Sort pikeun nyortir daptar, arrays, kamus, jsb ngagunakeun rupa-rupa métode sortir jeung algoritma dina Python:

Sorting nyaéta téknik anu digunakeun pikeun nyortir. data dina runtuyan urutan boh dina urutan naek atawa turun.

Seueurna waktos data proyek ageung henteu disusun dina urutan anu leres sareng ieu nyiptakeun masalah nalika ngaksés sareng nyandak data anu diperyogikeun sacara éfisién.

Téknik pangurutan digunakeun pikeun ngaréngsékeun ieu masalah. Python nyadiakeun rupa-rupa téhnik asihan contona, Bubble sort, Insertion sort, Merge sort, Quicksort, jsb.

Dina tutorial ieu, urang bakal ngarti kumaha asihan dina Python ku ngagunakeun rupa-rupa algoritma.

Urut Python

Sintaksis Urut Python

Pikeun ngalaksanakeun asihan, Python nyayogikeun fungsi anu diwangun nyaéta fungsi "sort ()". Hal ieu dipaké pikeun milah-milah unsur-unsur data tina daptar dina urutan naek atawa dina urutan nurun.

Hayu urang ngartikeun ieu konsép ku conto.

Conto 1: 

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

Kaluaran:

Dina conto ieu, daptar unordered dibikeun diurutkeun kana urutan naek ku ngagunakeun fungsi " sort ( ) ". .

Conto 2: 

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

Kaluaran

Dina conto di luhur, daptar unordered dibikeun diurutkeun dina urutan sabalikna ngagunakeun fungsi " sort( reverse = True ) ".

Timetempat Gelembung sortir O(n) O(n2) O(n2) O(1) Leres Leres Nurutkeun sisipan O(n) O(n2) O(n2) O(1) Leres Leres Nurunkeun gancang O(n log(n)) O(n log(n)) O(n2) O(N) Henteu Leres Gabung diurutkeun O(n log(n)) O(n log(n)) O(n log(n)) O(N) Leres Henteu Numpuk Urut O(n log (n)) O(n log(n)) O(n log(n)) O(1) No Leres

Dina tabel babandingan di luhur “ O “ mangrupa notasi Oh Big dipedar di luhur sedengkeun “ n ” jeung “ N ” hartina ukuran input. .

Patarosan anu Sering Ditanya

Q #1) Naon ari sort () dina Python?

Jawaban: Dina Python sort () nyaéta fungsi anu dipaké pikeun nyortir daptar atawa arrays dina urutan husus. Pungsi ieu ngagampangkeun prosés asihan nalika damel dina proyék-proyék ageung. Ieu pohara mantuan pikeun pamekar.

P #2) Kumaha anjeun nyortir dina Python?

Jawaban: Python nyadiakeun rupa-rupa téhnik asihan nu dipaké pikeun nyortir unsur. Contona, Urut gancang, Urut Gabung, Urut Gelembung, Urut sisipan, jsb. Sadaya téknik asihan éfisién sareng gampang kaharti.

P #3) Kumaha Python diurutkeun () gawé?

Jawaban: The sort()fungsi nyokot Asép Sunandar Sunarya dibikeun salaku input ti pamaké sarta sorts eta dina urutan husus ngagunakeun algoritma asihan. Pilihan algoritma gumantung kana pilihan pamaké. Pamaké bisa maké Quick sort, Merge sort, Bubble sort, Insertion sort, jsb gumantung kana pangabutuh pamaké.

Kacindekan

Dina tutorial di luhur, urang ngabahas téknik sortir dina Python babarengan jeung téhnik asihan umum.

  • Bubble Sort
  • Insertion Sort
  • Gancang Urut

Urang diajar ngeunaan complexities waktu maranéhanana jeung kaunggulan & amp; kalemahan. Urang ogé ngabandingkeun sakabéh téhnik di luhur.

Kompleksitas Algoritma Asihan

Waktu Kompleksitas nyaéta jumlah waktu nu diperlukeun komputer pikeun ngajalankeun hiji algoritma nu tangtu. Éta ngagaduhan tilu jinis kasus pajeulitna waktos.

  • Kasus Parantos: Waktos maksimal anu dicandak ku komputer pikeun ngajalankeun program.
  • Kasus Rata-rata: Waktu nu diperlukeun antara minimum jeung maksimum ku komputer pikeun ngajalankeun program.
  • Kasus Pangalusna: Waktu minimum nu diperlukeun komputer pikeun ngajalankeun program. Ieu mangrupikeun kasus pajeulitna waktos anu paling saé.

Notasi Kompleksitas

Notasi Oh Big, O: Notasi oh badag nyaéta cara resmi pikeun nepikeun wates luhur. waktos ngajalankeun algoritma. Hal ieu dipaké pikeun ngukur pajeulitna waktu-kasus awon atawa urang nyebutkeun jumlah pangbadagna waktu nu dicokot ku algoritma pikeun réngsé.

Notasi omega badag, : Notasi omega badag nyaéta cara resmi pikeun nepikeun wates panghandapna tina waktu ngajalankeun sahiji algoritma. Hal ieu dipaké pikeun ngukur pajeulitna waktu kasus pangalusna atawa urang nyebutkeun jumlah alus teuing waktu nu dicokot ku algoritma.

Notasi Theta, : Notasi Theta mangrupa cara resmi pikeun nepikeun duanana wates nyaéta handap jeung luhur waktu nu dicokot ku algoritma pikeun ngalengkepan.

Métode Asihan dina Python

Bubble Sort

Bubble sort nyaéta cara pangbasajanna pikeun nyortir data. anu ngagunakeun téhnik brute force. Bakal iterate ka unggal unsur data tur dibandingkeun jeung elemen séjénpikeun nyayogikeun data anu diurutkeun ka pangguna.

Cu we nyandak conto pikeun ngartos téknik ieu:

  • Kami disayogikeun ku susunan anu gaduh unsur " 10, 40, 7, 3, 15 ". Ayeuna, urang kedah ngatur Asép Sunandar Sunarya ieu dina urutan naek ngagunakeun téhnik Bubble sort dina Python.
    • Léngkah anu pangheulana nyaéta nyusun susunan dina urutan anu dipasihkeun.
    • Dina " Iterasi 1 ", urang ngabandingkeun unsur mimiti hiji array sareng elemen séjén hiji-hiji.
    • Panah beureum ngajéntrékeun babandingan unsur-unsur kahiji jeung unsur-unsur séjénna dina hiji array.
    • Upami anjeun merhatikeun “ 10 ” leuwih leutik batan “ 40 ”, éta tetep sarua. tempat tapi unsur salajengna "7" leuwih leutik batan "10". Ku kituna eta bakal diganti tur datang ka tempat munggaran.
    • Proses di luhur bakal dipigawé deui jeung deui pikeun nyortir unsur.

    • Dina " Iterasi 2 " unsur kadua dibandingkeun jeung elemen séjén tina hiji array.
    • Lamun elemen dibandingkeun leutik mangka, éta bakal meunang diganti, disebutkeun eta bakal tetep di tempat nu sarua.

    • Dina " Iteration 3 " unsur katilu meunang dibandingkeun jeung elemen séjén tina array.

    • Dina panungtungan " Iteration 4 " elemen panungtungan kadua lalaki dibandingkeun jeung elemen séjén tina hiji array.
    • Dinalengkah ieu array diurutkeun dina urutan naek.

Program pikeun Bubble sort 

``` 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)) ```

Kaluaran

Kompleksitas Waktos diurutkeun Gelembung

  • Kasus Parantos: Pajeulitna waktu nu paling awon pikeun sortir gelembung nyaéta O( n 2).
  • Kasus Rata-rata: Pajeulitna waktu rata-rata pikeun sortir gelembung nyaéta O( n 2).
  • Kasus Pangalusna: Pajeulitna waktos pangsaéna pikeun sortir gelembung nyaéta O(n).

Kauntungan

  • Seuseueurna dianggo sareng gampang diimplementasikeun.
  • Urang tiasa ngagentos unsur data tanpa nganggo neundeun jangka pondok.
  • Peryogikeun sakedik. spasi.

Kalemahan

  • Henteu kinerjana alus bari nungkulan sajumlah badag elemen data badag.
  • Éta peryogi n 2 léngkah pikeun tiap "n" jumlah elemen data pikeun diurutkeun.
  • Éta henteu saé pikeun aplikasi dunya nyata.

Selapkeun. Sort

Insertion sort mangrupikeun téknik asihan anu gampang sareng saderhana anu tiasa dianggo sami sareng nyortir kartu maén. Insertion sort sorts elemen ku ngabandingkeun unggal unsur hiji-hiji jeung lianna. Unsur-unsurna dipulut sareng diganti ku unsur anu sanés upami unsurna langkung ageung atanapi langkung alit tibatan unsur anu sanés.

Coba urang conto

  • Urang disadiakeun Asép Sunandar Sunarya ngabogaan elemen " 100, 50, 30, 40, 10 ".
  • Kahiji, urang ngatur Asép Sunandar Sunarya tur mimitian ngabandingkeuneta.
  • Dina lengkah kahiji “ 100 ” dibandingkeun jeung unsur kadua “ 50 ”. “ 50 ” diganti ku “ 100 ” sabab leuwih gede.
  • Dina lengkah kadua, unsur kadua “ 100 ” dibandingkeun jeung unsur katilu “ 30 ” sarta diganti.
  • Ayeuna, lamun aya bewara " 30 " datang ka tempat munggaran sabab deui leuwih leutik batan " 50 ".
  • Bandingan bakal lumangsung nepi ka unsur panungtungan hiji Asép Sunandar Sunarya jeung di ahir, urang bakal meunang data diurutkeun.

Program pikeun nyortir sisipan 

``` 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]) ```

Kaluaran

Pajeulitna Waktos Urut Selapkeun

  • Kasus Parantos: Pajeulitna waktos Panyelapkeun Urut nyaeta O( n 2).
  • Rata-rata Kasus: Rata-rata pajeulitna waktos kanggo Insertion sort nyaeta O( n 2).
  • Kasus Pangalusna: Pajeulitna waktos pangsaéna pikeun Insertion sort nyaéta O(n).

Kauntungan

  • Saderhana. sarta gampang diimplementasikeun.
  • Ieu kinerjana alus bari nungkulan sajumlah leutik elemen data.
  • Teu merlukeun leuwih spasi pikeun palaksanaan na.

Kakurangan

  • Henteu aya mangpaatna pikeun nyortir sajumlah ageung elemen data.
  • Upami dibandingkeun sareng téknik pangurutan anu sanés, éta henteu saé.

Gabungkeun sortir

Ieu métode asihan ngagunakeun métode divide and conquer pikeun nyortir unsur-unsur dina urutan nu tangtu. Bari asihan kalayan bantuan merge sort, nuelemen dibagi kana halves lajeng, aranjeunna neangan diurutkeun. Sanggeus milah-milah sakabeh bagian, deui unsur-unsurna dihijikeun pikeun ngabentuk susunan anu sampurna.

Cu we cokot conto pikeun ngarti kana téknik ieu

  • Urang disadiakeun kalawan hiji Asép Sunandar Sunarya "7, 3, 40, 10, 20, 15, 6, 5". Asép Sunandar Sunarya ngandung 7 unsur. Lamun urang bagikeun kana satengah ( 0 + 7 / 2 = 3 ).
  • Dina lengkah kadua, anjeun bakal nempo yén unsur dibagi jadi dua bagian. Masing-masing aya 4 unsur.
  • Salajengna, unsur-unsurna dibagi deui sareng masing-masing gaduh 2 unsur.
  • Proses ieu bakal diteruskeun dugi ka ngan hiji unsur anu aya dina array. Rujuk kana léngkah no. 4 dina gambar.
  • Ayeuna, urang bakal nyortir unsur-unsur sareng mimitian ngagabung nalika urang dibagi.
  • Dina léngkah No. 5 upami anjeun perhatikeun 7 langkung ageung tibatan 3, janten urang bakal tukeur aranjeunna sareng gabungkeun kana lengkah salajengna sareng sabalikna.
  • Ahirna, anjeun bakal perhatikeun yén array kami diurutkeun dina urutan naek.

Program pikeun Ngagabung Urut 

``` 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) ```

Kaluaran

Kompleksitas Waktos Susunan Gabung

  • Kasus Parantos: Kompleksitas waktos anu paling awon pikeun diurutkeun gabungan nyaéta O( n log( n )).
  • Rata-rata Kasus: Rata-rata pajeulitna waktu pikeun diurutkeun gabungan nyaéta O( n log( n )).
  • Kasus Pangalusna: Pajeulitna waktos anu pangsaéna pikeun diurutkeun gabungan nyaéta O( n log( n )).

Kauntungan

  • Ukuran file henteu masalah pikeun téknik asihan ieu.
  • Téknik ieu hadé pikeun data anu umumna diaksés dina urutan. Contona, daptar numbu, tape drive, jsb.

Kakurangan

  • Meryogikeun langkung seueur rohangan upami dibandingkeun sareng anu sanés. Téhnik pangurutan.
  • Éta rélatif kurang éfisiénna tibatan batur.

Urut gancang

Urutan gancang deui ngagunakeun métode divide and conquer pikeun nyortir unsur-unsur Daptar. atawa Asép Sunandar Sunarya. Éta nargétkeun unsur pangsi sareng nyortir unsur-unsur dumasar kana unsur pangsi anu dipilih.

Contona

  • Kami disayogikeun ku susunan anu gaduh unsur " 1 ,8,3,9,4,5,7 ".
  • Anggap "7" janten elemen pilot.
  • Ayeuna urang ngabagi array dina cara sapertos nu sisi kénca ngandung elemen anu leuwih leutik batan elemen pangsi " 7 " sarta sisi katuhu ngandung elemen leuwih badag batan elemen pangsi " 7 ".
  • Urang ayeuna boga dua arrays " 1,3,4,5 "Jeung " 8, 9 ".
  • Sakali deui, urang kudu ngabagi duanana arrays sagampil sarua jeung di luhur. Hiji-hijina bédana nyaéta yén elemen pangsi robah.
  • Urang kudu ngabagi susunan nepi ka meunang hiji unsur dina array.
  • Di ahir, kumpulkeun sakabeh elemen pangsi dina hiji urutan ti kénca ka katuhu jeung anjeun bakal meunang nu diurutkeunarray.

Program pikeun Urut Gancang 

``` 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 ] ) ```

Kaluaran

Kompleksitas Waktos diurutkeun Gancang

  • Kasus awon: Kompleksitas waktos anu paling awon pikeun Urut Gancang nyaéta O( n 2).
  • Rata-rata Kasus: Rata-rata kompleksitas waktu pikeun Quick sort nyaéta O( n log( n ) ).
  • Kasus Pangalusna: Pajeulitna waktos pangsaéna pikeun Quick sort nyaéta O( n log( n )).

Kauntungan

  • Kawanoh salaku algoritma pangurutan pangalusna dina Python.
  • Éta mangpaat nalika nanganan data anu ageung.
  • Henteu meryogikeun rohangan tambahan.

Kalemahan

  • Pajeulitna kasus anu paling parah sami sareng pajeulitna gelembung sortir sareng insertion sort.
  • Metode asihan ieu henteu kapaké lamun urang geus boga daptar nu diurutkeun.

Heap sort

Heap sort nyaéta vérsi canggih tina tangkal panéangan binér . Dina heap sort, unsur pangageungna tina susunan disimpen dina akar tangkal salawasna lajeng, dibandingkeun jeung akar jeung titik daun.

Contona:

  • Kami disayogikeun susunan anu gaduh elemen " 40, 100, 30, 50, 10 ".
  • Dina " lengkah 1 " kami ngadamel tangkal dumasar kana ayana elemen dina Asép Sunandar Sunarya.

  • Dina " lengkah 2 " urang nyieun tumpukan maksimum nyaéta pikeun ngatur elemen dina urutan nurun. Unsur greatest bakalreside di luhur (akar) jeung unsur pangleutikna resides di handap (daun titik). Array anu dipasihkeun janten " 100, 50, 30, 40, 10 ".

  • Dina " lengkah 3 " , urang nuju nyieun numpuk minimum ku kituna urang bisa manggihan elemen minimum hiji Asép Sunandar Sunarya. Ku ngalakukeun ieu, urang meunang elemen maksimum jeung minimum.

  • Dina “ lengkah 4 ” ku ngalakukeun léngkah nu sarua. urang meunang array nu diurutkeun.

Program pikeun Heap sort 

``` 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 ] ) ```

Kaluaran

Kompleksitas Waktos Urut Timbunan

  • Kasus Parantos: Kompleksitas waktos anu paling parah pikeun Urut Timbunan nyaéta O( n log( n )).
  • Rata-rata Kasus: Rata-rata kompleksitas waktu keur Heap sort nyaéta O( n log( n )).
  • Kasus Pangalusna: Pajeulitna waktu pangalusna pikeun Heap sort isO( n log( n )).

Kauntungan

  • Seueurna dianggo kusabab produktivitasna.
  • Bisa diimplementasikeun salaku algoritma di tempat.
  • Henteu meryogikeun panyimpenan anu ageung.

Kalemahan

  • Peryogi rohangan pikeun milah-milah unsur-unsurna.
  • Ngajadikeun tangkal pikeun milah-milah unsur-unsurna.

Perbandingan Antara Téhnik Asihan

Metode Asihan Pajeulitna waktos kasus pangalusna Pajeulitna waktos kasus rata-rata Pajeulitna waktos kasus awon Pajeulitna spasi Stabilitas Dina -
Gulir ke atas