Jakie rodzaje sortowania znasz i jakie mają one trudności pod względem czasu i pamięci?

Istnieje wiele algorytmów sortowania, oto główne z ich złożonością czasową i przestrzenną:

• Sortowanie bąbelkowe (Bubble Sort)

  • Czas: O(n²) w najgorszym i średnim przypadku
  • Pamięć: O(1) (sortowanie w miejscu)

• Sortowanie przez wstawianie (Insertion Sort)

  • Czas: O(n²) w najgorszym przypadku, O(n) w najlepszym (prawie posortowana tablica)
  • Pamięć: O(1)

• Sortowanie przez wybór (Selection Sort)

  • Czas: O(n²) we wszystkich przypadkach
  • Pamięć: O(1)

• Sortowanie przez scalanie (Merge Sort)

  • Czas: O(n log n) we wszystkich przypadkach
  • Pamięć: O(n) (wymaga dodatkowej pamięci do scalania)

• Sortowanie szybkie (Quick Sort)

  • Czas: O(n log n) średnio, O(n²) w najgorszym przypadku (rzadko)
  • Pamięć: O(log n) (stos rekurencyjny)

• Sortowanie przez kopiec (Heap Sort)

  • Czas: O(n log n) we wszystkich przypadkach
  • Pamięć: O(1)

• Timsort — hybrydowe sortowanie używane w Pythonie i Javie

  • Czas: O(n log n) średnio i w najgorszym przypadku
  • Pamięć: O(n)

Wybór algorytmu zależy od rozmiaru danych, wymagań pamięciowych i stabilności sortowania (czy zachowuje kolejność równych elementów). Na przykład Merge Sort jest stabilny, Quick Sort jest zwykle szybszy, ale niestabilny.