Selection sort

Selection sort — Tanlab saralash bu — oddiy tartiblash algoritmidir. Ushbu tartiblash algoritmi oʻz joyida taqqoslashga asoslangan algoritm boʻlib, unda roʻyxat ikki qismga boʻlinadi, tartiblangan qism chap tomonda va tartiblanmagan qism oʻng tomonda. Dastlab, tartiblangan qism boʻsh, tartiblanmagan qismi esa butun roʻyxatdir.

Udtag sort 001

Eng kichik element tartiblanmagan massivdan tanlanadi va eng chap element bilan almashtiriladi va bu element tartiblangan massivning bir qismiga aylanadi. Bu jarayon tartiblanmagan massiv chegarasini bitta element bilan oʻngga siljitishda davom etadi.

Ushbu algoritm katta maʼlumotlar toʻplamlari uchun mos emas, chunki uning oʻrtacha va eng yomon holatlari murakkabligi n (n²), bu yerda n — elementlar soni.

Tanlab saralash qanday ishlaydi?

Misol tariqasida quyidagi massivni koʻrib chiqamiz: arr[] = {64, 25, 12, 22, 11}

Birinchi oʻtish: Saralangan massivdagi birinchi oʻrin uchun butun massiv 0 dan 4 gacha boʻlgan indeksdan ketma-ket oʻtkaziladi. Hozirgi vaqtda 64 saqlanadigan birinchi pozitsiya, butun massivni aylanib oʻtgandan soʻng, 11 eng past qiymat ekanligi ayon boʻladi.

  64   	   25   	   12   	   22   	   11   

Shunday qilib, 64 ni 11 bilan almashtiring. Bir iteratsiyadan soʻng massivdagi eng kam qiymat boʻlgan 11 , tartiblangan roʻyxatning birinchi pozitsiyasida paydo boʻladi.

  11   	   25   	   12   	   22   	   64   

Ikkinchi oʻtish: 25 mavjud boʻlgan ikkinchi pozitsiya uchun massivning qolgan qismini yana ketma-ketlikda aylantiring.

  11   	   25   	   12   	   22   	   64   

Ketishdan soʻng biz 12 massivdagi ikkinchi eng past qiymat ekanligini va u massivda ikkinchi oʻrinda paydo boʻlishi kerakligini aniqladik, shuning uchun bu qiymatlarni almashtiring.

  11   	   12   	   25   	   22   	   64   

Uchinchi oʻtish: Endi, uchinchi oʻrin uchun, 25 mavjud boʻlgan joyda yana massivning qolgan qismini aylanib oʻting va massivdagi uchinchi eng kam qiymatni toping.

  11   	   12   	   25   	   22   	   64   

Ketish paytida 22 uchinchi eng kam qiymat boʻlib chiqdi va u massivda uchinchi oʻrinda paydo boʻlishi kerak, shuning uchun 22 ni uchinchi oʻrindagi element bilan almashtiring.

  11   	   12   	   22   	   25   	   64   

Toʻrtinchi oʻtish: Xuddi shunday, toʻrtinchi pozitsiya uchun massivning qolgan qismini kesib oʻting va massivdagi toʻrtinchi eng kichik elementni toping. 25 4-eng past qiymat boʻlgani uchun u toʻrtinchi oʻrinni egallaydi.

  11   	   12   	   22   	   25   	   64   

Beshinchi oʻtish: Nihoyat, massivda mavjud boʻlgan eng katta qiymat avtomatik ravishda massivning oxirgi pozitsiyasiga joylashtiriladi Olingan massiv tartiblangan massivdir.

  11   	   12   	   22   	   25   	   64

Selsort de 0

Tanlab saralash algoritmi

• 1-qadam − MINni 0-indexli joyga qoʻying
• 2-qadam − Roʻyxatdagi minimal elementni qidiring
• 3-qadam − MIN manzilidagi qiymat bilan almashtiring
• 4-qadam − Keyingi elementga ishora qilish uchun MIN ni oshiring
• 5-qadam − Roʻyxat tartiblashtirilguncha takrorlang

Dasturi

# include <bits/stdc++.h>
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;
}

.