Кои алгоритми за сортиране знаете?

Основни алгоритми за сортиране:

• Bubble Sort (Bubble Sort): Прост, но неефективен алгоритъм, който многократно преминава през списъка, разменяйки съседните елементи, ако са в неправилен ред.
• Selection Sort (Сортиране чрез избор): Намира най-малкия (или най-големия) елемент от несортирания част на списъка и го поставя в началото.
• Insertion Sort (Вмъкване): Постепенно изгражда сортиран списък, като вмъква всеки нов елемент на правилното място в вече сортирания сегмент.
• Merge Sort (Сливане): Рекурсивен алгоритъм, който разделя списъка на подсписъци, ги сортира и след това ги обединява.
• Quick Sort (Бързо сортиране): Алгоритъм "разделяй и владей", който избира опорен елемент (pivot) и преразпределя елементите така, че по-малките да са отляво, а по-големите отдясно. След това рекурсивно прилага към подсписъците.
• Shell Sort (Shell): Подобрение на сортирането чрез вмъкване, използващо сравнения на големи разстояния между елементите.
• Heap Sort (Куча): Използва структурата данни "купа" за ефективно сортиране.

Съществуват и по-малко разпространени, но ефективни в определени случаи алгоритми като сортиране по броене (Counting Sort), поразрядно сортиране (Radix Sort), и сортиране с кутии (Bucket Sort).

Времето за изпълнение на основните алгоритми (средно):

Алгоритъм за сортиране	Средно време
Bubble Sort	O(n²)
Selection Sort	O(n²)
Insertion Sort	O(n²)
Merge Sort	O(n log n)
Quick Sort	O(n log n)
Shell Sort	Зависи от стъпката
Heap Sort	O(n log n)

Пример за реализация на бързото сортиране на Python:

def quicksort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]  # Избиране на опорен елемент
    left = [x for x in arr if x < pivot]  # По-малки от опорния
    middle = [x for x in arr if x == pivot] # Равни на опорния
    right = [x for x in arr if x > pivot] # По-големи от опорния
    return quicksort(left) + middle + quicksort(right) # Рекурсивно сортиране и обединяване