Сортування алгоритмів: порівняння бульбашкового, швидкого, злиття та кученьових

Порівняння сортування має жорсткий рівень

Будь-яльний алгоритм сортування, який вирішує порядок виключно шляхом порівнювання пар елементів — що охоплює всі алгоритми на цій сторінці — не може обійтися ґрунтом O(n log n) у найгіршому випадку з чистої інформаційної точки зору: існує n! можливих порядків n елементів, кожне порівняння має лише два результати, і для розрізнення n! можливостей потрібно щонайменше log₂(n!) ≈ n·log₂(n) порівнянь, за оцінкою Стінгерла. Цей єдиний ліміт є мірцем, з яким вимірюються всі алгоритми нижче — деякі досягають його, інші ні, і ті, що не досягають його, не є просто гіршими реалізаціями однієї й тієї ж ідеї, вони є фундаментально різними компромісами.

O(n squared): simple, and honestly usually wrong for the job

Bubble sort repeatedly walks the array swapping adjacent out-of-order pairs until nothing moves; insertion sort builds the sorted region one element at a time, inserting each new element into its correct place among the already-sorted prefix; selection sort repeatedly finds the minimum of the unsorted remainder and swaps it into place. All three are O(n²) in the worst case — roughly n²/2 comparisons for a million elements is 500 billion operations, hopelessly slow — and none should be used on large real data.

Insertion sort earns a genuine exception: on nearly sorted data it runs close to O(n) because each new element needs very few swaps to reach its place, which is exactly why production sort implementations (Timsort, IntroSort) switch to insertion sort for small sub-arrays or nearly-sorted runs rather than recursing all the way down.

Heap Sort: Guaranteed n log n, at the cost of memory

Heap sort splits the array into a binary heap and then repeatedly extracts the maximum element from the heap, placing it at the end of the sorted portion of the array. This process continues until the entire array is sorted in O(n log n) time:

heapSort(arr): buildHeap(arr) for i in range(len(arr) - 1, 0, -1): arr[0], arr[i] = arr[i], arr[0] heapify(arr, i, 0) // Heapify the root of the heap after moving it to the end Heap sort guarantees O(n log n) in every case — best, average and worst — and is stable (equal elements keep their original relative order, which matters when sorting records by one field while wanting ties broken by insertion order). Its cost is memory: the heapify operation requires O(log n) auxiliary space, which is why in-place, memory-constrained contexts often reach for something else despite heap sort's clean worst-case guarantee.

mergeSort(arr):
  if len(arr) <= 1: return arr
  mid = len(arr) / 2
  left  = mergeSort(arr[:mid])
  right = mergeSort(arr[mid:])
  return merge(left, right)     // linear-time merge of two sorted arrays

Quicksort: usually fastest, occasionally terrible

Quicksort picks a pivot, partitions the array so everything smaller than the pivot lands left and everything larger lands right, and recurses on each side. Its average case is O(n log n) with excellent constants — in practice quicksort typically beats merge sort on random data because it sorts in place and has better cache locality — but its worst case is O(n²), which happens whenever the pivot choice consistently splits the array into a size-1 and a size-(n´)-1 partition instead of two roughly equal halves. A naive "always pick the first element" pivot strategy hits this worst case on already-sorted input, which is precisely the input real-world data most often looks like — the reason production quicksorts use randomised or median-of-three pivot selection instead.

Heap sort: quicksort’s worst-case guarantee, without the extra memory

Heap sort first arranges the array into a binary max-heap (every parent node at least as large as its children, buildable in O(n) time), then repeatedly swaps the heap’s root — always the current maximum — to the end of the unsorted region and re-heapifies what remains, in O(log n) per extraction. This gives a guaranteed O(n log n) worst case, in place, with no extra memory — strictly better worst-case behaviour than quicksort and less memory than merge sort — but it loses on real-world speed to quicksort because heap operations jump around the array non-sequentially, which is far less cache-friendly than quicksort’s mostly-sequential partitioning.

Що показують бари та тони

На цій сторінці кожен алгоритм сортує один і той же початковий масив висот, а кожне порівняння та обмін відображається на окремий аудіотон через Web Audio API, тому повільні алгоритми O(n^2) чутно так само як і видиміно перебирають значно більше операцій, ніж сортування злиттям або швидке сортування на однаковому вході. Спостереження за короткими зміщеннями сусідніх елементів у бульбашного сорту проти довгих розбиття швидкості швидкого сортування проти чистої перевірки злиттям і розділення злиттям робить різницю між цими схемами доступу — не лише їх кількість операцій — явно видимою, що велика O-нотація на сторінці ніколи не передає.

Frequently asked questions

Спробуйте наживо

Усе, що вище, працює прямо у вашому браузері — відкрийте Sorting Algorithms і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.