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

Reja:

1. Shell saralash usuli;

2. Tez saralash (Quicksort).

(yana

1. Piramidasimon saralash;

2.Сортировка подсчетом

3.Цифровая сортировка

4. Сортировка слиянием va x.z. )

5-Mavzu(Davomi): Saralashning yaxshilangan usullari

Shell saralash usuli

Bu saralash usuli 1959 yilda D.SHell tomonidan taklif qilingan bo‘lib, qo‘yish orqali saralashning modifikatsiyasi hisoblanadi.

Алгоритм:

• Dastlab bir-biridan 4ta pozitsiya (masofa)da turgan elementlar gruppalanadi va qo’yish usuli orqali saralanadi. Bu to’rtalik saralash deyiladi;
• Keyin bir-biridan 2ta pozitsiya (masofa)da turgan elementlar gruppalanadi va qo’yish usuli orqali saralanadi. Bu ikkitalik saralash deyiladi;
• oxirida bittalik yani oddiy saralash amalga oshiriladi

D.Shell taklif etgan oralig’lar ketma-ketligi umumiy holda quyidagicha:

D.Shell taklif etgan oralig’lar ketma-ketligi umumiy holda quyidagicha:

d1=n/2 , di=di-1/2 , dk=1 eng yomon holatda ;

algoritm samaradorligi - O(n2);

Eng yaxshi xolatda - O(nlog2n);

O’rtach vaqt – tanlangan qadamlarga bog’liq;

Xotira xajmi- O(n), qo’shimcha O(1)

Shell saralashi (qisqarib boruvchi qadamlar orqali saralash)

Algoritm umumiy g’oyasi
Faraz qilaylik, a[0],a[1],a[2],…, a[n] boshlang‘ich elementlar ketma-ketligi bo‘lsin.
1-qadam. Boshlang‘ich ketma-ketlikning har r1 o‘rinda joylashgan elementlari guruhlanib, har bir guruh alohida qo‘yish usuli orqali saralanadi: ({a[0], a[r1], a[2*r1],…,}, {a[1], a[1+r1], a[1+2*r1],…,} v.h.).
2-qadam. Hosil qilingan ketma-ketlikda har r2 o‘rinda joylashgan elementlar guruhlanib, har bir guruh alohida saralanadi.
....................................................................................................................