#dsa
🔬 Analysis - 3 Basic Sorting Algorithms
Sorting algoritmlar ichida linear bo'lgan eng fundamental 3 tasi - Bubble, Selection va Insertion, we know. Ularning turli holatlarda o'zaro taqqoslab ko'ramiz.
1️⃣ Already Sorted Array. Bu holatda Selection Sort ishlatish xato, chunki u baribir to'liq arrayni aylanib chiqadi. Bubble va Insertion ikkisi ham O(n), swaplarsiz.
2️⃣ Reverse Sorted Array. Uchala option ham terrible. Har bir element tekshiriladi va swap qilinadi. Lekin Insertion sort yomonlar ichida yomonroq - ko'proq shifting qiladi.
3️⃣ Almost Sorted Array. Bu holatda esa Insertion Sort is best - O(n). Rostdan ham, insertion sort logikasiga qarasak, kerakli index elementini olib oldingilar bilan compare qiladi, oldingilar already sorted bolgani uchun kamroq swap bo'ladi.
4️⃣ Small Array (n=10000). Hammasi Horrible. Hech birini tanlash kerak emas.
6️⃣ Expensive Swaps - Flash Memory. Element shift qilish qiyin holatlarda eng kam swap qiladiganini tanlaymiz - Selection Sort.
7️⃣ Stable Sort? Bubble ham Insertion ham stable, Selection sort esa tartibni buzib yuboradi. Stable degani:
Unsorted: [(A, 2), (B, 1), (C, 2), (D, 1)]
Stable sort: [(B, 1), (D, 1), (A, 2), (C, 2)]
Unstable sort: [(D, 1), (B, 1), (C, 2), (A, 2)]
Unstable sortda harflar tartibi o'zgarib ketadi.
@voidplog
🔬 Analysis - 3 Basic Sorting Algorithms
Sorting algoritmlar ichida linear bo'lgan eng fundamental 3 tasi - Bubble, Selection va Insertion, we know. Ularning turli holatlarda o'zaro taqqoslab ko'ramiz.
1️⃣ Already Sorted Array. Bu holatda Selection Sort ishlatish xato, chunki u baribir to'liq arrayni aylanib chiqadi. Bubble va Insertion ikkisi ham O(n), swaplarsiz.
2️⃣ Reverse Sorted Array. Uchala option ham terrible. Har bir element tekshiriladi va swap qilinadi. Lekin Insertion sort yomonlar ichida yomonroq - ko'proq shifting qiladi.
3️⃣ Almost Sorted Array. Bu holatda esa Insertion Sort is best - O(n). Rostdan ham, insertion sort logikasiga qarasak, kerakli index elementini olib oldingilar bilan compare qiladi, oldingilar already sorted bolgani uchun kamroq swap bo'ladi.
4️⃣ Small Array (n=10000). Hammasi Horrible. Hech birini tanlash kerak emas.
6️⃣ Expensive Swaps - Flash Memory. Element shift qilish qiyin holatlarda eng kam swap qiladiganini tanlaymiz - Selection Sort.
7️⃣ Stable Sort? Bubble ham Insertion ham stable, Selection sort esa tartibni buzib yuboradi. Stable degani:
Unsorted: [(A, 2), (B, 1), (C, 2), (D, 1)]
Stable sort: [(B, 1), (D, 1), (A, 2), (C, 2)]
Unstable sort: [(D, 1), (B, 1), (C, 2), (A, 2)]
Unstable sortda harflar tartibi o'zgarib ketadi.
@voidplog