Laboratoriya mashg’uloti №9

Laboratoriya mashg’uloti № 9. Saralashning qat’iy usullari va ularning qo’llanilishi

Ma’lumotlar tuzilmasi va algoritmlash fanidan

Laboratoriya mashg’uloti o’qituvchisi: Raxmanova M.

Sodda saralash usullari

• Qo’yish orqali saralash (Insertion sort)
• Tanlash orqali saralash (Selection sort)

Qo’yish orqali saralash

Qo’yish orqali saralashda massiv chapdan o’ngga qarab navbati bilan ko’rib chiqiladi. Bunda har bir keyingi element minimal va maksimal qiymatli yaqinroqda joylashlashgan elementlar orasiga joylashtiriladi.

Qo’yish orqali saralash

void InsertionSort(vector& values) {

for (size_t i = 1; i < values.size(); ++i) {

int x = values[i];

size_t j = i;

while (j > 0 && values[j - 1] > x) {

values[j] = values[j - 1];

--j;

}

values[j] = x;

}

}

Tanlash orqali saralash

Avval massiv elementlari to’plami ichidan maksimum (yoki minimum) ni topish lozim. Shundan so’ng tanlangan qiymat bilan birinchi saralanmagan elementning joyini almashtiradi. Bu qadamni massivda saralanmagan qismmassivlar tugaguniga qadar davom qildirish kerak.

Tanlash orqali saralash

void SelectionSort(vector& values) {

for (auto i = values.begin(); i != values.end(); ++i) {

auto j = std::min_element(i, values.end());

swap(*i, *j);

}

}

Saralashning effektiv usullari

• Tezkor saralash (Quicksort)
• Birlashtirish orqali saralash
• Piramidali saralash

Tezkor saralash

• Bu algoritm uch qadamdan iborat. Oldin massivdan bitta element tanlash lozim – uni odatda tayanch deb ham ataydilar. Keyin massivning qolgan elementlari ichidan tayanch qiymatidan kichiklari ungacha, undan katta yoki tenglari tayanchdan so’ng qayta joylashtiriladi. Shundan so’ng yuqoridagi ikkita qadam tayanchdan o’ng va chapda joylashgan qismmassivlarga rekursiv ravishda qo’llaniladi.
• Tezkor qidiruvni 1960-yilda mashinaviy tarjima uchun yaratishgan: u vaqtlarda lug’at magnit lentalarda joylashgan, qayta ishlanuvchi matn so’zlarini saralash lentaning bir marta aylanishida orqaga qaytarishlarsiz tarjimaga ega bo’lish imkonini bergan.

Tezkor saralash

Tezkor saralash

int Partition(vector& values, int l, int r) {

int x = values[r];

int less = l;

for (int i = l; i < r; ++i) {

if (values[i] <= x) {

swap(values[i], values[less]); ++less;

}

}

swap(values[less], values[r]);

return less;

}

void QuickSortImpl(vector& values, int l, int r) {

if (l < r) {

int q = Partition(values, l, r);

QuickSortImpl(values, l, q - 1);

QuickSortImpl(values, q + 1, r);

}

}

void QuickSort(vector& values) {

if (!values.empty()) {

QuickSortImpl(values, 0, values.size() - 1);

}

}

Birlashtirish orqali saralash

Birlashtirish orqali saralash elementlarga ketma-ket murojaat qilinadigan ma’lumotlar strukturasi (masalan, oqimlar uchun) uchun qulay hisoblanadi. Bunda massiv taxminan bir xil ikkita qismga ajratiladi va ularning har biri alohida saralanadi. Hosil bo’lgan qismmassivlar bittaga birlashtiriladi.

Birlashtirish orqali saralash

void MergeSortImpl(vector& values, vector& buffer, int l, int r) {

if (l < r) {

int m = (l + r) / 2;

MergeSortImpl(values, buffer, l, m);

MergeSortImpl(values, buffer, m + 1, r);

int k = l;

for (int i = l, j = m + 1; i <= m || j <= r; ) {

if (j > r || (i <= m && values[i] < values[j])) {

buffer[k] = values[i];

++i;

} else {

buffer[k] = values[j];

++j;

}

++k;

}

for (int i = l; i <= r; ++i) {

values[i] = buffer[i];

}

}

}

void MergeSort(vector& values) {

if (!values.empty()) {

vector buffer(values.size());

MergeSortImpl(values, buffer, 0, values.size() - 1);

}

}

Piramidali saralash

Bu saralash usulida avval kiruvchi massiv elementlaridan piramida tuziladi. Piramida (yoki ikkilik uyum (двоичная куча)) – bu elementlarni shunday tasvirlash usuliki, bunda har bitta tugundan ikkitadan ortiq bo’linish (shoxlarga ajralish) bo’lmaydi. Ota uzeldagi qiymat uning qiz uzellaridagi qiymatlaridan katta bo’lishi lozim.

• Bu saralash usulida avval kiruvchi massiv elementlaridan piramida tuziladi. Piramida (yoki ikkilik uyum (двоичная куча)) – bu elementlarni shunday tasvirlash usuliki, bunda har bitta tugundan ikkitadan ortiq bo’linish (shoxlarga ajralish) bo’lmaydi. Ota uzeldagi qiymat uning qiz uzellaridagi qiymatlaridan katta bo’lishi lozim.
• Piramidali saralash tanlash orqali saralashga o’xshash, bunda avval maksimal element topiladi, keyin uni oxiriga joylashtiramiz. Keyingi navbatlarda ham shu amallarni qolgan elementlar uchun rekursiv takrorlash lozim.

Piramidali saralash

void HeapSort(vector& values) {

std::make_heap(values.begin(), values.end());

for (auto i = values.end(); i != values.begin(); --i) {

std::pop_heap(values.begin(), i);

 }

}

E’TIBORINGIZ UCHUN RAXMAT!!!