Laboratoriya ishi №30. Almashtirish usuli bo'yicha saralash

Laboratoriya ishi № 30. Almashtirish usuli bo'yicha saralash  

(pufakchalarni saralash). 

 

Ishning  maqsadi:  ma'lumotlarni  saralash  maqsadini  tushunish.  Dasturlarda 

almashtirish tartibini (pufakchalarni saralash) ishlatishni o'rganing. 

Nazariy qism: 

 

 

C ++ da pufakchalarni saralash turi 

 

Bugun  biz  saralash  algoritmini  tahlil  qilamiz,  siz  pufakchalarni  saralash 

usulidan foydalanib o'z massivingiz yoki vektoringizni saralashingiz mumkin. 

 

Ushbu  algoritmni  amalga  oshirish  juda  sodda,  ammo  shu  bilan  birga  uning 

asosiy kamchiligi - sekin tartiblash. 

 

Pufakchalarni saralash o’zi nima? 

 

 

 

Pufakli  saralash,  ehtimol  men  ko'rgan  eng  oddiy  nav.  Odatda  dasturlash 

kitoblarida  uchraydi  va  undan  tashqariga  chiqmaydi.  Bu  boshqa  tartiblash 

algoritmlariga qaraganda ancha sekin. 

 

 

Ammo  uning  yordami  bilan  o'ziga  qaraganda  ancha  samarali  bo'lgan 

algoritmlar  paydo  bo'ldi.  Bunday  saralashlar  orasida  biz  shakerlarni  saralashni  yoki 

ularni aralashtirish tartibida saralashni aytib o'tamiz. 

 

Pufakni saralash algoritmi qanday ishlaydi 

 

 

Pufakni qanday saralashini uch nuqtai nazardan ta'riflash mumkin: 

1. Butun qatordan o'tish; 

2. Qo'shni hujayralar juftligini taqqoslash; 

3. Agar taqqoslash paytida i katakchaning qiymati i + 1 katakchaning qiymatidan 

katta ekanligi ayon bo'lsa, u holda biz ushbu kataklarning qiymatlarini o'zgartiramiz; 

 

Quyida siz qabariq turining amalda qanday ishlashini ko'rishingiz mumkin. 

 

 

  

Qanday qilib qabariq turini yaratish mumkin 

 

Pufakning turini yaratish uchun nima qilishimiz kerak: 

• Massivning barcha elementlarini N marta takrorlash uchun ikki qator hosil qiling (N 

massivning o'lchamidir). 

• If tarmoqlanuvchi operatori yordamida qator kataklarini taqqoslang. 

• Hujayralar qiymatlarini almashtiring. 

Quyidagi  misolda  biz  foydalanuvchiga  massivni  to'ldirishni  so'radik,  uni  pufakchali 

navlardan foydalanib saralaymiz. 

 

 

1 

2 

3 

4 

5 

6 

7 

8 

9 

10 

11 

12 

13 

14 

15 

16 

17 

18 

19 

20 

21 

22 

23 

24 

25 

26 

27 

28 

29 

30 

31 

32 

33 

#include  

  

using namespace std; 

  

int main() { 

 setlocale(LC_ALL, "rus"); 

  

 int digitals[10]; // 

10 hujayradan iborat qator e'lon qildi 

 

  

 cout << "

 Massivni to'ldirish uchun 10 ta raqamni kiriting: 

" << endl; 

  

 for (int i = 0; i < 10; i++) { 

 cin >> digitals[i]; // "

o'qing

 " 

elementlar qator 

 } 

  

 for (int i = 0; i < 10; i++) { 

 for (int j = 0; j < 9; j++) { 

 if (digitals[j] > digitals[j + 1]) { 

 int b = digitals[j]; // 

qo'shimcha o'zgaruvchini yaratdi 

 

 

 digitals[j] = digitals[j + 1]; // 

almashtirish 

 

 digitals[j + 1] = b; // 

element qiymatlari

 

 } 

 } 

 } 

  

 cout << "

 Saralangan qator:

";

 

  

 for (int i = 0; i < 10; i++) { 

 cout << digitals[i] << " "; // 

massiv elementlarini ko'rsatish 

 

 } 

 system("pause"); 

 return 0; 

} 

 

Keling, 16 - 24 qatorlarni batafsil ko'rib chiqamiz (qabariq bu erda): 

1. 16-qatorda: biz birinchi tsiklni yaratdik. 

2.  17-qatorda:  ikkinchi,  ammo  allaqachon  o'rnatilgan  ichki  halqa  xuddi  shunga 

o'xshash tarzda yaratilgan. 

3. 18-qatorda: ikkita element taqqoslanadi. 

Agar ushbu shartning natijasi ijobiy bo'lsa, unda biz elementlarning qiymatini 

o'zgartiramiz. 

Agar natija salbiy bo'lsa, unda biz qiymatlarni o'zgartirish bosqichini o'tkazib 

yuboramiz. 

4.  19-qatorda:  [i]  va  raqamli  [i  +  1]  raqamlarning  hujayralari  qiymatlarini 

almashtirish uchun b o'zgaruvchini yaratdi. 

Keling, yuqoridagi dastur ishga tushganda nimani ko'rsatishini ko'raylik: 

 

sort_puzerek.cpp 

Введите 10 чисел для заполнения массива: 

5 3 6 2 7 0 2 8 9 10 

Массив в отсортированном виде: 0 2 2 3 5 6 7 8 9 10 

Process returned 0 (0x0) execution time : 0.005 s 

Press any key to continue. 

  

pufakchalarni saralash turini qanday yaxshilash mumkin 

Quyida siz qabariq turining optimallashtirilgan versiyasini ko'rishingiz mumkin. 

 

 

1 

2 

3 

4 

5 

6 

7 

8 

9 

10 

11 

12 

 for (int i = 0; i < 10; i++) { 

 bool flag = true; 

 for (int j = 0; j < 10 - (i + 1); j++) {  

 if (digitals[j] > digitals[j + 1]) { 

 flag = false; 

 swap (digitals[j], digitals[j + 1]); 

 } 

 } 

 if (flag) { 

 break; 

 } 

 } 

 

 

Keling, uni optimallashtirish uchun nima qilganimizni ko'rib chiqaylik: 

1. 17-qatorda: ichki pastadir holatini i <10 - (i + 1) ga o'zgartirildi. 

 

 

Gap  shundaki,  massivni  birinchi  to'liq  aylanishida  eng  katta  element  suzadi 

(qator oxiriga o'ting). Ikkinchi eng katta element tsiklning ikkinchi o'tishida va hokazo 

penaltimetr hujayrasiga joylashadi. 

 

Shunday qilib, ketma-ketlik elementlarini yana bir marta taqqoslamaslik uchun 

vaqtni behuda sarflash uchun tashqi ko'chadan har bir o'tishidan keyin ichki pastadir 

segmentini 1 ga kamaytirishga qaror qildik. 

 

2.  Siz  hattoki  qator  tartiblangan  bo'lsa  ham  (yoki  darhol  tartiblangan)  bo'lsa  ham, 

algoritm  elementlarni  taqqoslashni  davom  ettirayotganini  payqagan  bo'lishingiz 

mumkin. 

 

Buning  uchun  5-qatorda:  qabariq  turini  to'xtatish  uchun  (qator  allaqachon 

tartiblangan  bo'lsa),  biz  o'zgaruvchan  bayroqni  e'lon  qilamiz  (odatda  bayroq  yoki 

bayroq deb nomlanadi). Hatto uni ishga tushirish vaqtida biz qiymatni rost qo'yamiz, 

ammo u quyidagicha o'zgaradi: 

• 4-qatorda shartning natijasi ijobiy bo'lsa, noto'g'ri. 

Shuningdek,  siz  int  turidagi  o'zgaruvchan  bayroqni  e'lon  qilishingiz  mumkin  va 

haqiqiy yoki noto'g'ri o'rniga, 1 va 0 qiymatlarini o'zgaruvchiga saqlang. 

 

Va 9-qatorda: algoritmdan chiqishimiz uchun quyidagilarni tekshiramiz: 

• Agar boolean o'zgaruvchisi to'g'ri bo'lsa, u holda massiv allaqachon tartiblangan va 

siz chiqishingiz mumkin. Buning uchun break operatoridan foydalanamiz. 

• Agar bayroqning qiymati noto'g'ri bo'lsa, biz qatorni tartiblashtirishda davom etamiz. 

6-qatorda:  siz  (ehtimol)  notanish  almashtirish  funktsiyasini  ko'rdingiz.  U  nima 

qilayotganini qisqacha tavsiflash uchun ikkita dalilni (vergul bilan ajratilgan) oladi va 

ularning  qiymatlarini  almashtiradi.  Bizning  holatlarimizda  u  [j]  va  [j  +  1]  raqamli 

raqamlarni  oladi.  Ushbu  3  qatorni  yozmaslik  uchun  biz  ushbu  funktsiyadan 

foydalanganmiz: 

 

1 

2 

3 

int b = digitals[j];  

digitals[j] = digitals[j + 1];  

digitals[j + 1] = b; 

 

Siz undan foydalanishingiz shart emas, chunki u sizning kodingizni 

tezlashtirmaydi. Ammo yuqorida aytib o'tganimizdek, kam kod bo'ladi. 

 

Ish tartibi: 

 

 

Usulning  g'oyasi:  saralash  bosqichi  pastdan  yuqoriga  massivdan  o'tishdan 

iborat.  Yo'l  davomida  qo'shni  elementlarning  juftlari  ko'rinadi.  Agar  juftlikning 

elementlari noto'g'ri tartibda bo'lsa, biz ularni almashtiramiz. 

 

Taqqoslash / almashtirish operatsiyasi har ikki qo'shni element uchun amalga 

oshiriladi.  Birinchi  qatordan  o'tgandan  so'ng,  "tepa"  -  "eng  engil"  element.  Keyingi 

tartiblash  loopi  ikkinchi  elementdan  boshlab  amalga  oshiriladi,  natijada  massivdagi 

ikkinchi eng kichik element va hokazo. 

 

 

 

 

Paskal dasturida almashinuvini saralash dasturi 

 

{ Сортируются записи типа item по ключу item.key } 

{ для вспомогательных переменных используется тип index } 

procedure BubbleSort; 

 var i,j: index; x:item; 

begin for i:=2 to n do 

 begin for j:=n downto i do 

 

 if a[j-1].key > a[j].key then 

 

 

begin x:=a[j-1]; a[j-1]:=a[j]; a[j]:=x; 

 

 

end; 

 

end; 

end; 

 

C ++ almashinuvini saralash dasturi 

 

emplate< class T > 

void bubbleSort(T* arr, int size) 

{ 

 T tmp; 

 for(int i = 0; i < size - 1; ++i) // i - номер прохода 

 {  

 for(int j = 0; j < size - 1; ++j) // внутренний цикл прохода 

 {  

 if (arr[j + 1] < arr[j])  

 { 

 tmp = arr[j + 1];  

 arr[j + 1] = arr[j];  

 arr[j] = tmp; 

 } 

 } 

 } 

 

 

 

Pufakchalarni  saralash  algoritmi  juda  sekin  va  samarasiz.  Shunga  qaramay, 

uning katta plyusi bor: u sodda va uni har qanday usulda yaxshilash mumkin. Amalda, 

yaxshilanish  bo'lsa  ham,  qabariq  usuli  juda  sekin.  Shuning  uchun  u  deyarli 

ishlatilmaydi. 

 

 

Mashqlar 

 

Pufakchalarni saralash turini tuzatish uchun barcha amallarni bajaring: 

1. 15 elementdan iborat qatorni tasodifiy sonlar bilan to'ldiring. 

2. pufakchalarni saralashni tartiblash algoritmi yordamida qatorni tartiblang. 

3. Dasturga sharhlarda, pufakchalarni saralashlarni saralash jarayonini aytib bering. 

4. Ekranda butun massivni ko'rsating. 

 

2. Dastur quyidagilarni o'z ichiga olishi kerak: 

 

a. Ekrandan ma'lumotlarni kiritish; 

b. Harakat sharhlari; 

v. Tegishli saralash tartibini ko'rsatish; 

d. Ekranda ma'lumotlar chiqishi; 

e. Noto'g'ri harakat xatosi haqida xabarlar. 

 

 

 

Nazorat savollari: 

 

1. Pufakni saralashdan maqsad nima? 

2. Pufakchalarni saralash algoritmlari qanday baholanadi? 

3. Qabariq turining asosiy kamchiligi nimada? 

4. Qabariq qanday turga bo'linadi? 

5. Pufakni saralash algoritmi qanday ishlaydi? 

6. Pufak turini qanday yarataman? 

7. Qabariq turini qanday yaxshilashimiz mumkin?