Selection Sort
A selection sort is a sorting techniqlue in which successive elements are selected in order and paced into their proper sorted positions.
By starting from the first element and using a nest of for loops, a pass through the array is made to locate the minimum value.
Once this is found, it 1s placed in the first position of the array (position 0). Then the remaining elements is made to find the
next smallest element, which is placed in the second position (position 1), and so on. Once the next to last element is
compared with the last element, all the elements have been sorted into ascending order.
The algorithm works as follows:
- Find the minimum value in the list.
- Swap it with the value in the first position.
- Repeat the above steps for the remainder of the list (starting at the second position and advancing each time).
Algorithm for Selection Sort
This algorithm sorts the array list with n elements
- Initialization,
- Set loc=o
- Repeat through step 7 while loc
- Set j=loc+1
- Repeat through step 6 while j
- If list[loc]>list[j]
- Interchange list[loc] and list[ j ]
- i=i+1
- loc=loc+1
- Exit
Efficiency of Selection Sort
In the selection sort, the first pass requires (n-1) comparisons to fix the minimum element to its location i.e. location o, the second pass requires (n-2) comparisons to fix the next minimum element to location 1, ..., kth pass requires (n-k) comparisons to fix the kth minimum element at its location (k-1) and the last pass requires only one comparison to be fixed at the last position of the array.
Therefore total number of comparisons:
f(n) = (n-1) + (n-2) + + (n-k) + + 3 + 2 + 1 = n*(n-1)/2
Thus, f(n)= O(n^2).
In case of selection sort,
Worst case complexity = Best case complexity = Average case complexity = O(n^2).
C Program For Selection Sort
#include <stdio.h>
void selection_sort(int[], int);
int main()
{
int list[100], n, i;
printf("\nHow many elements in the array:");
scanf("%d", &n);
scanf("%d", &n);
printf("\nEnter %d values to sort:", n);
for (i = 0; i < n; i++)
scanf("%d", &list[i]);
selection_sort(list, n);
printf("\nThe sorted list is:");
for (i = 0; i < n; i++)
printf("%d\t", list[i]);
return 0;
}
void selection_sort(int list[], int n)
{
int temp, loc, j;
for (loc = 0; loc < n - 1; loc++)
{
for (j = loc + 1; j < n; j++)
{
if (list[loc] > list[j])
{
temp = list[loc];
list[loc] = list[j];
list[j] = temp;
}
}
}
#include <stdio.h>
void selection_sort(int[], int);
int main()
{
int list[100], n, i;
printf("\nHow many elements in the array:");
scanf("%d", &n);
scanf("%d", &n);
printf("\nEnter %d values to sort:", n);
for (i = 0; i < n; i++)
scanf("%d", &list[i]);
selection_sort(list, n);
printf("\nThe sorted list is:");
for (i = 0; i < n; i++)
printf("%d\t", list[i]);
return 0;
}
void selection_sort(int list[], int n)
{
int temp, loc, j;
for (loc = 0; loc < n - 1; loc++)
{
for (j = loc + 1; j < n; j++)
{
if (list[loc] > list[j])
{
temp = list[loc];
list[loc] = list[j];
list[j] = temp;
}
}
}
}
Related Posts
Comments
Post a Comment
Subscribe Us and Thanks for visiting blog.