Qaysi turdagi saralashlarni bilasiz va ularning vaqt va xotira bo'yicha qiyinchiliklari qanday?

Ko'p sonli saralash algoritmlari mavjud, ularning asosiylari va ularning vaqt va joylashuv murakkabligi:

• Pufak saralash (Bubble Sort)

  • Vaqt: O(n²) eng yomon va o'rtacha holatda
  • Xotira: O(1) (joyda saralash)

• Kiritish saralash (Insertion Sort)

  • Vaqt: O(n²) eng yomon holatda, O(n) eng yaxshi (deyarli saralangan massiv)
  • Xotira: O(1)

• Tanlash saralash (Selection Sort)

  • Vaqt: Barcha holatlarda O(n²)
  • Xotira: O(1)

• Qayta birlashtirish saralash (Merge Sort)

  • Vaqt: Barcha holatlarda O(n log n)
  • Xotira: O(n) (qo'shimcha xotira talab qiladi)

• Tez saralash (Quick Sort)

  • Vaqt: O(n log n) o'rtacha, O(n²) eng yomon holatda (kamdan-kam)
  • Xotira: O(log n) (rekursiv stek)

• Xotira saralash (Heap Sort)

  • Vaqt: Barcha holatlarda O(n log n)
  • Xotira: O(1)

• Timsort — Python va Java da ishlatiladigan gibrid saralash algoritmi

  • Vaqt: O(n log n) o'rtacha va eng yomon holatda
  • Xotira: O(n)

Algoritm tanlovi ma'lumotlarning hajmiga, xotira talablariga va saralashning barqarorligiga (teng elementlarning tartibini saqlash yoki saqlamaslik) bog'liq. Masalan, Merge Sort barqarordir, Quick Sort odatda tezroq, lekin barqaror emas.