Bu usul ingliz informatigi Charlz Xoar (Чарльз Хоар) tomonidan 1960 yilda Moskva universitetida kompiyterda electron tarjima qilish bo’yicha o’qiyotganida, rus-ingliz so’zlashgichini ishlab chiqayotganida taklif etilgan.
Bu usul almashtirish usulining modifikatsiyasi bo‘lib, uning asosini kalitlarni tanlangan kalitga(tayanch kalit) nisbatan almashtirish tashkil qiladi. Tanlash-ixtiyoriy ravishda, masalan, o’rtasini.
Bu usul almashtirish usulining modifikatsiyasi bo‘lib, uning asosini kalitlarni tanlangan kalitga(tayanch kalit) nisbatan almashtirish tashkil qiladi. Tanlash-ixtiyoriy ravishda, masalan, o’rtasini.
Algoritm g’oyasi: 1) tayanch element tanlanadi;
2) elementlarni tayanch elementdan kichik elementlar to’plami va katta yoki teng elementlar to’plamiga bo’lamiz;
3) bu 2 to’plamga nisbatan yuqoridagi 1-2 punktni qo’llaymiz ( bo’sh yoki 1ta elementli to’plamga qo’llanilmaydi)
Tez saralash (Quicksort) Misol: Samaradorlik: T(n)=O(nlogn)
Samaradorligi :
Yaxshi holat. Har bir iteratsiyada massiv 2ta teng podmassivga bo’linadi.Bu saralash uchun eng kam vaqtni beradi. Bunda – O(n2)
Yomon holat. Har bir iteratsiyada massiv 1ta tayanch elementdan iborat podmassiv va qolgan barcha elementdan iborat podmassivga bo’linadi. Bu xolat har bir etapda yoki eng kichik yoki eng katta element tanlanganda yuz beradi. –
О(n logn)
O’rtacha samaradorlik - О(n logn).
Birlashtirish orqali saralash (sortirovka sliyaniyem)
Saralash masalasini hal qilish bosqichlari:
Saralanadigan massiv ikkita kichik qismga bo'linadi;
Kichik o'lchamdagi ikkita tartiblangan massiv bittaga birlashtiriladi(tanlash orqali).
Masalani kichik qismlarga rekursiv bo'linish massivning o’lchami bir kattalikda bo'lguncha sodir bo'ladi (1 uzunlikdagi har qanday massivni tartiblangan deb hisoblash mumkin).
Birlashtirish orqali saralash
Birlashtirish orqali saralash
Mavzu bo‘yicha nazorat savollari
