In previous post, I discussed about insertion sort. Now I am going to discuss about selection sort.
Selection sort is based on selection. You are given an array, you select the minimum element and place it.
For example, let us consider an array: [1,3,2,4,6,5]
In selection sort,
1. select the minimum and place it at first position: So, the minimum is 1, now array looks like:
1 3,2,4,6,5
2. select the minimum and place it at the second position. The minimum is 2, now array will look like:
1,2 3,4,6,5
On each step, add the minimum element to the sorted array.
In this you keep on going and finally get the whole array sorted.
The heart of selection sort is:
int min_index = i;
for (int j = i; j < n; ++j)
{
if ( array[min_index] > array[j] )
{
min_index = j;
}
}
if ( i != min_index )
{
int temp = array[i];
array[i] = array[min_index];
array[min_index] = temp;
}
The whole program is:
#include <stdio.h>
int main(int argc, char const *argv[])
{
int array[] = {1,2,3,4,10,123,1,8,9};
int n = 9;
for (int i = 0; i < n; ++i)
{
int min_index = i;
for (int j = i; j < n; ++j)
{
if ( array[min_index] > array[j] )
{
min_index = j;
}
}
if ( i != min_index )
{
int temp = array[i];
array[i] = array[min_index];
array[min_index] = temp;
}
}
for (int i = 0; i < n; ++i)
{
printf("%d\n", array[i]);
}
return 0;
}
Time complexity:
1. Worst case: O(n*n)
2. Best case: O(n), when array is already sorted. We don't have to swap elements in this case.
Selection sort is based on selection. You are given an array, you select the minimum element and place it.
For example, let us consider an array: [1,3,2,4,6,5]
In selection sort,
1. select the minimum and place it at first position: So, the minimum is 1, now array looks like:
1 3,2,4,6,5
2. select the minimum and place it at the second position. The minimum is 2, now array will look like:
1,2 3,4,6,5
On each step, add the minimum element to the sorted array.
In this you keep on going and finally get the whole array sorted.
The heart of selection sort is:
int min_index = i;
for (int j = i; j < n; ++j)
{
if ( array[min_index] > array[j] )
{
min_index = j;
}
}
if ( i != min_index )
{
int temp = array[i];
array[i] = array[min_index];
array[min_index] = temp;
}
The whole program is:
#include <stdio.h>
int main(int argc, char const *argv[])
{
int array[] = {1,2,3,4,10,123,1,8,9};
int n = 9;
for (int i = 0; i < n; ++i)
{
int min_index = i;
for (int j = i; j < n; ++j)
{
if ( array[min_index] > array[j] )
{
min_index = j;
}
}
if ( i != min_index )
{
int temp = array[i];
array[i] = array[min_index];
array[min_index] = temp;
}
}
for (int i = 0; i < n; ++i)
{
printf("%d\n", array[i]);
}
return 0;
}
Time complexity:
1. Worst case: O(n*n)
2. Best case: O(n), when array is already sorted. We don't have to swap elements in this case.
Comments
Post a Comment