Научете како да ја користите функцијата Python Sort за сортирање списоци, низи, речници итн. користејќи различни методи и алгоритми за сортирање во Python:
Сортирањето е техника што се користи за сортирање податоците по редослед или по растечки или опаѓачки редослед.
Поголемиот дел од времето податоците на големите проекти не се подредени во правилен редослед и тоа создава проблеми при ефикасно пристапување и преземање на потребните податоци.
Се користат техники за сортирање за да се реши овој проблем. Python обезбедува различни техники за сортирање на пример, Сортирање со меурчиња, Сортирање со вметнување, Сортирање со спојување, Брзо сортирање итн.
Во ова упатство, ќе разбереме како функционира сортирањето во Пајтон со користење на различни алгоритми.
Пајтон сортирање
Синтакса на сортирање на Пајтон
За да се изврши сортирање, Python ја обезбедува вградената функција, односно функцијата „сорт()“. Се користи за подредување на податочните елементи на списокот во растечки редослед или во опаѓачки редослед.
Ајде да го разбереме овој концепт со пример.
Пример 1:
``` a = [ 3, 5, 2, 6, 7, 9, 8, 1, 4 ] a.sort() print( “ List in ascending order: ”, a ) ```
Излез:
Во овој пример, дадената неподредена листа е подредена во растечки редослед со користење на функцијата „ sort( )“ .
Пример 2:
``` a = [ 3, 5, 2, 6, 7, 9, 8, 1, 4 ] a.sort( reverse = True ) print( “ List in descending order: ”, a ) ```
Излез
Во горниот пример, дадената неподредена листа е подредена во обратен редослед со помош на функцијата „ sort( reverse = True ) “.
Времеместо Сортирање со меурчиња O(n) O(n2) O(n2) O(1) Да Да Вметни сортирање O(n) O(n2) O(n2) O(1) Да Да Брзо сортирање O(n log(n)) O(n log(n)) O(n2) O(N) Не Да Спој подреди O(n log(n)) O(n log(n)) O(n log(n)) O(N) Да Не Сортирање на купови O(n дневник (n)) O(n log(n)) O(n log(n)) O(1) Не Да
Во горната табела за споредба „О“ е ознаката Голема О објаснета погоре, додека „n“ и „N“ значат големината на влезот .
Најчесто поставувани прашања
П #1) Што е сортирање () во Python?
Одговор: во Python sort() е функција која се користи за сортирање на списоци или низи по одреден редослед. Оваа функција го олеснува процесот на сортирање додека работите на големи проекти. Тоа е многу корисно за програмерите.
П #2) Како се подредувате во Python?
Одговор: Python обезбедува различни техники за сортирање кои се користат за сортирање на елементот. На пример, Брзо сортирање, Спојување сортирање, Сортирање со меурчиња, Сортирање со вметнување итн. Сите техники за сортирање се ефикасни и лесни за разбирање.
П #3) Како функционира Python подреди () работа?
Одговор: Сортот()функцијата ја зема дадената низа како влез од корисникот и ја подредува по одреден редослед користејќи го алгоритмот за сортирање. Изборот на алгоритам зависи од изборот на корисникот. Корисниците можат да користат Брзо сортирање, Спојување сортирање, Сортирање со меурчиња, Сортирање со вметнување итн. во зависност од потребите на корисникот.
Заклучок
Во горното упатство, разговаравме за техниката сортирање во Python заедно со општи техники за сортирање.
- Сортирање со меурчиња
- Вметнување сортирање
- Брзо сортирање
Научивме за нивните временски сложености и предности & недостатоци. Ги споредивме и сите горенаведени техники.
Комплексност на алгоритмите за подредувањеВременската сложеност е времето потребно на компјутерот за да изврши одреден алгоритам. Има три типа случаи со временска сложеност.
- Најлош случај: Максимално време потребно на компјутерот за да ја изврши програмата.
- Просечен случај: Време кое е потребно помеѓу минимумот и максимумот од страна на компјутерот за да ја изврши програмата.
- Најдобар случај: Минимално време потребно од компјутерот за да ја изврши програмата. Тоа е најдобриот случај на временска сложеност.
Нотации за сложеност
Голема О нотација, О: Голема о нотација е официјалниот начин да се пренесе горната граница на времето на работа на алгоритмите. Се користи за мерење на сложеноста на времето во најлош случај или велиме дека алгоритмот го бара најголемото време за да се заврши.
Големата омега нотација, 
: Големата омега нотација е официјалниот начин за пренесување на најниската граница на времето на работа на алгоритмите. Се користи за мерење на сложеноста на времето во најдобар случај или велиме за одличната количина на време одвоено од алгоритмот.
Тета нотација, 
: Тета нотацијата е официјалниот начин за пренесување и двете граници, т.е. долниот и горниот дел од времето потребно на алгоритмот за завршување.
Методи за подредување во Python
Подредување со меури
Сортирање со меур е наједноставниот начин за сортирање на податоците која користи техника на брутална сила. Ќе се повторува на секој податочен елемент и ќе го споредува со други елементиза да му обезбедиме на корисникот сортирани податоци.
Да земеме пример за да ја разбереме оваа техника:
- Ни е обезбедена низа со елементите „ 10, 40, 7, 3, 15 “. Сега, треба да ја подредиме оваа низа во растечки редослед користејќи ја техниката за сортирање меурчиња во Python.
- Првиот чекор е да се распореди низата по дадениот редослед.
- Во „Итерација 1“, ние го споредуваме првиот елемент од низата со другите елементи еден по еден.
- Црвените стрелки ја опишуваат споредбата на првите елементи со другите елементи од низата.
- Ако забележите дека „10“ е помала од „40“, така што останува исто место, но следниот елемент „7“ е помал од „10“. Оттука, се заменува и доаѓа на прво место.
- Горенаведениот процес ќе се врши повторно и повторно за да се подредат елементите.
-
- Во „Итерација 2“ вториот елемент се споредува со другите елементи од низата.
- Ако споредениот елемент е мал тогаш, тој ќе се замени, во спротивно ќе остане на истото место.
-
- Во „ Итерација 3“ третиот елемент се споредува со другите елементи од низата. „Итерација 4“ вториот последен елемент се споредува со другите елементи на низата.
- Воовој чекор низата е подредена во растечки редослед.
Програма за подредување меурчиња
``` 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)) ``` Излез
Временска сложеност на сортирање меурчиња
- Најлош случај: Најлошата временска сложеност за сортирање со меур е O( n 2).
- Просечен случај: Просечната временска сложеност за сортирање балон е O( n 2).
- Најдобар случај: Најдобрата временска сложеност за сортирање балон е O(n).
Предности
- Најмногу се користи и е лесен за имплементација.
- Можеме да ги замениме елементите на податоци без потрошувачка на краткорочно складирање.
- Потребно е помалку простор.
Недостатоци
- Не функционираше добро додека се занимаваше со голем број големи податочни елементи.
- Тоа потребни се n 2 чекори за секој „n“ број на податочни елементи да се подреди.
- Тоа не е навистина добро за апликации од реалниот свет.
Вметнување Сортирање
Вметнувањето сортирање е лесна и едноставна техника за сортирање која функционира слично како сортирањето на картите за играње. Сортирањето со вметнување ги подредува елементите споредувајќи го секој елемент еден по еден со друг. Елементите се избираат и се заменуваат со другиот елемент ако елементот е поголем или помал од другиот.
Ајде да земеме пример
- Ни е обезбедено низа со елементите „ 100, 50, 30, 40, 10“.
- Прво, ја распоредуваме низата и почнуваме да споредувамеit.
- Во првиот чекор „100“ се споредува со вториот елемент „50“. „50“ се заменува со „100“ бидејќи е поголемо.
- Во вториот чекор, повторно вториот елемент „100“ се споредува со третиот елемент „30“ и се заменува.
- Сега, ако забележите дека „30“ е на прво место бидејќи е повторно помала од „50“.
- Споредбата ќе се случи до последниот елемент од низата и на крајот ќе го добиеме подредени податоци.
Програма за вметнување подредување
``` 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]) ``` Излез
Временска сложеност на сортирање вметнување
- Најлош случај: Најлошата временска сложеност за сортирање вметнување е O( n 2).
- Просечен случај: Просечната временска сложеност за сортирање со вметнување е O( n 2).
- Најдобар случај: Најдобрата временска сложеност за сортирање со вметнување е O(n).
Предности
- Тоа е едноставно и лесен за имплементација.
- Добро функционира додека се занимава со мал број на податочни елементи.
- Не му треба повеќе простор за нејзина имплементација.
Недостатоци
- Не е корисно да се подредат огромен број на податочни елементи.
- Кога се споредуваат со други техники за сортирање, тоа не функционира добро.
Сортирање со спојување
Овој метод на сортирање го користи методот подели и владеј за да ги подреди елементите по одреден редослед. При сортирање со помош на merge sort, наелементите се делат на половини, а потоа се сортираат. По сортирањето на сите половини, елементите повторно се спојуваат за да формираат совршен редослед.
Ајде да земеме пример за да ја разбереме оваа техника
- Ни е обезбедено низа „7, 3, 40, 10, 20, 15, 6, 5“. Низата содржи 7 елементи. Ако го поделиме на половина ( 0 + 7 / 2 = 3 ).
- Во вториот чекор, ќе видите дека елементите се поделени на два дела. Секој има 4 елементи во него.
- Понатаму, елементите повторно се поделени и имаат по 2 елементи.
- Овој процес ќе продолжи се додека само еден елемент не биде присутен во низата. Погледнете го чекорот бр. 4 на сликата.
- Сега, ќе ги подредиме елементите и ќе почнеме да ги спојуваме како што бевме поделени.
- Во чекор бр. 5 ако забележите дека 7 е поголемо од 3, па ќе ги размениме и ќе го споиме во следниот чекор и обратно.
- На крајот, ќе забележите дека нашата низа се подредува по растечки редослед.
Програма за сортирање на спојување
``` 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) ``` Излез
Временска сложеност на сортирање на спојување
- Најлош случај: Најлошата временска сложеност за сортирање на спојување е O( n log( n )).
- Просечен случај: Просечната временска сложеност за сортирање на спојување е O( n log( n )).
- Најдобар случај: Најдобрата временска сложеност за сортирање на спојување е O( n log( n )).
Предности
- Големината на датотеката не е важна за оваа техника на сортирање.
- Оваа техника е добра за податоците до кои обично се пристапува по редослед. На пример, поврзани списоци, лента, итн.
Недостатоци
- Бара повеќе простор во споредба со другите техники за подредување.
- Споредбено е помалку ефикасен од другите.
Брзо сортирање
Брзото сортирање повторно го користи методот подели и владеј за подредување на елементите на списокот или низа. Ги насочува елементите на свртување и ги подредува елементите според избраниот елемент на свртување.
На пример
- Ни е обезбедена низа со елементите „ 1 ,8,3,9,4,5,7 ".
- Да претпоставиме дека „7“ е пилот-елемент.
- Сега ќе ја поделиме низата на таков начин што левата страна ги содржи елементите кои се помали од стожерниот елемент „7“, а десната ги содржи елементите поголеми од стожерниот елемент „7“.
- Сега имаме две низи „ 1,3,4,5 ” и “ 8, 9 “.
- Повторно, мораме да ги поделиме двете низи исто како што направивме погоре. Единствената разлика е во тоа што стожерните елементи се менуваат.
- Треба да ги поделиме низите додека не го добиеме единствениот елемент во низата.
- На крајот, соберете ги сите елементи на свртување во секвенца од лево кон десно и ќе го добиете подреденотониза.
Програма за брзо сортирање
``` 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 ] ) ```
Излез
Временска сложеност на брзото сортирање
- Најлош случај: Најлошата временска сложеност за брзо сортирање е O( n 2).
- Просечен случај: Просечната временска сложеност за брзо сортирање е O( n log( n ) ).
- Најдобар случај: Најдобрата временска сложеност за брзо сортирање е O( n log( n )).
Предности
- Познат е како најдобар алгоритам за сортирање во Python.
- Корисен е при ракување со голема количина на податоци.
- Не бара дополнителен простор.
Недостатоци
- Нејзината сложеност во најлош случај е слична на сложеноста на сортирањето со меур и сортирање на вметнување.
- Овој метод на сортирање не е корисен кога веќе ја имаме сортираната листа.
Сортирање на купови
Редот на грамада е напредна верзија на дрвото за бинарно пребарување . Во сортирањето на куп, најголемиот елемент од низата се става на коренот на дрвото секогаш и потоа, во споредба со коренот со јазлите на листовите.
На пример:
- Ни е обезбедена низа со елементите „ 40, 100, 30, 50, 10“.
- Во „ чекор 1 " направивме дрво според присуство на елементите во низата.
- Во „ чекор 2“ правиме максимален куп, т.е. елементи во опаѓачки редослед. Најголемиот елемент ќепрестојува на врвот (корен), а најмалиот елемент се наоѓа на дното (лисни јазли). Дадената низа станува „ 100, 50, 30, 40, 10“.
- Во „ чекор 3 " , ние го прават минималниот куп за да можеме да ги најдеме минималните елементи на низата. Со ова, ги добиваме максимумот и минималните елементи.
- Во “ чекор 4 ” со извршување на истите чекори ја добиваме подредената низа.
Програма за сортирање на купови
``` 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 ] ) ```
Излез
Временска сложеност на сортирањето на грамада
- Најлош случај: Најлошата временска сложеност за сортирање на куп е O( n log( n )).
- Просечен случај: Просечната временска сложеност за сортирање на куп е O( n log( n )).
- Најдобар случај: Најдобрата временска сложеност за сортирање на куп еО( n log( n )).
Предности
- Најмногу се користи поради неговата продуктивност.
- Може да се имплементира како алгоритам на место.
- Не бара големо складирање.
Недостатоци
- Потребен е простор за подредување на елементите.
- Тоа го прави дрвото за сортирање на елементите.
Споредба помеѓу техниките за сортирање
| Метод на подредување | Најдобра временска сложеност | Просечна временска сложеност на случај | Комплексност во најлош случај | Комплексност на простор | Стабилност | Во - |
|---|