“Ўринга қўйиш билан саралаш”

“Ўринга қўйиш билан саралаш”

Маърузачи: доц. М.Тўхтасинов

“Ахборотларга ишлов беришни алгоритмлаш” фани
Очик дарс мавзуси:

Назарий

Ўрнига қўйиш усулида тартиблаш - оддий саралаш алгоритми ҳисобланади. Унинг моҳияти шундаки, алгоритмнинг ҳар бир босқичида биз массив элементларидан бирини оламиз ва уни қўшиш керак бўлган жойни топиб (ўсиш тартибини текширган ҳолда, яъни ) шу жойга қўямиз. Шуни таъкидлаш керакки, массивнинг 1 –элементи сараланган деб ҳисобланади.
Алгоритмнинг оғзаки таърифи мураккаб кўринади, лекин аслида уни амалга ошириш осон усуллардан ҳисобланади. Ҳар биримиз, фаолият туридан қатъи назар, тартиблаш алгоритмини ўзимиз сезмаган ҳолатда қўллаймиз. Мисол учун, биз ҳамёнимизда пулларни саралашда ишлатамиз. Масалан, 10000 сўмни оламиз ва кўрамиз – қўлимизда бошқа 2000, 5000 ва 20000 сўмли пуллар бор. У ҳолда 10000 сўмли пулимизни 5000 ва 20000 сўмли пуллар орасига қўямиз. Ва ҳ.к.

Назарий

Қўйиш алгоритми массив қаторини иккита соҳага ажратади: тартибланган ва тартибланмаган. 1-элементдан ташқари бутун қатор дастлаб тартибланмаган майдон ҳисобланади. Биринчи ўтиш пайтида, тартибга солинмаган майдондан биринчи элемент олиб ташланади ва тартибланган соҳанинг тўғри жойига тартиб билан жойлаштирилади.
Ҳар бир ўтишда тартибланган майдоннинг катталиги 1 га, тартибланмаган майдоннинг катталиги эса 1 га камаяди.
Асосий цикл 1 дан n-1 гача ишлайди. j -итерацияда [i]-элемент тартибланган майдондаги тўғри жойга қўйилади. Бу тартибланган майдоннинг [i] дан катта барча элементларини ўнгга битта позиция силжитиш орқали амалга оширилади. [i] - элемент [i] дан кичик ва [i] дан катта бўлган элементлар орасига қўйилади.

Анимацияли намойиш

Анимацияли намойиш

Амалий дастури

for(int i=1;ifor(int j=i;j>0 && x[j-1]>x[j];j--)
swap(x[j-1],x[j]); // o’rnini almashtirish
void InsertionSort(int data[], int lenD)
{
int key = 0; int i = 0;
for(int j = 1;jkey = data[j];
i = j-1;
while(i>=0 && data[i]>key)
{ data[i+1] = data[i];
i = i-1;
data[i+1]=key;
}
}
}
ЁКИ

Синов натижалари