Koje vrste sortiranja poznajete i kakve su njihove teškoće po vremenu i memoriji?

Postoji mnogo algoritama za sortiranje, a evo glavnih sa njihovom vremenskom i prostorom složenošću:

• Bubble Sort (Sortiranje mehurićima)

  • Vreme: O(n²) u najgorem i prosečnom slučaju
  • Memorija: O(1) (sortiranje na mestu)

• Insertion Sort (Sortiranje umetanja)

  • Vreme: O(n²) u najgorem slučaju, O(n) u najboljem (skoro sortirani niz)
  • Memorija: O(1)

• Selection Sort (Sortiranje izbora)

  • Vreme: O(n²) u svim slučajevima
  • Memorija: O(1)

• Merge Sort (Mešovito sortiranje)

  • Vreme: O(n log n) u svim slučajevima
  • Memorija: O(n) (zahteva dodatnu memoriju za spajanje)

• Quick Sort (Brzo sortiranje)

  • Vreme: O(n log n) u proseku, O(n²) u najgorem slučaju (retko)
  • Memorija: O(log n) (rekurzivni stek)

• Heap Sort (Heap sortiranje)

  • Vreme: O(n log n) u svim slučajevima
  • Memorija: O(1)

• Timsort — hibridni algoritam sortiranja koji se koristi u Pythonu i Javi

  • Vreme: O(n log n) u proseku i u najgorem slučaju
  • Memorija: O(n)

Izbor algoritma zavisi od veličine podataka, zahteva memorije i stabilnosti sortiranja (da li održava redosled jednakih elemenata). Na primer, Merge Sort je stabilan, Quick Sort je obično brži, ali nestabilan.