|
Bubble sort
Bubble Sort - bu eng oddiy tartiblash algoritmi bo'lib, agar ular noto'g'ri tartibda bo'lsa, qo'shni elementlarni qayta-qayta almashtirish orqali ishlaydi.
Misol:
Birinchi o‘tish:
( 5 1 4 2 8 ) –> ( 1 5 4 2 8 ), Bu yerda algoritm dastlabki ikki elementni taqqoslaydi va 5 > 1 dan keyin almashinadi.
( 1 5 4 2 8 ) –> ( 1 4 ) 5 2 8 ), 5 > 4 dan beri almashtirish
( 1 4 5 2 8 ) –> ( 1 4 2 5 8 ), 5 dan beri almashtirish > 2
( 1 4 2 5 8 ) –> ( 1 4 2 5 8 )), Endi, bu elementlar allaqachon tartibda bo'lgani uchun (8 > 5), algoritm ularni almashtirmaydi.
Ikkinchi oʻtish:
( 1 4 2 5 8 ) –> ( 1 4 2 5 8 )
( 1 4 2 5 8 ) –> ( 1 2 4 5 8 ), 4 > 2 dan beri almashtirish
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
Endi massiv tartiblangan, lekin bizning algoritmimiz uning tugallanganligini bilmaydi. Algoritm tartiblanganligini bilish uchun uni almashtirishsiz bitta to'liq o'tish kerak .
Uchinchi o‘tish:
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 ) )
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
#include
using namespace std;
void swap(int *xp, int *yp)
{
int temp = *xp;
*xp = *yp;
*yp = temp;
}
void bubbleSort(int arr[], int n)
{
int i, j;
for (i = 0; i < n-1; i++)
for (j = 0; j < n-i-1; j++)
if (arr[j] > arr[j+1])
swap(&arr[j], &arr[j+1]);
}
/* Function to print an array */
void printArray(int arr[], int size)
{
int i;
for (i = 0; i < size; i++)
cout << arr[i] << " ";
cout << endl;
}
int main()
{
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr)/sizeof(arr[0]);
bubbleSort(arr, n);
cout<<"Sorted array: \n";
printArray(arr, n);
return 0;
}
Chiqish:
Saralangan massiv:
11 12 22 25 34 64 90
Eng yomon va o'rtacha ish vaqtining murakkabligi: O(n*n). Eng yomon holat massiv teskari tartiblanganda sodir bo'ladi.
Eng yaxshi ish vaqtining murakkabligi: O(n). Eng yaxshi holat massiv allaqachon tartiblangan bo'lsa sodir bo'ladi.
Yordamchi bo'shliq: O(1)
chegara holatlari: Elementlar allaqachon tartiblangan bo'lsa, qabariq bilan tartiblash minimal vaqtni oladi (n tartibi).
Joyda saralash: Ha
Barqaror: Ha
Oddiyligi tufayli qabariqli tartiblash ko'pincha tartiblash algoritmi tushunchasini kiritish uchun ishlatiladi.
Kompyuter grafikasida u deyarli tartiblangan massivlarda juda kichik xatolikni (masalan, ikkita elementni almashtirish) aniqlash va uni chiziqli murakkablik (2n) bilan tuzatish qobiliyati bilan mashhur. Masalan, u ko'pburchaklarni to'ldirish algoritmida qo'llaniladi, bunda chegaralovchi chiziqlar ma'lum bir skanerlash chizig'ida (x o'qiga parallel chiziq) x koordinatasi bo'yicha tartiblanadi va y ortishi bilan ularning tartibi o'zgaradi (ikki element almashtiriladi) faqat kesishish joylarida. ikki qatorli
Selection sort
Tanlovni saralash algoritmi tartiblanmagan qismdan minimal elementni (oʻsish tartibini hisobga olgan holda) qayta-qayta topib, uni boshiga qoʻyish orqali massivni saralaydi. Algoritm berilgan massivda ikkita pastki massivni saqlaydi.
1) Allaqachon tartiblangan pastki qator.
2) Saralanmagan qolgan pastki qator.
Saralashning har bir iteratsiyasida saralanmagan pastki qatordan minimal element (o‘sish tartibini hisobga olgan holda) tanlanadi va tartiblangan pastki qatorga o‘tkaziladi.
Quyidagi misol yuqoridagi qadamlarni tushuntiradi:
arr[] = 64 25 12 22 11
// arr[0...4] dagi minimal elementni toping
// va uni boshiga joylashtiring
11 25 12 22 64
// arr[1...4] dagi minimal elementni toping
// va uni arr [1...4] boshiga qo'ying
11 12 25 22 64
// arr[2...4] dagi minimal elementni toping.
// va uni arr boshiga qo'ying[2...4]
11 12 22 25 64
// arr[3...4] dagi minimal elementni toping.
// va uni arr boshiga qo'ying[3...4]
11 12 22 25 64
Code:
#include
using namespace std;
void swap(int *xp, int *yp)
{
int temp = *xp;
*xp = *yp;
*yp = temp;
}
void selectionSort(int arr[], int n)
{
int i, j, min_idx;
for (i = 0; i < n-1; i++)
{
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]);
}
}
void printArray(int arr[], int size)
{
int i;
for (i=0; i < size; i++)
cout << arr[i] << " ";
cout << endl;
}
int main()
{
int arr[] = {64, 25, 12, 22, 11};
int n = sizeof(arr)/sizeof(arr[0]);
selectionSort(arr, n);
cout << "Sorted array: \n";
printArray(arr, n);
return 0;
}
Quick sort
Birlashtirish saralash kabi , QuickSort ham bo'lish va zabt etish algoritmidir. U elementni pivot sifatida tanlaydi va berilgan massivni tanlangan pivot atrofida ajratadi. QuickSort-ning turli yo'llar bilan pivotni tanlaydigan ko'plab turli versiyalari mavjud.
Har doim birinchi elementni pivot sifatida tanlang.
Har doim oxirgi elementni pivot sifatida tanlang (quyida amalga oshiriladi)
Pivot sifatida tasodifiy elementni tanlang.
Pivot sifatida medianni tanlang.
QuickSort-dagi asosiy jarayon bo'lim(). Bo'limlar maqsadi - massiv va massivning x elementi pivot sifatida berilgan, x ni tartiblangan massivda o'zining to'g'ri joyiga qo'ying va barcha kichikroq elementlarni (x dan kichik) x dan oldin qo'ying va barcha katta elementlarni (x dan katta) keyin qo'ying. x. Bularning barchasi chiziqli vaqtda amalga oshirilishi kerak.
Do'stlaringiz bilan baham: |
