Gruntle Software & Testing

Python Saralash: Pythonda tartiblash usullari va algoritmlari

Tarafidan Stewart TristianYozilgan sana Yozilgan joy Qo'llanmalar

Python-da turli xil tartiblash usullari va algoritmlaridan foydalangan holda ro'yxatlar, massivlar, lug'atlar va hokazolarni saralash uchun Python Sort funksiyasidan qanday foydalanishni o'rganing:

Tartiblash - tartiblash uchun ishlatiladigan texnikadir. ma'lumotlar ketma-ketlikda o'sish yoki kamayish tartibida.

Ko'pincha yirik loyihalarning ma'lumotlari to'g'ri tartibda joylashtirilmaydi va bu kerakli ma'lumotlarga samarali kirish va olishda muammolarni keltirib chiqaradi.

Ushbu muammoni hal qilish uchun saralash usullari qo'llaniladi. Python turli xil saralash usullarini taqdim etadi masalan, Bubble sort, Insertion sort, Merge sort, Quicksort, va hokazo.

Ushbu qo'llanmada biz Python-da turli xil algoritmlardan foydalangan holda tartiblash qanday ishlashini tushunamiz.

Python Saralash

Python Saralash sintaksisi

Saralashni amalga oshirish uchun Python o‘rnatilgan funksiyani, ya’ni “sort()” funksiyasini taqdim etadi. U roʻyxatning maʼlumotlar elementlarini oʻsish yoki kamayish tartibida saralash uchun ishlatiladi.

Ushbu tushunchani misol bilan tushunib olaylik.

1-misol: 

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

Chiqish:

Ushbu misolda berilgan tartibsiz roʻyxat “sort( )” funksiyasi yordamida oʻsish tartibida tartiblangan. .

2-misol: 

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

Chiqish

Yuqoridagi misolda, berilgan tartibsiz roʻyxat “sort( reverse = True )” funksiyasi yordamida teskari tartibda tartiblanadi.

Vaqtjoy Koʻpikli tartiblash O(n) O(n2) O(n2) O(1) Ha Ha Qoʻshish tartibi O(n) O(n2) O(n2) O(1) Ha Ha Tez tartiblash O(n log(n)) O(n log(n)) O(n2) O(N) Yo'q Ha Birlashtirish sort O(n log(n)) O(n log(n)) O(n log(n)) O(N) Ha Yoʻq Uyma tartiblash O(n log) (n)) O(n log(n)) O(n log(n)) O(1) Yo'q 42> Ha

Yuqoridagi taqqoslash jadvalidagi “O” yuqorida tushuntirilgan Big Oh belgisi, “n” va “N” esa kirish hajmini bildiradi. .

Tez-tez so'raladigan savollar

Savol №1) Pythonda sort () nima?

Javob: Pythonda sort() - bu ro'yxatlar yoki massivlarni ma'lum bir tartibda saralash uchun ishlatiladigan funktsiya. Bu funksiya yirik loyihalar ustida ishlashda saralash jarayonini osonlashtiradi. Bu ishlab chiquvchilar uchun juda foydali.

2-savol) Pythonda qanday tartiblash mumkin?

Javob: Python elementni saralash uchun ishlatiladigan turli xil saralash usullarini taqdim etadi. Masalan, Tez tartiblash, Birlashtirish tartibi, Pufakchali tartiblash, Qo'shish tartibi va boshqalar. Barcha tartiblash usullari samarali va tushunarli.

№3-savol) Python qanday ishlaydi sort () ish?

Javob: Sort()funktsiya berilgan massivni foydalanuvchidan kirish sifatida oladi va saralash algoritmi yordamida ma'lum bir tartibda saralaydi. Algoritmni tanlash foydalanuvchining xohishiga bog'liq. Foydalanuvchilar foydalanuvchi ehtiyojlariga qarab Tez tartiblash, Birlashtirish saralash, Pufakcha tartiblash, Qo‘shish tartibi va h.k.lardan foydalanishi mumkin.

Xulosa

Yuqoridagi qo‘llanmada biz Python tilidagi tartiblash texnikasini muhokama qildik. umumiy saralash texnikasi.

  • Ko'pikli saralash
  • Qo'shishni saralash
  • Tezkor saralash

Ularning vaqt murakkabligi va afzalliklari haqida & kamchiliklari. Biz yuqoridagi barcha texnikalarni ham solishtirdik.

Saralash algoritmlarining murakkabligi

Vaqt Murakkabligi - bu ma'lum bir algoritmni bajarish uchun kompyuter tomonidan sarflangan vaqt. Unda uch xil vaqt murakkabligi holatlari mavjud.

  • Eng yomon holat: Kompyuter tomonidan dasturni ishga tushirish uchun sarflangan maksimal vaqt.
  • Oʻrtacha holat: Dasturni ishga tushirish uchun kompyuter tomonidan minimal va maksimal vaqt oralig'ida olingan vaqt.
  • Eng yaxshi holat: Dasturni ishga tushirish uchun kompyuter tomonidan minimal vaqt. Bu vaqt murakkabligining eng yaxshi holati.

Murakkablik belgilari

Big Oh notation, O: Big oh notation - bu yuqori chegarani uzatishning rasmiy usuli algoritmlarning ishlash vaqti. U eng yomon vaqt murakkabligini o'lchash uchun ishlatiladi yoki biz algoritm tomonidan bajarish uchun eng katta vaqtni aytamiz.

Big omega Notation, : Katta omega notation - bu algoritmlarning ishlash vaqtining eng past chegarasini etkazishning rasmiy usuli. U eng yaxshi vaqt murakkabligini o'lchash uchun ishlatiladi yoki biz algoritm tomonidan olingan ajoyib vaqt miqdorini aytamiz.

Theta Notation, : Teta notation - bu etkazishning rasmiy usuli ikkala chegara, ya'ni algoritm tomonidan bajarish uchun zarur bo'lgan vaqtning pastki va yuqori qismi.

Python'da saralash usullari

Bubble Sort

Bubble sort - ma'lumotlarni saralashning eng oddiy usuli bu qo'pol kuch texnikasidan foydalanadi. U har bir ma'lumot elementini takrorlaydi va uni boshqa elementlar bilan taqqoslaydifoydalanuvchini tartiblangan ma'lumotlar bilan ta'minlash uchun.

Ushbu texnikani tushunish uchun misol keltiramiz:

  • Bizga "elementlarga ega massiv taqdim etilgan. 10, 40, 7, 3, 15 ”. Endi biz Python-da Bubble sort texnikasidan foydalangan holda ushbu massivni o'sish tartibida tartibga solishimiz kerak.
    • Birinchi qadam massivni berilgan tartibda joylashtirishdir.
    • “ Takrorlash 1 ” da biz massivning birinchi elementini boshqa elementlar bilan birma-bir solishtiramiz.
    • Qizil strelkalar birinchi elementlarni massivning boshqa elementlari bilan solishtirishni tasvirlaydi.
    • Agar “10” “40” dan kichikroq ekanligini sezsangiz, u oʻzgarishsiz qoladi. joy, lekin keyingi “7” elementi “10” dan kichikroq. Shuning uchun u almashtiriladi va birinchi o'ringa chiqadi.
    • Elementlarni saralash uchun yuqoridagi jarayon qayta-qayta bajariladi.

    • “Iteratsiya 2” da ikkinchi element massivning boshqa elementlari bilan taqqoslanadi.
    • Agar solishtirilgan element kichik boʻlsa, u shunday boʻladi. almashtiring, aks holda u o'sha joyda qoladi.

    • " Takrorlash 3 "da uchinchi element massivning boshqa elementlari bilan taqqoslanadi.

    • Oxirgi element “Iteratsiya 4” ikkinchi oxirgi element massivning boshqa elementlari bilan taqqoslanadi.
    • Inbu bosqichda massiv o'sish tartibida tartiblanadi.

Bubble sort uchun dastur 

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

Chiqish

Bubble sortining vaqt murakkabligi

  • Eng yomon holat: Pufakchani saralash uchun eng yomon vaqt murakkabligi O( n 2).
  • Oʻrtacha holat: Pufakchani saralash uchun oʻrtacha vaqt murakkabligi O(4)>n 2).
  • Eng yaxshi holat: Pufakchani saralash uchun eng yaxshi vaqt murakkabligi O(n).

Afzalliklar

  • U asosan ishlatiladi va amalga oshirish oson.
  • Biz maʼlumotlar elementlarini qisqa muddatli saqlashni sarflamasdan almashtira olamiz.
  • U kamroq vaqt talab etadi. bo'sh joy.

Kamchiliklari

  • Ko'p sonli katta ma'lumotlar elementlari bilan ishlashda u yaxshi ishlamadi.
  • Bu Saralash uchun har bir “n” sonli ma’lumotlar elementi uchun n 2 qadam kerak.
  • Bu haqiqiy ilovalar uchun yaxshi emas.

Kiritish Saralash

Qo'shish tartibi - bu o'yin kartalarini saralashga o'xshash ishlaydigan oson va oddiy tartiblash usuli. Qo'shish tartibi har bir elementni bir-biri bilan taqqoslash orqali elementlarni tartiblaydi. Agar element boshqasidan katta yoki kichik bo'lsa, elementlar tanlanadi va boshqa element bilan almashtiriladi.

Keling, misol keltiraylik

  • Bizga taqdim etilgan “ 100, 50, 30, 40, 10” elementlariga ega massiv.
  • Birinchi navbatda, massivni tartibga solamiz va taqqoslashni boshlaymiz.u.
  • Birinchi bosqichda “ 100 ” ikkinchi element “ 50 ” bilan taqqoslanadi. “ 50 ” katta bo'lgani uchun “ 100 ” bilan almashtiriladi.
  • Ikkinchi bosqichda yana ikkinchi “ 100 ” elementi uchinchi “ 30 ” elementi bilan taqqoslanadi va almashtiriladi.
  • Endi, agar siz e'tibor bergan bo'lsangiz, "30" birinchi o'rinda turadi, chunki u yana "50" dan kichikroq.
  • Taqqoslash massivning oxirgi elementigacha amalga oshiriladi va oxirida biz quyidagini olamiz tartiblangan ma'lumotlar.

Qo'shish uchun dastur tartiblash 

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

Chiqish

Qo'shish vaqtini saralashning murakkabligi

  • Eng yomon holat: Qo'shishni tartiblash uchun eng yomon vaqt murakkabligi O( n 2).
  • Oʻrtacha holat: Qoʻshish tartibi uchun oʻrtacha vaqt murakkabligi O( n 2).
  • Eng yaxshi holat: Qo'shishni tartiblash uchun eng yaxshi vaqt murakkabligi O(n).

Afzalliklar

  • Bu oddiy va amalga oshirish oson.
  • Kichik miqdordagi ma'lumotlar elementlari bilan ishlashda u yaxshi ishlaydi.
  • Uni amalga oshirish uchun ko'proq joy kerak emas.

Kamchiliklari

  • Ko'p sonli ma'lumotlar elementlarini saralash foydali emas.
  • Boshqa tartiblash usullari bilan solishtirganda u yaxshi ishlamaydi.

Birlashtirish tartiblash

Ushbu tartiblash usuli elementlarni maʼlum tartibda saralash uchun boʻlish va zabt etish usulidan foydalanadi. Birlashtirish yordamida saralashda, theelementlar ikkiga bo'linadi va keyin tartiblanadi. Barcha yarmini saralagandan so'ng, elementlar yana mukammal tartibni hosil qilish uchun birlashtiriladi.

Ushbu texnikani tushunish uchun misol keltiramiz

  • Bizga taqdim etilgan. "7, 3, 40, 10, 20, 15, 6, 5" massivi. Massiv 7 ta elementdan iborat. Agar uni yarmiga bo'ladigan bo'lsak ( 0 + 7 / 2 = 3 ).
  • Ikkinchi bosqichda siz elementlar ikki qismga bo'linganligini ko'rasiz. Har birida 4 ta element mavjud.
  • Bundan tashqari, elementlar yana bo'linadi va har biri 2 ta elementga ega.
  • Bu jarayon massivda faqat bitta element mavjud bo'lmaguncha davom etadi. № qadamga qarang. Rasmdagi 4.
  • Endi biz elementlarni saralaymiz va ularni bo'lingandek birlashtira boshlaymiz.
  • №-bosqichda. 5 ga e'tibor bersangiz, 7 3 dan katta bo'lsa, biz ularni almashtiramiz va uni keyingi bosqichda qo'shamiz va aksincha.
  • Oxirida siz bizning massivimiz o'sish tartibida saralanayotganini sezasiz.

Birlashtirish uchun dastur 

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

Chiqish

Birlashtirishning vaqt murakkabligi

  • Eng yomon holat: Birlashtirishning eng yomon vaqt murakkabligi O( n) 5> log( n )).
  • Oʻrtacha holat: Birlashtirish uchun oʻrtacha vaqt murakkabligi O( n log(4)>n ).
  • Eng yaxshi holat: Birlashtirish uchun eng yaxshi vaqt murakkabligi O( n ).log( n )).

Afzalliklar

  • Bu tartiblash texnikasi uchun fayl hajmi muhim emas.
  • Ushbu usul odatda ketma-ketlikda foydalaniladigan ma'lumotlar uchun yaxshi. Masalan, bog'langan ro'yxatlar, lenta drayveri va boshqalar.

Kamchiliklari

  • Boshqalari bilan solishtirganda ko'proq joy talab qiladi. saralash texnikasi.
  • U boshqalarga qaraganda unchalik samarali emas.

Tez tartiblash

Tez tartiblash yana roʻyxat elementlarini saralash uchun boʻlish va zabt etish usulidan foydalanadi. yoki massiv. U pivot elementlarini nishonga oladi va elementlarni tanlangan pivot elementiga qarab tartiblaydi.

Masalan

  • Bizga “ 1” elementlariga ega massiv taqdim etilgan. ,8,3,9,4,5,7 ”.
  • “ 7 ” ni uchuvchi element deb faraz qilaylik.
  • Endi massivni shunday ajratamizki, chap tomonda “ 7 ” burilish elementidan kichikroq elementlar, o‘ng tomonda esa “ 7 ” aylanish elementidan kattaroq elementlar mavjud.
  • Hozir bizda ikkita massiv bor “ 1,3,4,5” ” va “ 8, 9 ”.
  • Yana, biz ikkala massivni ham xuddi yuqoridagidek ajratishimiz kerak. Yagona farq shundaki, pivot elementlari o'zgaradi.
  • Biz massivdagi bitta elementni olmagunimizcha massivlarni bo'lishimiz kerak.
  • Oxirida barcha pivot elementlarini to'plang. chapdan o'ngga ketma-ketlik va tartibni olasizmassiv.

Tezkor saralash dasturi 

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

Chiqish

Tez tartiblashning vaqt murakkabligi

  • Eng yomon holat: Tezkor saralash uchun eng yomon vaqt murakkabligi O(4)>n 2).
  • Oʻrtacha holat: Tez tartiblash uchun oʻrtacha vaqt murakkabligi O( n log( n ) ).
  • Eng yaxshi holat: Tez tartiblash uchun eng yaxshi vaqt murakkabligi O( n log( n )).

Afzalliklar

  • Bu Python-da eng yaxshi tartiblash algoritmi sifatida tanilgan.
  • U katta hajmdagi ma'lumotlarni qayta ishlashda foydalidir.
  • U qo'shimcha joyni talab qilmaydi.

Kamchiliklari

  • Uning eng yomon murakkabligi pufakchalarni tartiblash va qo'shishni saralash.
  • Ushbu tartiblash usuli bizda tartiblangan ro'yxat allaqachon mavjud bo'lsa foydali emas.

Uyma tartiblash

Uyma tartiblash - Ikkilik qidiruv daraxtining kengaytirilgan versiyasi . Uyumli tartiblashda massivning eng katta elementi har doim daraxt ildiziga joylashtiriladi va barg tugunlari bilan ildiz bilan solishtiriladi.

Masalan:

  • Bizga “ 40, 100, 30, 50, 10 ” elementlariga ega massiv taqdim etilgan.
  • “ 1-bosqich ” da biz ga muvofiq daraxt yasadik. massivdagi elementlarning mavjudligi.

  • “ 2-bosqich ” da biz maksimal toʻp hosil qilamiz, yaʼni tartibga solish uchun. elementlar kamayish tartibida. Eng katta element bo'laditepada (ildiz) va eng kichik element pastki qismida (barg tugunlari) joylashgan. Berilgan massiv “ 100, 50, 30, 40, 10” ga aylanadi.

  • “ 3-bosqichda ” , biz massivning minimal elementlarini topishimiz uchun minimal to'p hosil qilmoqdamiz. Shunday qilib, biz maksimal va minimal elementlarni olamiz.

  • “ 4-bosqich ” da bir xil amallarni bajarib. tartiblangan massivni olamiz.

Uyma tartiblash dasturi 

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

Chiqish

Uyma tartiblashning vaqt murakkabligi

  • Eng yomon holat: Uyma tartiblash uchun eng yomon vaqt murakkabligi O( n log( n )).
  • Oʻrtacha holat: Uyma tartiblash uchun oʻrtacha vaqt murakkabligi O( n) log( n )).
  • Eng yaxshi holat: Uyma tartiblash uchun eng yaxshi vaqt murakkabligi O( n log(4)>n )).

Afzalliklari

  • U asosan unumdorligi tufayli ishlatiladi.
  • U mumkin joyida algoritm sifatida amalga oshirilishi mumkin.
  • U katta hajmli saqlashni talab qilmaydi.

Kamchiliklari

  • Bosh joy kerak. elementlarni saralash.
  • Elementlarni saralash uchun daraxt yaratadi.

Saralash usullari o'rtasidagi taqqoslash

Saralash usuli Eng yaxshi holat vaqtining murakkabligi O'rtacha ish vaqtining murakkabligi Eng yomon holat vaqtining murakkabligi Kosmik murakkabligi Barqarorlik In -
Yuqoriga o'tish