“Ma’lumotlar tuzilmasi va algoritmlar” fanining maqsadi va vazifasi

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;
• Olingan qismlarning har biri alohida tartiblanadi;
• Kichik o'lchamdagi ikkita tartiblangan massiv bittaga birlashtiriladi.

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

1. Shell saralashi

2. Piramida tushunchasi va uni qurish

3. Piramidasimon saralash

4. Tez saralash tushunchasi

Режа:

• Шелл саралаш усули;
• Пирамидасимон саралаш;
• Тез саралаш (Quicksort).

Мавзу: Саралашнинг яхшиланган усуллари

Шелл саралаши (қисқариб борувчи қадамлар орқали саралаш)

Алгоритм ғояси
Изоҳ
Шелл саралаш 1959 йилда Д.Шелл томонидан таклиф қилинган бўлиб, қўшиш орқали саралашнинг модификацияси ҳисобланади.
Фараз қилайлик, a[0],a[1],a[2],…, a[n] бошланғич элементлар кетма-кетлиги бўлсин.
1-қадам. Бошланғич кетма-кетликнинг ҳар r1 ўринда жойлашган элементлари гуруҳланиб, ҳар бир гуруҳ алоҳида қўшиш усули орқали сараланади({a[0], a[r1], a[2*r1],…,}, {a[1], a[1+r1], a[1+2*r1],…,} в.ҳ.).
2-қадам. Ҳосил қилинган кетма-кетликда ҳар r2 ўринда жойлашган элементлар гуруҳланиб, ҳар бир гуруҳ алоҳида сараланади.
....................................................................................................................