Реалізації алгоритмів сортування в Python

Сортування є однією з найбільш використовуваних функцій у програмуванні. І для завершення сортування знадобиться час, якщо ми не використали правильний алгоритм.

У цій статті ми обговоримо різні алгоритми сортування.

Ми розповімо вам про різні алгоритми сортування на кожному етапі впровадження. Частина реалізації буде на Python. Ви можете легко перетворити його на будь-яку мову, отримавши алгоритм. Це питання синтаксису мови.

У цьому підручнику ми побачимо різні алгоритми від найгіршого до найкращого. Так що не хвилюйтеся. Дотримуйтесь статті та втілюйте їх у життя.

Давайте зануримося в алгоритми сортування.

Сортування вставкою

Сортування вставкою є одним із простих алгоритмів сортування. Це легко реалізувати. І сортування масиву коштуватиме вам більше часу. У більшості випадків він не використовуватиметься для сортування великих масивів.

Алгоритм сортування вставкою підтримує відсортовані та невідсортовані частини в заданому масиві.

Відсортована підчастина містить лише перший елемент на початку процесу сортування. Ми візьмемо елемент із невідсортованого масиву та розмістимо його у правильному місці у відсортованому підмасиві.

Давайте подивимося на візуальні ілюстрації сортування вставки крок за кроком на прикладі.

Давайте розглянемо кроки для реалізації сортування вставкою.

  • Ініціалізуйте масив фіктивними даними (цілі числа).
  • Ітерація по заданому масиву з другого елемента.
    • Візьміть поточну позицію та елемент у двох змінних.
    • Напишіть цикл, який повторюється, доки не з’явиться перший елемент масиву або елемент, менший за поточний елемент.
      • Оновити поточний елемент попереднім елементом.
      • Зменшення поточної позиції.
    • Тут цикл повинен або досягти початку масиву, або знайти елемент, менший за поточний елемент. Замінити поточний елемент позиції на поточний елемент.

Часова складність сортування вставкою дорівнює O(n^2), а просторова – O(1).

Це воно; ми відсортували заданий масив. Давайте запустимо наступний код. Сподіваюся, ви встановили Python, якщо ні, перегляньте посібник із встановлення. Крім того, ви можете скористатися онлайн-компілятором Python.

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

Сортування вибору

Сортування вибору подібне до сортування вставкою з невеликою відмінністю. Цей алгоритм також ділить масив на відсортовані та невідсортовані підчастини. А потім, на кожній ітерації, ми будемо брати мінімальний елемент із невідсортованої підчастини та розміщувати його в останній позиції відсортованої підчастини.

  Немає параметра «Виконати з графічним процесором» у контекстному меню, клацнувши правою кнопкою миші

Давайте відсортуємо ілюстрації виділення для кращого розуміння.

Давайте розглянемо кроки для реалізації сортування вибору.

  • Ініціалізуйте масив фіктивними даними (цілі числа).
  • Ітерація по заданому масиву.
    • Зберігати індекс мінімального елемента.
    • Напишіть цикл, який повторюється від поточного елемента до останнього.
      • Перевірте, чи поточний елемент менший за мінімальний.
      • Якщо поточний елемент менше мінімального елемента, то замінити індекс.
    • Ми маємо з собою мінімальний індекс елемента. Поміняти місцями поточний елемент на мінімальний за допомогою індексів.

Часова складність сортування дорівнює O(n^2), а просторова – O(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))

Бульбашкове сортування

Бульбашкове сортування – це простий алгоритм. Він змінює місцями сусідні елементи на кожній ітерації неодноразово, доки заданий масив не буде відсортований.

Він повторює масив і переміщує поточний елемент на наступну позицію, доки він не буде меншим за наступний елемент.

  Чому варто уникати загальнодоступних портів USB

Ілюстрації допомагають нам візуально зрозуміти бульбашкове сортування. Давайте їх подивимось.

Давайте розглянемо кроки для реалізації бульбашкового сортування.

  • Ініціалізуйте масив фіктивними даними (цілі числа).
  • Ітерація по заданому масиву.
  • Ітерація від 0 до ni-1. Останні i елементи вже відсортовані.
  • Перевірте, чи поточний елемент більший за наступний.
  • Якщо поточний елемент більший за наступний, поміняйте місцями два елементи.
  • Часова складність бульбашкового сортування дорівнює O(n^2), а просторова – O(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))

    Сортування злиттям

    Сортування злиттям — це рекурсивний алгоритм для сортування заданого масиву. Він більш ефективний, ніж розглянуті раніше алгоритми з точки зору складності часу. Він дотримується підходу «розділяй і володарюй».

    Алгоритм сортування злиттям ділить масив на дві половини та сортує їх окремо. Після сортування двох половин масиву вони об’єднуються в один відсортований масив.

    Оскільки це рекурсивний алгоритм, він ділить масив до тих пір, поки масив не стане найпростішим (масив з одним елементом) для сортування.

    Настав час ілюстрації. Давайте подивимося.

    Давайте розглянемо кроки для реалізації сортування злиттям.

    • Ініціалізуйте масив фіктивними даними (цілі числа).
    • Напишіть функцію під назвою merge, щоб об’єднати підмасиви в один відсортований масив. Він приймає масив аргументів, лівий, середній і правий індекси.
      • Отримайте довжину лівого та правого підмасивів, використовуючи задані індекси.
      • Скопіюйте елементи з масиву у відповідні лівий і правий масиви.
      • Перебирайте два підмасиви.
        • Порівняйте два елементи підмасиву.
        • Замініть елемент масиву на менший елемент із двох підмасивів для сортування.
      • Перевірте, чи залишилися елементи в обох підмасивах.
      • Додайте їх до масиву.
    • Напишіть функцію під назвою merge_sort із масивом параметрів, лівим і правим індексами.
      • Якщо лівий індекс більший або дорівнює правому індексу, повертається.
      • Знайдіть середню точку масиву, щоб розділити масив на дві половини.
      • Рекурсивно викликайте merge_sort за допомогою лівого, правого та середнього індексів.
      • Після рекурсивних викликів об’єднайте масив за допомогою функції злиття.
      Як отримати доступ до старого облікового запису Myspace без електронної пошти та пароля

    Часова складність сортування злиттям дорівнює O(nlogn), а просторова – O(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))

    Висновок

    Існує багато інших алгоритмів сортування, але вище наведено деякі з часто використовуваних. Сподіваюся, вам сподобалося вивчати сортування.

    Далі дізнайтеся про алгоритми пошуку.

    Щасливого кодування 🙂 👨‍💻