Сортування є однією з найбільш використовуваних функцій у програмуванні. І для завершення сортування знадобиться час, якщо ми не використали правильний алгоритм.
У цій статті ми обговоримо різні алгоритми сортування.
Ми розповімо вам про різні алгоритми сортування на кожному етапі впровадження. Частина реалізації буде на 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))
Бульбашкове сортування
Бульбашкове сортування – це простий алгоритм. Він змінює місцями сусідні елементи на кожній ітерації неодноразово, доки заданий масив не буде відсортований.
Він повторює масив і переміщує поточний елемент на наступну позицію, доки він не буде меншим за наступний елемент.
Ілюстрації допомагають нам візуально зрозуміти бульбашкове сортування. Давайте їх подивимось.
Давайте розглянемо кроки для реалізації бульбашкового сортування.
Часова складність бульбашкового сортування дорівнює 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 за допомогою лівого, правого та середнього індексів.
- Після рекурсивних викликів об’єднайте масив за допомогою функції злиття.
Часова складність сортування злиттям дорівнює 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))
Висновок
Існує багато інших алгоритмів сортування, але вище наведено деякі з часто використовуваних. Сподіваюся, вам сподобалося вивчати сортування.
Далі дізнайтеся про алгоритми пошуку.
Щасливого кодування 🙂 👨💻