Programming and Data Structures

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.