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

2) Har bir mumkin bo'lgan qiymatdan qancha elementlarning tartiblash tugmalari borligini aniqlang

Protsedura Count-Keys-Less(teng, m).
Kirish:
• teng - Count-Keys-Equal protsedurasiga chaqiruv orqali qaytariladigan massiv,
• m - teng massiv indekslari diapazonini belgilaydi-0 dan m-1 gacha.
Chiqish: massiv kamroq[0..m-1], shundayki j = 0,1,2,...,m-1 uchun kamroq[j] element teng[0] + teng[1 yigʻindisini oʻz ichiga oladi. ] + … + teng[j-1].
Jarayon bosqichlari:
1. Kichik[0..m-1] yangi massiv bo'lsin.
2. Kamroq[0] ni nolga sozlang.
3. j = 1 dan m-1 gacha:
A. Kam[j] ni kamroq[j-1] + teng[j-1] ga teng o'rnating.
4. Kamroq massivni qaytaring.
d(m)

3) Elementlarni A massivdan B massivga ko‘chirish orqali tartiblangan massiv yarating, shunda ular saralangan tartibda B massivda tugaydi.

Qayta tartibga solish (A, kam, n, m).
Kirish:
• A – 0 dan m-1 oralig‘idagi butun sonlar massivi,
• less - Count-Keys-Less protsedurasi tomonidan qaytariladigan massiv,
• n – A massivdagi elementlar soni,
• m – A massivdagi elementlar qiymatlari diapazonini belgilaydi.
Chiqish: saralangan tartibda A massivining elementlarini o'z ichiga olgan B massivi.
Jarayon bosqichlari:
1. B[1..n] va keyingi[0..m-1] yangi massivlar boʻlsin.
2. j = 0 dan m-1 gacha:
A. Keyingi[j] ni kamroq[j] + 1 ga o‘rnating.

3. i = 1 dan n gacha:
A. Kalit qiymatini A[i] ga o'rnating.
B. Indeks qiymatini keyingi [tugma] ga o'rnating.
C. B[indeks] ni A[i] ga o'rnating.
D. Keyingi[tugmachani] bittaga oshiring.
4. B massivini qaytaring.

• Keyingi[j] yordamchi massiv B massivdagi element indeksini bildiradi, unda j kalitli A massivning keyingi elementi joylashtirilishi kerak. Bu indeks dastlab keyingi[j] = kamroq[j] +1 bo'lib, j tugmasi yordamida topilgan har bir element uchun 1 ga oshirilishi kerak.
• 2-bosqichdagi sikl vaqt ichida bajariladi D(m) va 3-bosqichdagi sikl vaqtni oladi D(n). Shuning uchun, Rearrange protsedurasi ish vaqtiga ega D(m+n).

d(m+n)