Saralashning qat’iy usullari
Saralash to’plamdagi elementlarni ishlashga qulay ko’rinishga olib keladi. Agar sonli massivdagi sonlar kamayish tartibida saralansa uning eng birinchi elementi doimo eng kattasi bo’lib hisoblanadi. Shu sababli ma’lumotlarni saralangan formada saqlagan ma’qul.
Ushbu amaliy ishda quyidagi saralash usullari realizatsiyasi qarab chiqiladi:
• Pufakchali saralash (Bubble sort)
• Tanlash orqali saralash (Selection sort)
• O’rniga qo’yish orqali saralash (Insertion sort)
• Tez saralash (Quick sort)
• Birlashtirish orqali saralash (Merge sort)
• Shell saralash usuli (Shell sort)
1. PUFAKCHALI SARALASH (Bubble sort)
Bu saralash usulida har bir element keyingi element bilan solishtiriladi. Agar bu elementlar kerakli tartib joylashmagan bo’lsa ular o’rni almashtiriladi. Har bir iteratsiya oxirida eng katta yoki kichik element ro’yxat oxiriga joylashtiriladi.
Algoritm murakkabligi
• eng yaxshi holatda: O(n)
• o’rtacha holatda O(n2 )
• eng yomon holatda O(n2)
Dastur kodi
#include
using namespace std;
void bubbleSort(int list[], int listLength)
{
while(listLength--)
{
bool swapped = false;
for(int i = 0; i < listLength; i++)
{
if(list[i] > list[i + 1])
{
swap(list[i], list[i + 1]);
swapped = true;
}
}
if(swapped == false)
break;
}
}
int main()
{
int list[5] = {3,19,8,0,48};
cout << "Input array ..." << endl;
for(int i = 0; i < 5; i++)
cout << list[i] << '\t';
cout << endl;
bubbleSort(list, 5);
cout << "Sorted array ..." << endl;
for(int i = 0; i < 5; i++)
cout << list[i] << '\t';
cout << endl;
}
Natija:
2. Tanlash orqali saralash (Selection sort)
Ro’yxatda eng kichik element qidiriladi va uni joriy indeks bilan almashtiriladi.
|
