Имплементације алгоритама за сортирање у Питхон-у

by
Tweet
Share
Share
Pin

Сортирање је једна од најчешће коришћених функција у програмирању. И биће потребно време да се заврши сортирање ако нисмо користили исправан алгоритам.

У овом чланку ћемо разговарати о различитим алгоритмима сортирања.

Провешћемо вас кроз различите алгоритме за сортирање са сваким кораком који долази у имплементацији. Имплементациони део ће бити у Питхон-у. Можете га лако претворити у било који језик када добијете алгоритам. То је ствар синтаксе језика.

У овом водичу ћемо видети различите алгоритме од најгорих до најбољих. Дакле, не брини. Пратите чланак и примените их.

Хајде да заронимо у алгоритме за сортирање.

Инсертион Сорт

Сортирање уметањем је један од једноставних алгоритама за сортирање. Лако је имплементирати. И коштаће вас више времена да сортирате низ. Неће се користити у већини случајева за сортирање за веће низове.

Алгоритам сортирања уметањем одржава сортиране и несортиране под-делове у датом низу.

Сортирани поддео садржи само први елемент на почетку процеса сортирања. Узећемо елемент из несортираног низа и поставити га на исправан положај у сортираном поднизу.

Хајде да погледамо визуелне илустрације сортирања уметањем корак по корак са примером.

Хајде да видимо кораке за имплементацију сортирања уметањем.

  • Иницијализујте низ лажним подацима (целим бројевима).
  • Итерирајте преко датог низа из другог елемента.
    • Узмите тренутну позицију и елемент у две променљиве.
    • Напишите петљу која се понавља све док се не појави први елемент низа или елемент који је мањи од тренутног елемента.
      • Ажурирајте тренутни елемент претходним елементом.
      • Смањење тренутне позиције.
    • Овде петља мора да стигне или до почетка низа или да пронађе мањи елемент од тренутног елемента. Замените елемент тренутне позиције тренутним елементом.

Временска сложеност сортирања уметањем је О(н^2), а комплексност простора ако је О(1).

То је то; сортирали смо дати низ. Покренимо следећи код. Надам се да сте инсталирали Питхон, ако нисте, погледајте водич за инсталацију. Алтернативно, можете користити онлајн Питхон компајлер.

def insertion_sort(arr, n):
	for i in range(1, n):

		## current position and element
		current_position = i
		current_element = arr[i]

		## iteratin until
		### it reaches the first element or
		### the current element is smaller than the previous element
		while current_position > 0 and current_element <
		 arr[current_position - 1]:
			## updating the current element with previous element
			arr[current_position] = arr[current_position - 1]

			## moving to the previous position
			current_position -= 1

		## updating the current position element
		arr[current_position] = current_element

if __name__ == '__main__':
	## array initialization
	arr = [3, 4, 7, 8, 1, 9, 5, 2, 6]
	insertion_sort(arr, 9)

	## printing the array
	print(str(arr))

Селецтион Сорт

Сортирање избора је слично сортирању уметањем са малом разликом. Овај алгоритам такође дели низ на сортиране и несортиране под-делове. А онда ћемо, на свакој итерацији, узети минимални елемент из несортираног поддела и поставити га на последњу позицију сортираног поддела.

  Како да пронађем софтвер који недостаје на Убунту-у?

Хајде да сортирамо илустрације селекције ради бољег разумевања.

Хајде да видимо кораке за имплементацију сортирања селекције.

  • Иницијализујте низ лажним подацима (целим бројевима).
  • Итерирајте преко датог низа.
    • Одржавајте индекс минималног елемента.
    • Напишите петљу која се понавља од тренутног до последњег елемента.
      • Проверите да ли је тренутни елемент мањи од минималног елемента или не.
      • Ако је тренутни елемент мањи од минималног елемента, замените индекс.
    • Ми имамо минимални индекс елемента са собом. Замените тренутни елемент минималним елементом користећи индексе.

Временска сложеност селекцијског сортирања је О(н^2), а комплексност простора ако је О(1).

Покушајте да имплементирате алгоритам јер је сличан сортирању уметањем. Код испод можете видети.

def selection_sort(arr, n):
	for i in range(n):

		## to store the index of the minimum element
		min_element_index = i
		for j in range(i + 1, n):
			## checking and replacing the minimum element index
			if arr[j] < arr[min_element_index]:
				min_element_index = j

		## swaping the current element with minimum element
		arr[i], arr[min_element_index] = arr[min_element_index], arr[i]

if __name__ == '__main__':
	## array initialization
	arr = [3, 4, 7, 8, 1, 9, 5, 2, 6]
	selection_sort(arr, 9)

	## printing the array
	print(str(arr))

Буббле Сорт

Буббле сортирање је једноставан алгоритам. Он мења суседне елементе на свакој итерацији узастопно док се дати низ не сортира.

Итерира низ низ и помера тренутни елемент на следећу позицију све док не буде мањи од следећег елемента.

Илустрације нам помажу да визуелно разумемо сортирање мехурића. Хајде да их видимо.

Хајде да видимо кораке за имплементацију сортирања мехурића.

  • Иницијализујте низ лажним подацима (целим бројевима).
  • Итерирајте преко датог низа.
  • Итерирајте од 0 до ни-1. Последњи и елементи су већ сортирани.
  • Проверите да ли је тренутни елемент већи од следећег или не.
  • Ако је тренутни елемент већи од следећег, замените два елемента.
    •   Како променити радњу двоструког додира на Аппле Пенцил-у за иПад Про

    Временска сложеност сортирања мехурића је О(н^2), а комплексност простора ако је О(1).

    До сада можете лако имплементирати сортирање мехурића. Хајде да видимо код.

    def bubble_sort(arr, n):
	for i in range(n):
		## iterating from 0 to n-i-1 as last i elements are already sorted
		for j in range(n - i - 1):
			## checking the next element
			if arr[j] > arr[j + 1]:
				## swapping the adjucent elements
				arr[j], arr[j + 1] = arr[j + 1], arr[j]

if __name__ == '__main__':
	## array initialization
	arr = [3, 4, 7, 8, 1, 9, 5, 2, 6]
	bubble_sort(arr, 9)

	## printing the array
	print(str(arr))

    Сортирање спајањем

    Сортирање спајањем је рекурзивни алгоритам за сортирање датог низа. Ефикаснији је од претходно разматраних алгоритама у смислу временске сложености. Следи приступ подела па владај.

    Алгоритам за сортирање спајањем дели низ на две половине и сортира их одвојено. Након сортирања две половине низа, он их спаја у један сортирани низ.

    Пошто је то рекурзивни алгоритам, он дели низ све док низ не постане најједноставнији (низ са једним елементом) за сортирање.

    Време је за илустрацију. Дај да видимо.

    Хајде да видимо кораке за имплементацију сортирања спајањем.

    • Иницијализујте низ лажним подацима (целим бројевима).
    • Напишите функцију која се зове спајање за спајање поднизова у један сортирани низ. Прихвата низ аргумената, леви, средњи и десни индекс.
      • Добијте дужине дужине левог и десног подниза користећи дате индексе.
      • Копирајте елементе из низа у одговарајући леви и десни низ.
      • Итерирајте преко два подниза.
        • Упоредите два елемента подниза.
        • Замените елемент низа мањим елементом из два подниза за сортирање.
      • Проверите да ли су остали елементи у оба подниза.
      • Додајте их у низ.
    • Напишите функцију која се зове мерге_сорт са низом параметара, левим и десним индексима.
      • Ако је леви индекс већи или једнак десном индексу, онда вратите.
      • Пронађите средњу тачку низа да бисте поделили низ на две половине.
      • Рекурзивно позовите мерге_сорт користећи леви, десни и средњи индекс.
      • Након рекурзивних позива, спојите низ са функцијом спајања.
      Како да креирате иМессаге профил на иПхоне-у и иПад-у

    Временска сложеност сортирања спајањем је О(нлогн), а комплексност простора ако је О(1).

    То је то за имплементацију алгоритма сортирања спајањем. Проверите код испод.

    def merge(arr, left_index, mid_index, right_index):
	## left and right arrays
	left_array = arr[left_index:mid_index+1]
	right_array = arr[mid_index+1:right_index+1]

	## getting the left and right array lengths
	left_array_length = mid_index - left_index + 1
	right_array_length = right_index - mid_index

	## indexes for merging two arrays
	i = j = 0

	## index for array elements replacement
	k = left_index

	## iterating over the two sub-arrays
	while i < left_array_length and j < right_array_length:

		## comapring the elements from left and right arrays
		if left_array[i] < right_array[j]:
			arr[k] = left_array[i]
			i += 1
		else:
			arr[k] = right_array[j]
			j += 1
		k += 1

	## adding remaining elements from the left and right arrays
	while i < left_array_length:
		arr[k] = left_array[i]
		i += 1
		k += 1

	while j < right_array_length:
		j += 1
		k += 1

def merge_sort(arr, left_index, right_index):
	## base case for recursive function
	if left_index >= right_index:
		return

	## finding the middle index
	mid_index = (left_index + right_index) // 2

	## recursive calls
	merge_sort(arr, left_index, mid_index)
	merge_sort(arr, mid_index + 1, right_index)

	## merging the two sub-arrays
	merge(arr, left_index, mid_index, right_index)

if __name__ == '__main__':
	## array initialization
	arr = [3, 4, 7, 8, 1, 9, 5, 2, 6]
	merge_sort(arr, 0, 8)

	## printing the array
	print(str(arr))

    Закључак

    Постоји много других алгоритама за сортирање, али горе су неки од често коришћених. Надам се да сте уживали у учењу сортирања.

    Затим сазнајте о алгоритмима за претрагу.

    Срећно кодирање 🙂 👨‍💻