Qarshi davlat universiteti fizika-matematika fakulteti

2.Tanlash yoki ajratilgan oraliq asosida saralash usullariga doir masalalar
Bubble sort
Bubble sort saralash algoritmi qanday usulda saralash? Ushbu so`z pufakcha usulida saralash degan ma’noni anglatadi. Bu saralash usulida massiv elementlarining ikki qo`shni elementlari taqqoslanadi va agarda noto`g`ri joylashgan bo`lsa ularnung o`rinlari almashtiriladi. Umumiy n-1 marta ushbu jarayon bajariladi. Har safar ikkita qo`shni element taqqoslanadi. Yuqoridagi jarayonda har bir element o`z o`rniga siljib boradi xuddi suvdagi pufakchaga o`xshab. Shu sababli ham uning nomi pufakcha usulida saralash deb nomlanadi. Bu algoritmning asosiy g‘oyasini yozish uchun tartiblanishi kerak bo‘lgan yozuvlar vertikal joylashgan massivda saqlanadi deb faraz qilamiz. Kalit maydonning kichik qiymatli yozuvlari «yengil» va shuning uchun pufakcha kabi ular yuqoriga «suzib chiqadi». Massiv bo‘ylab birinchi o‘tishda massivning birinchi yozuvi olinadi va uning kaliti navbatma-navbat keyingi yozuvlarning kalitlari bilan solishtirib boriladi. Agar nisbatan «og‘ir» kalitli yozuvlar uchrasa, u holda bu yozuvlar joyini almashtiradi. Nisbatan «yengil» yozuvlar uchraganda bu yozuv taqqoslash uchun etolon bo‘ladi va keyingi barcha yozuvlar shu kalit bilan solishtiriladi. Natijada eng kichik qiymatli kalit massivning eng yuqorisiga chiqadi. Massiv bo‘ylab ikkinchi o‘tishda massivning massivni birinchi o‘tishda topilgan yozuvdan keyin joylashgan og‘irligi bo‘yicha ikkinchi kalit olinadi. Massiv bo‘ylab ikkinchi va keyingi o‘tishlarda oldingi o‘tishlarda topilgan yozuvlarni ko‘rib chiqish shart emas, chunki ular qolgan yozuvlarga qaraganda kichik kalitlarga ega.
Quyida Bubble sort algoritmining c++ tilidagi dasturini keltiramiz:
#include
using namespace std;
int main(){ int a[100], i, j, n, t;
cin>>n;
for(i=0; icin>>a[i];
for(i=n; i>=1; i--)
{ for(j=0; jif(a[j]>a[j+1])
{ t=a[j]; a[j]=a[j+1]; a[j+1]=t; } }
for(i=0; icout<
Insertion sort
Yana bir saralash usuli insertion sort bo`lib, u ham massiv elementlarini saralashda qulay usullardan biri hisoblanadi. Insertion sort saralash algoritmida asosan boshidan boshlab 2 ta elementini keyin 3 ta so`ngra 4 ta va hakozo n ta elementni tartiblanadi. (1) - qadamda dastlabki 2 ta element tartiblanganda faqat 2 ta element, (2) - qadamda 3 ta element tartiblanganda esa 3 - element dastlabki 2 tasi bilan, (3) - qadamda 4 ta element tartiblanganda 4 - element dastlabki 3 tasi bilan va hakozo (n -1) - qadamda n ta element tartiblanganda n- element dastlabki n tasi bilan taqqoslanadi. Bizning maqsad ham shu oxirgi qadamda bajarilgan vazifa ya’ni n ta elementni saralashdan iborat edi.
#include
using namespace std;
int main()
{ int *a, i, n, j, m;
cin >> n;
a=new int [n];
for(i=0; icin>>a[i];
for(i=1; i{ j=i;
while(j>0&&(a[j]{ m=a[j];
a[j]=a[j-1];
a[j-1]=m;
j--; } }
for(i=0; icout << a[i] << " ";
delete []a; return 0; }