Jifunze jinsi ya kutumia chaguo la kukokotoa la Chatu kupanga orodha, safu, kamusi, n.k kwa kutumia mbinu mbalimbali za kupanga na algoriti katika Python:
Kupanga ni mbinu inayotumika kupanga. data kwa mpangilio wa mfuatano ama kwa mpangilio wa kupanda au kushuka.
Mara nyingi data ya miradi mikubwa haijapangwa kwa mpangilio sahihi na hii husababisha matatizo wakati wa kupata na kuleta data inayohitajika kwa ufanisi.
Mbinu za kupanga hutumiwa kutatua tatizo hili. Chatu hutoa mbinu mbalimbali za kupanga kwa mfano, kupanga viputo, Upangaji wa Uingizaji, Unganisha aina, Quicksort, n.k.
Katika somo hili, tutaelewa jinsi upangaji unavyofanya kazi katika Chatu kwa kutumia algoriti mbalimbali.
Aina ya Chatu
Sintaksia ya Aina ya Chatu
Ili kutekeleza kupanga, Python hutoa kitendakazi kilichojengewa ndani yaani kazi ya " sort() ". Inatumika kupanga vipengele vya data vya orodha kwa mpangilio wa kupanda au kushuka.
Hebu tuelewe dhana hii kwa mfano.
Mfano 1:
``` a = [ 3, 5, 2, 6, 7, 9, 8, 1, 4 ] a.sort() print( “ List in ascending order: ”, a ) ```
Pato:
Katika mfano huu, orodha iliyotolewa isiyopangwa imepangwa kwa mpangilio wa kupanda kwa kutumia kitendakazi cha “ sort( ) ”. .
Mfano 2:
``` a = [ 3, 5, 2, 6, 7, 9, 8, 1, 4 ] a.sort( reverse = True ) print( “ List in descending order: ”, a ) ```
Pato
Katika mfano ulio hapo juu, orodha iliyotolewa ambayo haijapangwa imepangwa kwa mpangilio wa kinyume kwa kutumia chaguo la kukokotoa “ sort( reverse = True ) .
Mudamahali Kupanga Bubble O(n) O(n2) O(n2) O(1) Ndiyo Ndiyo Aina ya Uingizaji O(n) O(n2) O(n2) O(1) Ndiyo Ndiyo Kupanga kwa haraka O(n logi(n)) O(n logi(n)) O(n2) O(N) Hapana Ndiyo Unganisha panga O(n logi(n)) O(n logi(n)) O(n logi(n)) 41>O(N) Ndiyo Hapana Aina ya lundo O(n logi (n)) O(n logi(n)) O(n logi(n)) O(1) Hapana O(1) Hapana Ndiyo
Katika jedwali la ulinganishi lililo hapo juu “ O “ ni nukuu ya Oh Kubwa iliyofafanuliwa hapo juu ambapo “ n ” na “ N ” inamaanisha ukubwa wa ingizo. .
Maswali Yanayoulizwa Mara Kwa Mara
Q #1) Ni aina gani () katika Chatu?
Jibu: Katika Chatu sort() ni chaguo la kukokotoa ambalo hutumika kupanga orodha au safu katika mpangilio maalum. Kitendaji hiki hurahisisha mchakato wa kupanga wakati wa kufanya kazi kwenye miradi mikubwa. Inafaa sana kwa wasanidi.
Q #2) Je, unapangaje katika Python?
Jibu: Chatu hutoa mbinu mbalimbali za kupanga ambazo hutumika kupanga kipengele. Kwa mfano, Upangaji wa haraka, Upangaji wa Kuunganisha, Upangaji wa Viputo, Upangaji wa Uwekaji, n.k. Mbinu zote za kupanga ni bora na rahisi kueleweka.
Q #3) Chatu hufanyaje aina () kazi?
Jibu: Aina()kipengele cha kukokotoa huchukua safu fulani kama ingizo kutoka kwa mtumiaji na kuipanga kwa mpangilio maalum kwa kutumia algoriti ya kupanga. Uchaguzi wa algorithm inategemea chaguo la mtumiaji. Watumiaji wanaweza kutumia upangaji wa Haraka, Upangaji wa Kuunganisha, Upangaji Viputo, Upangaji wa Kuweka, n.k kulingana na mahitaji ya mtumiaji.
Hitimisho
Katika mafunzo yaliyo hapo juu, tulijadili mbinu ya kupanga katika Chatu pamoja na mbinu za jumla za kupanga.
- Upangaji wa Viputo
- Panga Uingizaji
- Upangaji Haraka
Tulijifunza kuhusu matatizo na manufaa ya wakati wao & hasara. Pia tulilinganisha mbinu zote hapo juu.
Utata wa Kupanga AlgorithmsUtata wa Muda ni muda unaochukuliwa na kompyuta kutekeleza kanuni fulani. Ina aina tatu za matukio ya utata wa wakati.
- Hali Mbaya Zaidi: Muda wa juu zaidi unaochukuliwa na kompyuta kuendesha programu.
- Kesi ya Wastani: Muda unaochukuliwa kati ya kiwango cha chini kabisa na cha juu zaidi na kompyuta ili kuendesha programu.
- Kesi Bora Zaidi: Muda wa chini unaochukuliwa na kompyuta kuendesha programu. Ndiyo hali bora zaidi ya utata wa wakati.
Vidokezo vya Utata
Notesi ya Big Oh, O: Nukuu kubwa ndiyo njia rasmi ya kuwasilisha alama ya juu. wakati wa kuendesha algorithms. Inatumika kupima uchangamano wa wakati wa hali mbaya zaidi au tunasema muda mkubwa zaidi unaochukuliwa na algoriti kukamilisha.
Note ya omega kubwa, : Alama kubwa ya omega ni njia rasmi ya kufikisha kikomo cha chini kabisa cha wakati wa uendeshaji wa algorithms. Inatumika kupima uchangamano wa wakati wa kesi bora zaidi au tunasema muda bora zaidi unaochukuliwa na algoriti.
Notation ya Theta, : Note ya Theta ndiyo njia rasmi ya kuwasilisha. mipaka yote miwili, yaani, chini na juu zaidi ya muda uliochukuliwa na algoriti kukamilisha.
Mbinu za Kupanga katika Chatu
Upangaji Viputo
Kupanga viputo ndiyo njia rahisi zaidi ya kupanga data. ambayo hutumia mbinu ya nguvu ya kinyama. Itajirudia kwa kila kipengele cha data na kuilinganisha na vipengele vingineili kumpa mtumiaji data iliyopangwa.
Hebu tuchukue mfano ili kuelewa mbinu hii:
- Tumepewa safu yenye vipengele “ 10, 40, 7, 3, 15 ”. Sasa, tunahitaji kupanga safu hii kwa mpangilio wa kupanda kwa kutumia mbinu ya kupanga Bubble katika Python.
- Hatua ya kwanza kabisa ni kupanga safu katika mpangilio uliotolewa.
- Katika “Marudio 1”, tunalinganisha kipengele cha kwanza cha safu na vipengele vingine kimoja baada ya kingine.
- Vishale vyekundu vinaelezea ulinganisho wa vipengee vya kwanza na vipengee vingine vya safu.
- Ukiona “ 10 ” ni ndogo kuliko “ 40 ” kwa hivyo, itasalia sawa. mahali lakini kipengele kinachofuata " 7 " ni ndogo kuliko " 10 ". Kwa hivyo inabadilishwa na kuja mahali pa kwanza.
- Mchakato ulio hapo juu utafanywa tena na tena ili kupanga vipengele.
-
- Katika “ Iteration 2 ” kipengele cha pili kinalinganishwa na vipengele vingine vya safu.
- Ikiwa kipengele kilicholinganishwa ni kidogo basi, kitalinganishwa. ibadilishwe, vinginevyo itasalia mahali pale pale.
-
- Katika “ Iteration 3 “ kipengele cha tatu kinalinganishwa na vipengele vingine vya safu.
-
- Katika mwisho " Iteration 4 " kipengele cha pili cha mwisho kinalinganishwa na vipengele vingine vya safu.
- Katikahatua hii safu imepangwa kwa mpangilio wa kupanda.
Programu ya kupanga Maputo
``` 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)) ```
Pato
Utata wa Muda wa Kupanga Viputo
- Hali Mbaya Zaidi: Utata mbaya zaidi wa wakati wa kupanga viputo ni O( n 2).
- Kesi Wastani: Wastani wa uchangamano wa wakati wa kupanga viputo ni O( >n 2).
- Kisa Bora: Utata bora wa wakati wa kupanga viputo ni O(n).
Faida
- Inatumika zaidi na ni rahisi kutekelezwa.
- Tunaweza kubadilisha vipengele vya data bila matumizi ya hifadhi ya muda mfupi.
- Inahitaji kidogo zaidi. nafasi.
Hasara
- Haikufanya vizuri wakati wa kushughulikia idadi kubwa ya vipengele vya data.
- It inahitaji n hatua 2 kwa kila nambari ya "n" ya vipengele vya data ili kupangwa.
- Sio nzuri kabisa kwa programu za ulimwengu halisi.
Uingizaji Panga
Upangaji wa uwekaji ni mbinu rahisi na rahisi ya kupanga ambayo hufanya kazi sawa na kupanga kadi za kucheza. Uingizaji hupanga vipengele kwa kulinganisha kila kipengele kimoja baada ya kingine na kingine. Vipengele huchaguliwa na kubadilishana na kipengele kingine ikiwa kipengele ni kikubwa au kidogo kuliko kingine.
Hebu tuchukue mfano
- Tumepewa safu iliyo na vipengee " 100, 50, 30, 40, 10 ".
- Kwanza, tunapanga safu na kuanza kulinganisha.it.
- Katika hatua ya kwanza " 100 " inalinganishwa na kipengele cha pili " 50 ". “ 50 ” inabadilishwa na “ 100 ” kwa kuwa ni kubwa zaidi.
- Katika hatua ya pili, tena kipengele cha pili “ 100 ” kinalinganishwa na kipengele cha tatu “ 30 ” na kubadilishwa.
- Sasa, ukiona “ 30 ” inakuja mahali pa kwanza kwa sababu ni ndogo tena kuliko “ 50 ”.
- Ulinganisho utafanyika hadi kipengele cha mwisho cha safu na mwisho, tutapata data iliyopangwa.
Programu ya Upangaji wa Uingizaji
``` 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]) ```
Pato
Utata wa Muda wa Aina ya Uingizaji
- Hali Mbaya Zaidi: Utata mbaya zaidi wa aina ya Uingizaji ni O( n 2).
- Kesi Wastani: Wastani wa utata wa wakati wa kupanga Uingizaji ni O( n 2).
- Kesi Bora Zaidi: Utata bora wa wakati wa kupanga Uingizaji ni O(n).
Faida
- Ni rahisi na ni rahisi kutekelezwa.
- Inafanya kazi vyema huku ikishughulika na idadi ndogo ya vipengele vya data.
- Haihitaji nafasi zaidi kwa utekelezaji wake.
1>Hasara
- Haisaidii kupanga idadi kubwa ya vipengele vya data.
- Ikilinganishwa na mbinu nyingine za kupanga haifanyi vizuri.
- 16>
Unganisha aina
Njia hii ya kupanga hutumia mbinu ya kugawanya na kushinda ili kupanga vipengele kwa mpangilio maalum. Wakati wa kuchagua kwa usaidizi wa kuunganisha aina, thevipengele vinagawanywa katika nusu na kisha, hupangwa. Baada ya kupanga nusu zote, vipengele vinaunganishwa tena ili kuunda mpangilio kamili.
Hebu tuchukue mfano ili kuelewa mbinu hii
- Tumepewa safu "7, 3, 40, 10, 20, 15, 6, 5". Safu ina vipengele 7. Ikiwa tunaigawanya katika nusu ( 0 + 7 / 2 = 3 )
- Katika hatua ya pili, utaona kwamba vipengele vimegawanywa katika sehemu mbili. Kila moja ikiwa na vipengele 4 ndani yake.
- Zaidi ya hayo, vipengele vimegawanywa tena na vina vipengele 2 kila kimoja.
- Mchakato huu utaendelea hadi kipengele kimoja pekee kiwepo katika safu. Rejea hatua Na. 4 kwenye picha.
- Sasa, tutapanga vipengele na kuanza kuviunganisha jinsi tulivyogawanywa.
- Katika hatua Na. 5 ukiona 7 ni kubwa kuliko 3, kwa hivyo tutazibadilisha na kuziunganisha katika hatua inayofuata na kinyume chake.
- Mwishoni, utaona kwamba safu yetu inapangwa kwa mpangilio wa kupanda. 15>
Programu ya Kuunganisha aina
``` 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) ```
Pato
Utata wa Muda wa Kuunganisha
- Hali Mbaya Zaidi: Utata mbaya zaidi wa aina ya kuunganisha ni O( n log( n )).
- Kesi Wastani: Wastani wa uchangamano wa wakati wa kuunganisha ni O( n logi( n )).
- Kesi Bora: Utata bora wa wakati wa kuunganisha ni O( n log( n )).
Faida
- Ukubwa wa faili haijalishi kwa mbinu hii ya kupanga.
- Mbinu hii ni nzuri kwa data ambayo kwa ujumla hupatikana kwa mpangilio wa mfuatano. Kwa mfano, orodha zilizounganishwa, hifadhi ya tepe, n.k.
Hasara
- Inahitaji nafasi zaidi ikilinganishwa na nyinginezo. mbinu za kupanga.
- Ina ufanisi mdogo kwa kulinganisha kuliko zingine.
Upangaji wa haraka
Kupanga kwa haraka tena hutumia mbinu ya kugawa na kushinda kupanga vipengele vya Orodha. au safu. Inalenga vipengele egemeo na kupanga vipengele kulingana na kipengele egemeo kilichochaguliwa.
Kwa mfano
- Tumepewa safu yenye vipengele “ 1 ,8,3,9,4,5,7 ”.
- Hebu tuchukulie “ 7 ” kuwa kipengele cha majaribio.
- Sasa tutagawanya safu kwa namna ambayo upande wa kushoto una vipengele ambavyo ni vidogo kuliko kipengele cha egemeo " 7 " na upande wa kulia una vipengele vikubwa kuliko kipengele cha egemeo " 7 ".
- Sasa tuna safu mbili " 1,3,4,5 ” na “ 8, 9 ”.
- Tena, tunapaswa kugawanya safu zote mbili sawa na tulivyofanya hapo juu. Tofauti pekee ni kwamba vipengele egemeo hubadilishwa.
- Tunahitaji kugawanya safu hadi tupate kipengele kimoja katika mkusanyiko.
- Mwishoni, kusanya vipengele vyote vya egemeo katika safu moja. mlolongo kutoka kushoto kwenda kulia na utapata iliyopangwasafu.
Programu ya Kupanga Haraka
``` 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 ] ) ```
Pato
Utata wa Muda wa Upangaji Haraka
- Hali Mbaya Zaidi: Utata mbaya zaidi wa aina ya Haraka ni O( n 2).
- Kesi Wastani: Wastani wa utata wa wakati wa upangaji Haraka ni O( n logi( n ) ).
- Kisa Bora: Utata bora wa wakati wa kupanga Haraka ni O( n log( n )).
Faida
- Inajulikana kama algoriti bora zaidi ya kupanga katika Python.
- Inafaa wakati unashughulikia kiasi kikubwa cha data.
- Hahitaji nafasi ya ziada.
Hasara
- Utata wake wa hali mbaya zaidi ni sawa na ugumu wa upangaji wa viputo na aina ya uwekaji.
- Mbinu hii ya kupanga si muhimu wakati tayari tunayo orodha iliyopangwa.
Aina ya lundo
Kupanga kwa lundo ni toleo la juu zaidi la mti wa utafutaji wa binary. . Katika mpangilio wa lundo, kipengele kikubwa zaidi cha safu huwekwa kwenye mzizi wa mti kila mara na kisha, ikilinganishwa na mzizi na nodi za majani.
Kwa mfano:
- Tumepewa safu yenye vipengele “ 40, 100, 30, 50, 10 ”.
- Katika “ hatua ya 1 ” tulitengeneza mti kulingana na uwepo wa vipengele katika safu.
- Katika “ hatua ya 2 ” tunatengeneza rundo la juu zaidi yaani kupanga mpangilio vipengele katika utaratibu wa kushuka. kipengele kubwa mapenzikaa juu (mizizi) na kitu kidogo zaidi hukaa chini (nodi za majani). Safu iliyotolewa inakuwa “ 100, 50, 30, 40, 10 ”.
- Katika “ hatua ya 3 ” , sisi wanatengeneza rundo la chini zaidi ili tuweze kupata vipengele vya chini zaidi vya safu. Kwa kufanya hivi, tunapata vipengele vya juu zaidi na vya chini zaidi.
- Katika “ hatua ya 4 ” kwa kutekeleza hatua sawa. tunapata safu iliyopangwa.
Programu ya aina ya Lundo
``` 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 ] ) ```
Pato
Utata wa Muda wa Aina ya Lundo
- Hali Mbaya Zaidi: Utata mbaya zaidi wa aina ya Lundo ni O( n logi( n )).
- Kesi Wastani: Wastani wa utata wa aina ya Lundo ni O( n logi( n )).
- Kisa Bora: Utata bora wa wakati wa kupanga Lundo niO( n logi( n )).
Faida
- Inatumika zaidi kwa sababu ya uzalishaji wake.
- Inaweza. itekelezwe kama algoriti ya mahali.
- Haihitaji hifadhi kubwa.
Hasara
- Inahitaji nafasi kwa ajili ya kupanga vipengele.
- Hufanya mti kwa ajili ya kupanga vipengele.
Ulinganisho Kati ya Mbinu za Kupanga
Njia ya Kupanga Utata bora wa muda wa kesi Utata wa wastani wa muda Utata wa wakati wa kesi mbaya zaidi Utata wa nafasi Uthabiti Katika -