1. Saralash algoritmi bu roʻyxatdagi elementlarni saralash algoritmi. Agar roʻyxat elementida bir nechta maydon boʻlsa, saralash amalga oshiriladigan maydon saralash kaliti deb ataladi

6. saralash
1. Saralash algoritmi – bu roʻyxatdagi elementlarni saralash algoritmi. Agar roʻyxat elementida bir nechta maydon boʻlsa, saralash amalga oshiriladigan maydon saralash kaliti deb ataladi. Amalda raqam koʻpincha kalit sifatida ishlatiladi va ba’zi ma’lumotlar algoritm ishlashiga hech qanday ta’sir koʻrsatmaydigan qolgan maydonlarda saqlanadi. Ehtimol, boshqa hech qanday muammo saralash muammosi kabi juda koʻp turli xil yechimlarni keltirib chiqarmagan. Butun dunyoda tan olingan eng yaxshi algoritm bormi? Umuman aytganda, yoʻq. Biroq, kirish ma’lumotlarining taxminiy xususiyatlarini hisobga olgan holda, siz eng yaxshi ishlaydigan usulni tanlashingiz mumkin. Saralash usullari juda koʻp, ularning har biri oʻzining afzalliklari va kamchiliklariga ega. Tartiblash algoritmlari katta amaliy ahamiyatga ega, ular oʻzlari uchun qiziqarli. Bu juda chuqur oʻrganilgan informatika sohasi axborot qidirish tizimlarida, harbiy sohada va bank sohalarida koʻproq qoʻllaniladi. Ammo hozirgi kunda axborot oqimini tartiblash masalasi deyarli har bir sohaga kirib bordi
2. Algoritmlarni saralashga boʻlgan umumiy ilmiy qiziqishdan tashqari, har bir algoritmda uning murakkabligi deb ataladigan narsani baholash qiziq. Murakkablik algoritmning boshlangʻich bosqichlarining maksimal soni sifatida tushuniladi. Tartiblash misollari algoritmni murakkablashtirish orqali koʻrsatilishi mumkin, garchi hozirda aniq 52 usullar mavjud boʻlsa-da, siz samaradorlikda sezilarli yutuqqa erishishingiz mumkin. Massivlarni saralash masalasini yechishda odatda qoʻshimcha xotiradan foydalanishni minimallashtirish talabi qoʻyiladi, bu esa qoʻshimcha massivlardan foydalanishga yoʻl qoʻyilmasligini anglatadi. Quyidagi koʻrsatkichlar ham muhimdir: • Xotira. Bir qator algoritmlar ma’lumotlarni vaqtincha saqlash uchun qoʻshimcha xotira ajratishni talab qiladi. Amaldagi xotirani baholashda boshlangʻich massiv egallagan joy, kirish ketma-ketligidan mustaqil sarflangan xotira, masalan, dastur kodini saqlash uchun ajratilgan joy hisobga olinmaydi. • Turgʻunlik. Doimiy saralash teng elementlarning nisbiy holatini oʻzgartirmaydi. Ushbu xususiyat juda foydali boʻlishi mumkin, agar ular bir nechta maydonlardan iborat boʻlsa va saralash ulardan biri tomonidan amalga oshirilsa. Barcha saralash usullarini ikkita katta guruhga boʻlish mumkin: • Saralashning bevosita usullari; • Takomillashtirilgan saralash usullari; Toʻgʻridan-toʻgʻri tartiblash usullari usul asosida yotadigan prinsipga koʻra, uchta kichik guruhga boʻlinadi: • oddiy qoʻshimchalar boʻyicha saralash (qoʻshish); • tanlash (saralash) boʻyicha saralash; • Almashish boʻyicha saralash ("Pufakchali" saralash)
4. Pufakchali saralash (Bubble sort) algoritmining C++ dastur kodi. Ushbu algoritm ta’limiy hisoblanadi va samaradorligi pastligi sababli amalda deyarli hech qachon qoʻllanilmaydi: u kichik elementlar (ular "toshbaqalar" deb nomlanadi) massiv oxirida joylashgan testlarda sekin ishlaydi. Biroq, koʻplab boshqa usullar bunga asoslangan, masalan, Sheyker saralash va taroqsimon saralashlari. Vaqt boʻyicha murakkabligi: Eng yomon baho: O(n2 ) Oʻrtacha baho: O(n2 ) Eng yaxshi baho: O(n) void bubbleSort(int arr[], int n) { int i, j; bool swapped; for (i = 0; i < n-1; i++) { swapped = false; for (j = 0; j < n-i-1; j++) { if (arr[j] > arr[j+1]) { swap(&arr[j], &arr[j+1]); swapped = true; } } if (swapped == false) break; } }
6. #include
#include
#include

int main() {

// Ixtiyoriy son generatori
std::random_device rd;
std::mt19937 generator(rd());
std::uniform_int_distribution distribution(1, 100);

// Massivni to'ldirish

const int size = 20;
int arr[size];
for (int i = 0; i < size; ++i) {
arr[i] = distribution(generator);
}

// Massivni kamayish tartibida saralash

std::sort(arr, arr + size);

// Massivni chiqarish

std::cout << "Massiv: ";
for (int i = 0; i < size; ++i) {
std::cout << arr[i] << " ";
}
std::cout << std::endl;

return 0;

}

1. 
   7. Eng yaxshi baho: O(n) - Eng yaxshi holatda pufakchali saralashi, to'liq tuzilish bo'lsa ham, saralashni yakunlash uchun faqat bir marta o'tish va qarshilangan o'zgarishni algoritmi uchun belgilanishi. Bu holatda. murakkabligi minimal bo'ladi.
   
2. 
   O'rtacha baho: O(n^2) - Pufakchali saralash algoritmi murakkabligi o'rtacha vaqtda O(n^2) bo'ladi. Ush algoritm har bir elementni qiyoslash va rejalashtirish uchun sonli marta o'tish talab qiladi.
   
3. 
   Eng baho: O(n^2) - Pufakchali saralash algoritmi eng yomon holatda ham O(n^2) murakkablikka ega bo'ladi. Bu vaqtda saralash tizimi to'liq tesadufiy har bo'lsa ham, algoritm bir elementni qiyoslash va natija uchun sonli marta o'tishni bajarganligi tufayli murakkablik hosil qiladi.
   

8. Almashtirish funksiyasi, ikkita o'zgaruvchining narxlarini boshqarish (swap) boshqarishni boshqarish. Bu funksiya o'zgaruvchilar tashqi qiymatlarni rejalashtirishning asosiy mexanizmini ta'minladi. Swap funksiyasining ishlashini sozlashdir:

1. 
   O'zgaruvchilar narxlarini yo'nalishi: Swap funksiyasi, ikkita o'zgaruvchining narxlarini yuklaydi. Bu, o'zgaruvchilarning narxlari o'zaro almashtiriladi, funktsiyalar ichida berilgan o'zaro bog'lanish orqali amalga oshirish.
   
2. 
   Qiymatlarni o'zgaruvchilar yo'nalishi: Swap funktsiyalari, o'zgaruvchilarni rejalashtirish uchun o'zgaruvchilar bilan ishlaydi. Bu, o'zgaruvchilarning o'zgartirmaydi, balki ularning manzillarini o'zgartirmaydi.
   

9. #include
using namespace std;
void bubbleSort(int arr[], int size) {
for (int i = 0; i < size - 1; ++i) {
for (int j = 0; j < size - i - 1; ++j) {
if (arr[j] > arr[j + 1]) {
// Qiymatlarni almashtirish
arr[j] = arr[j] + arr[j + 1];
arr[j + 1] = arr[j] - arr[j + 1];
arr[j] = arr[j] - arr[j + 1];
}
}
}
}

int main() {

const int size = 10;
int arr[size] = {9, 4, 2, 7, 1, 5, 8, 3, 6, 10};

cout << "Boshlang'ich massiv: ";

for (int i = 0; i < size; ++i) {
cout << arr[i] << " ";
}

bubbleSort(arr, size);

cout << "Saralangan massiv: ";
for (int i = 0; i < size; ++i) {
cout << arr[i] << " ";
}

return 0;

}
10. #include
using namespace std;
void swap(int& a, int& b) {
int temp = a;
a = b;
b = temp;
}

void bubbleSort(int arr[], int size) {

for (int i = 0; i < size - 1; ++i) {
for (int j = 0; j < size - i - 1; ++j) {
if (arr[j] > arr[j + 1]) {
// Qiymatlar o'zgarishi
swap(arr[j], arr[j + 1]);
}
}
}
}

int main() {

const int size = 30;
int arr[size] = {9, 4, 2, 7, 1, 5, 8, 3, 6, 10, 15, 12, 19, 17, 20, 13, 11, 16, 14, 18, 26, 23, 21, 24, 22, 30, 25, 28, 27, 29};

cout << "Boshlang'ich massiv: ";

for (int i = 0; i < size; ++i) {
cout << arr[i] << " ";
}
bubbleSort(arr, size);

cout << "Saralangan massiv: ";

for (int i = 0; i < size; ++i) {
cout << arr[i] << " ";
}
return 0;
}
11. Sheyker saralashi. Sheyker (kokteyl) saralashi - bu Pufakchali (Bubble Sort) algoritmining varianti. Bubble sort algoritmi har doim chapdan elementlarni aylanib oʻtadi va birinchi iteratsiyada eng katta elementni toʻgʻri holatiga, ikkinchisida esa ikkinchi takrorlashda va 56 hokazo. Kokteyl saralash berilgan massiv orqali har ikki yoʻnalishda ham muqobil ravishda harakatlanadi. Algoritmning har bir takrorlanishi 2 bosqichga boʻlinadi: Birinchi bosqich massivni xuddi Bubble Sort singari chapdan oʻngga aylantiradi. Sikl davomida qoʻshni elementlar taqqoslanadi va agar chapdagi qiymat oʻngdagi qiymatdan katta boʻlsa, qiymatlar almashtiriladi. Birinchi takrorlash oxirida eng katta son massivning oxirida boʻladi. Ikkinchi bosqich massivni qarama-qarshi yoʻnalishda aylantiradi - bu eng soʻnggi saralangan elementdan oldin va massivning boshiga qaytish.
13Bu yerda qoʻshni elementlar taqqoslanadi va agar kerak boʻlsa almashtiriladi. Quyidagi massivni koʻrib chiqaylik (6 1 4 2 8 0 2). Birinchi oldinga oʻtish: (6 1 4 2 8 0 2)? (1 6 4 2 8 0 2), 6> 1 bilan almashtirish (1 6 4 2 8 0 2)? (1 4 6 2 8 0 2), 6> 4 bilan almashtirish (1 4 6 2 8 0 2)? (1 4 2 6 8 0 2), 6> 2 bilan almashtirish (1 4 2 6 8 0 2)? (1 4 2 6 8 0 2) (1 4 2 6 8 0 2)? (1 4 2 6 0 8 2), 8> 0 bilan almashtirish (1 4 2 6 0 8 2)? (1 4 2 6 0 2 8), 8> 2 bilan almashtirish Birinchi oldinga oʻtishdan soʻng, massivning eng katta elementi massivning oxirgi indeksida boʻladi. Birinchi orqaga oʻtish: (1 4 2 6 0 2 8)? (1 4 2 6 0 2 8) (1 4 2 6 0 2 8)? (1 4 2 0 6 2 8), 6> 0 bilan almashtirish (1 4 2 0 6 2 8)? (1 4 0 2 6 2 8), 2> 0 bilan almashtirish (1 4 0 2 6 2 8)? (1 0 4 2 6 2 8), 4> 0 bilan almashtirish (1 0 4 2 6 2 8)? (0 1 4 2 6 2 8), 1> 0 bilan almashtirish Birinchi orqaga uzatgandan soʻng, massivning eng kichik elementi massivning birinchi indeksida boʻladi. 57 Ikkinchi oldinga oʻtish: (0 1 4 2 6 2 8)? (0 1 4 2 6 2 8) (0 1 4 2 6 2 8)? (0 1 2 4 6 2 8), 4>2 bilan almashtirish (0 1 2 4 6 2 8)? (0 1 2 4 6 2 8) (0 1 2 4 6 2 8)? (0 1 2 4 2 6 8), 6>2 bilan almashtirish Ikkinchi orqaga oʻtish: (0 1 2 4 2 6 8)? (0 1 2 2 4 6 8), 4>2 bilan almashtirish Endi, massiv allaqachon saralangan, ammo bizning algoritmimiz tugallanganligini bilmaydi. Algoritm bu saralanganligini bilish uchun barcha oʻtishlarni hech qanday almashtirishsiz bajarishi kerak. (0 1 2 2 4 6 8) ? (0 1 2 2 4 6 8) (0 1 2 2 4 6 8) ? (0 1 2 2 4 6 8)
14
Quyida yuqoridagi algoritmning bajarilishi keltirilgan: void CocktailSort(int a[], int n) { bool swapped = true; int start = 0; int end = n - 1; while (swapped) { swapped = false; for (int i = start; i < end; ++i) { if (a[i] > a[i + 1]) { swap(a[i], a[i + 1]); swapped = true; } } 58 if (!swapped) break; swapped = false; --end; for (int i = end - 1; i >= start; --i) { if (a[i] > a[i + 1]) { swap(a[i], a[i + 1]); swapped = true; } } ++start; } } Vaqt boʻyicha murakkabligi: Eng yomon baho: O(n2 ) Oʻrtacha baho: O(n2 ) Eng yaxshi baho: O(n)
15#include
#include
using namespace std;
void swap(int& a, int& b) {
int temp = a;
a = b;
b = temp;
}

void cocktailSort(int arr[], int size) {

bool swapped = true;
int start = 0;
int end = size - 1;

while (swapped) {

swapped = false;

// Kamayish tartibida boshdan oxirgacha o'tish

for (int i = start; i < end; ++i) {
if (arr[i] > arr[i + 1]) {
swap(arr[i], arr[i + 1]);
swapped = true;
}
}

if (!swapped) {

break;
}

swapped = false;

--end;

// Kamayish tartibida oxirgacha boshdan o'zgarish

for (int i = end - 1; i >= start; --i) {
if (arr[i] > arr[i + 1]) {
swap(arr[i], arr[i + 1]);
swapped = true;
}
}

++start;
}

}

int main() {

const int size = 20;
int arr[size];

// Ixtiyoriy juft sonlar bilan massivni to'ldirish

random_device rd;
mt19937 rng(rd());
uniform_int_distribution dist(0, 100);

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

int num = dist(rng);
arr[i] = num % 2 == 0 ? num : num + 1; // Faqat juft sonlar
}

cout << "Boshlang'ich massiv: ";

for (int i = 0; i < size; ++i) {
cout << arr[i] << " ";
}

cocktailSort(arr, size);

std::cout << "Saralangan massiv: ";
for (int i = 0; i < size; ++i) {
std::cout << arr[i] << " ";
}

return 0;

}
25. Tanlash boʻyicha saralash (Selection sort). Birinchidan, siz massivning kichik qismini koʻrib chiqishingiz va undagi maksimal (yoki minimal) miqdorni topishingiz kerak. Keyin tanlangan qiymat birinchi saralanmagan elementning qiymati bilan almashtiriladi. Ushbu qadam massivning saralanmagan ichki qismlari tugamaguncha takrorlanishi kerak. Vaqt boʻyicha murakkabligi: Eng yomon baho: O(n2 ) Oʻrtacha baho: O(n2 ), Eng yaxshi baho: O(n2 ) void selectionSort(int arr[], int n) { int i, j, min_idx; for (i = 0; i < n-1; i++) 61 { min_idx = i; for (j = i+1; j < n; j++) if (arr[j] < arr[min_idx]) min_idx = j; swap(&arr[min_idx], &arr[i]); } } Ushbu algoritmlarning elementlari soni bir xil boʻlgan holatda qanday vaqt ichida bajarilishi va sarflangan xotira hajmi haqidagi qiyosiy jadval quyida berilgan. Sinov oʻtkaziladigan kompyuter quyidagi xususiyatlarga ega: AMD A6-3400M 4x1.4 GHz, 8 Gb operativ xotira, Windows 10 x64 build 10586.36
27. #include
#include
using namespace std;
void swap(int& a, int& b) {
int temp = a;
a = b;
b = temp;
}

void cocktailSort(int arr[], int size) {

bool swapped = true;
int start = 0;
int end = size - 1;

while (swapped) {

swapped = false;

// Kamayish tartibida boshdan oxirgacha o'tish

for (int i = start; i < end; ++i) {
if (arr[i] > arr[i + 1]) {
swap(arr[i], arr[i + 1]);
swapped = true;
}
}

if (!swapped) {

break;
}

swapped = false;

--end;

// Kamayish tartibida oxirgacha boshdan o'zgarish

for (int i = end - 1; i >= start; --i) {
if (arr[i] > arr[i + 1]) {
swap(arr[i], arr[i + 1]);
swapped = true;
}
}

++start;
}

}

int main() {

const int size = 20;
int arr[size];

// Ixtiyoriy toq sonlar bilan massivni to'ldirish

random_device rd;
mt19937 rng(rd());
uniform_int_distribution dist(1, 100);

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

int num = dist(rng);
arr[i] = num % 2 != 0 ? num : num + 1; // Faqat toq sonlar
}

cout << "Boshlang'ich massiv: ";

for (int i = 0; i < size; ++i) {
cout << arr[i] << " ";
}
cout << endl;

cocktailSort(arr, size);

cout << "Saralangan massiv: ";
for (int i = 0; i < size; ++i) {
cout << arr[i] << " ";
}
cout << endl;

return 0;

}