Programming and Data Structures


Insertion Sort Insertion Sort



Download 256,76 Kb.
bet2/2
Sana26.06.2022
Hajmi256,76 Kb.
#706239
1   2
Bog'liq
Saralash algoritmlari 3-ma\'ruza

Insertion Sort

Insertion Sort

General situation :


0
size-1
i
remainder, unsorted
smallest elements, sorted
0
size-1
i
x:
i
j
x[i] katta
bo’lmagunigachon
davom etadi.

Insertion Sort


void insertionSort (int list[], int size)
{
int i,j,item;
for (i=1; i{
item = list[i] ;
/* Move elements of list[0..i-1], that are greater than item, to one position ahead of their current position */
for (j=i-1; (j>=0)&& (list[j] > item); j--)
list[j+1] = list[j];
list[j+1] = item ;
}
}

Insertion Sort


int main()
{
int x[ ]={-45,89,-65,87,0,3,-23,19,56,21,76,-50};
int i;
for(i=0;i<12;i++)
printf("%d ",x[i]);
printf("\n");
insertionSort(x,12);
for(i=0;i<12;i++)
printf("%d ",x[i]);
printf("\n");
}
OUTPUT
-45 89 -65 87 0 3 -23 19 56 21 76 -50
-65 -50 -45 -23 0 3 19 21 56 76 87 89

Insertion Sort - Example

Selection Sort

Selection Sort

General situation :


remainder, saralanmagan
Eng kichik element, saralangan
0
size-1
k
x:
Steps :
    • Eng kichik element topiladi, mval, in x[k…size-1]
    • Eng kichik element bilan almashadi x[k], keyin kortib boradi.

0
k
size-1
mval
swap
x:

Selection Sort


/* Yield location of smallest element in
x[k .. size-1];*/
int findMinLloc (int x[ ], int k, int size)
{
int j, pos; /* x[pos] is the smallest element found so far */
pos = k;
for (j=k+1; jif (x[j] < x[pos])
pos = j;
return pos;
}

Selection Sort


/* The main sorting function */
/* Sort x[0..size-1] in non-decreasing order */
int selectionSort (int x[], int size)
{ int k, m;
for (k=0; k{
m = findMinLoc(x, k, size);
temp = a[k];
a[k] = a[m];
a[m] = temp;
}
}

Selection Sort - Example


-17
12
-5
6
142
21
3
45
x:
3
12
-5
6
142
21
-17
45
x:
-17
-5
12
6
142
21
3
45
x:
-17
-5
3
6
142
21
12
45
x:
-17
-5
3
6
142
21
12
45
x:
-17
-5
3
6
12
21
142
45
x:
-17
-5
3
6
12
21
45
142
x:
-17
-5
3
6
21
142
45
x:
12
-17
-5
3
6
12
21
45
142
x:

Bubble Sort

Bubble Sort


Saralash jarayoni bir necha o'tishda davom etadi.
Har bir o'tishda biz qo'shni juftlarni solishtirishda davom etamiz va agar tartibsizlik bo'lsa, ularni almashtiramiz.
Har bir o'tishda ko'rib chiqilayotgan elementlarning eng kattasi tepaga (ya'ni o'ngga) chiqadi.
Har bir qadamda eng og'ir element pastki qismga tushadi.
Quyidan yuqoriga

Bubble Sort -Misol


3
12
-5
6
72
21
-7
45
x:
Pass: 1
3
12
-5
6
72
21
-7
45
x:
3
-5
12
6
72
21
-7
45
x:
3
-5
6
12
72
21
-7
45
x:
3
-5
6
12
72
21
-7
45
x:
3
-5
6
12
21
72
-7
45
x:
3
-5
6
12
21
-7
72
45
x:
3
-5
6
12
21
-7
45
72
x:

Bubble Sort - Example


3
-5
6
12
21
-7
45
72
x:
Pass: 2
-5
3
6
12
21
-7
45
72
x:
-5
3
6
12
21
-7
45
72
x:
-5
3
6
12
21
-7
45
72
x:
-5
3
6
12
21
-7
45
72
x:
-5
3
6
12
-7
21
45
72
x:
-5
3
6
12
-7
21
45
72
x:

Bubble Sort


void swap(int *x, int *y)
{
int tmp = *x;
*x = *y;
*y = tmp;
}
void bubble_sort(int x[], int n)
{
int i,j;
for (i=n-1; i>0; i--)
for (j=0; jif (x[j] > x[j+1])
swap(&x[j],&x[j+1]);
}

Bubble Sort


int main()
{
int x[ ]={-45,89,-65,87,0,3,-23,19,56,21,76,-50};
int i;
for(i=0;i<12;i++)
printf("%d ",x[i]);
printf("\n");
bubble_sort(x,12);
for(i=0;i<12;i++)
printf("%d ",x[i]);
printf("\n");
}
Natija:
-45 89 -65 87 0 3 -23 19 56 21 76 -50
-65 -50 -45 -23 0 3 19 21 56 76 87 89
Agar siz muammolarni o'zingiz hal qilishga harakat qilsangiz, unda siz ko'p narsalarni avtomatik ravishda o'rganasiz.
Bir necha daqiqa vaqt ajrating va keyin o'qishdan zavqlaning.
Download 256,76 Kb.

Do'stlaringiz bilan baham:
1   2




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish