Какви видове сортиране знаете и какви са техните трудности по време и памет?

Има много алгоритми за сортиране, ето основните от тях с тяхната времева и пространствена сложност:

• Пузырковата сортировка (Bubble Sort)

  • Време: O(n²) в най-лошия и средния случай
  • Памет: O(1) (сортиране на място)

• Сортировка по вставки (Insertion Sort)

  • Време: O(n²) в най-лошия случай, O(n) в най-добрия (почти сортиран масив)
  • Памет: O(1)

• Сортировка по избор (Selection Sort)

  • Време: O(n²) във всички случаи
  • Памет: O(1)

• Сортировка сливане (Merge Sort)

  • Време: O(n log n) във всички случаи
  • Памет: O(n) (изисква допълнителна памет за сливане)

• Бърза сортировка (Quick Sort)

  • Време: O(n log n) средно, O(n²) в най-лошия случай (рядко)
  • Памет: O(log n) (рекурсивен стек)

• Кучешка сортировка (Heap Sort)

  • Време: O(n log n) във всички случаи
  • Памет: O(1)

• Timsort — хибридна сортировка, използвана в Python и Java

  • Време: O(n log n) средно и в най-лошия случай
  • Памет: O(n)

Изборът на алгоритъм зависи от размера на данните, изискванията към паметта и стабилността на сортирането (запазва ли реда на равните елементи). Например, Merge Sort е стабилен, Quick Sort обикновено е по-бърз, но нестабилен.