Лекция 2 Алгоритмы сортировки и поиска

Juda oddiy tartiblash tartibi

Protsedura Really-Simple-Sort(A,n).
Kirish:

• A massiv bo'lib, uning barcha elementlari 1 yoki 2 qiymatga ega,
• n - tartiblangan elementlar soni A.

Natija: A ning elementlari kamaymaydigan tartibda tartiblangan.
Jarayon bosqichlari:
1. k ni nolga tenglashtiring.
2. i = 1 dan n gacha:
A. Agar A[i] = 1 bo'lsa, k ni bir marta oshiring.
3. i = 1 dan k gacha:
A. A[i] ni 1 ga o‘rnating.
4. i = k + 1 dan n gacha:
A. A[i] ni 2 ga o‘rnating.

Hisoblash tartibi

• m turli mumkin bo'lgan saralash kalit qiymatlari holatiga umumlashtirish, masalan, 0 dan butun sonlar.m-1.
• Fikr: agar k elementning x ga teng saralash tugmachalari borligini va l elementning x dan kichik saralash tugmachalariga ega ekanligini bilsak, tartiblangan massivdagi x ga teng tartiblash tugmachalariga ega elementlar l + 1 dan l + k gacha pozitsiyalarni egallashi kerak.
• Kerakli: har bir mumkin boʻlgan saralash kaliti qiymati uchun nechta elementda ushbu qiymatdan (l qiymati) kichik tartiblash kalitlari borligini va nechta elementda berilgan tartiblash kaliti qiymati (k qiymati) borligini hisoblang.

Quyi vazifalarga ajratish

1) Berilgan qiymatga teng tartiblash kalitlari nechta element borligini hisoblang

Protsedura Count-Klavishlar-Teng(A,n,m).
Kirish:
• A – 0 dan m-1 oralig‘idagi butun sonlar massivi,
• n – A massivdagi elementlar soni,
• m – A massividagi qiymatlar diapazonini belgilaydi.
Chiqish: massiv teng[0..m-1] shundayki teng[j] j = 0,1,2,...,m-1 uchun j ga teng A massiv elementlari sonini o'z ichiga oladi.
Jarayon bosqichlari:
1. teng[0..m-1] yangi massiv bo'lsin.
2. Teng massivning barcha qiymatlarini nolga o'rnating.
3. i=1 dan n gacha:
A. Asosiy o'zgaruvchining qiymatini A[i] ga o'rnating.
B. Teng[tugmani] bittaga oshiring.
4. Massivni teng qaytaring.
d(n+m)