8.7 – Sorting array elements – Selection sort

by subbu on October 28, 2013

Sorting is arranging numbers, names or entities either in ascending or descending order to improve the readability. It is so easy to search for a name if all the names are arranged in ascending order. It is an important and fundamental technique used in computing.

There are number of sorting methods used to sort entities either in ascending or descending order. Some of them are

  • Selection sort
  • Bubble sort
  • Insertion sort
  • Shell sort
  • Heap sort
  • Merge sort
  • Radix sort
  • Quick sort

Out of all these methods selection sort and bubble sort are simple, takes n2 steps to sort n elements. Say for example takes 100 (102) steps to sort 10 elements. Where as quick sort takes log2n steps to sort n elements that is, takes 3 steps to sort 10 elements. Quick sort is considered as the most efficient method of sorting, which we will discourse in other session under recursion.

Sorting is generally performed by repeatedly comparing pairs of elements and swapping those if certain criteria is met. The common logic used to swap any two elements using third variable is

temp=a[i];
a[i]=a[j];
a[j]=temp;

Selection sort:

Though it is the slowest and less efficient method of sorting, it is simple to understand for learners.

Selection sort algorithm:

Let us take an array a of n elements
The selection sort algorithm first selects the smallest element in the array x and places it at a[0]; then selects next smallest element in the array a and places at a[1]. The same procedure continues until the last element is the biggest element.

Now let us start with few elements

25      20      22      11      8        18
Selection sort pass1

Pass 0:
selection sort pass0 Here the index of minimum element is 4 (idx_min), a[idx_min]8        20      22      11      25      18

Pass 1:

selection sort pass01 Here the index of minimum element is 3 (idx_min), a[idx_min]11      22      20      25      18

Pass 2:

selection sort pass2 Here the index of minimum element is 5 (idx_min), a[idx_min]18      20      25      22

Pass 3:

selection sort pass3 Here the index of the minimum element is 5 (idx_min), a[idx_min] Here the index of the minimum element is 5 (idx_min), a[idx_min]Logic:

Selection sort operations

By observing the above procedure, we come to know that a key element must be selected for each pass from a[0] to a[n-2]. It can be done using a loop.

for(k=0;k<n-1;k++)

We need to find the index of minimum element in the remaining elements of array after the key element.
We assume that the element next to the key element is minimum and stores its index in the idx_min.

idx_min=k+1;

We continue checking for minimum element, if we find any element which is less than the minimum then its index is stored in idx_min.

for(i=k+1;i<n;i++)
   if(a[i]<a[idx_min])
       idx_min=i;

At the end of loop, the index of minimum element would be in idx_min. if the new minimum element is less than the key element (a[idx_min]<a[k]) then the elements are swapped.

if(a[idx_min]<a[k])
{
   temp=a[k];
   a[k]=a[idx_min];
   a[idx_min]=temp;
}

Putting all together:

for(k=0;k<n-1;k++)
{
   idx_min =k+1;
   for(i=k+1;i<n;i++)
     if(a[i]<a[idx_min])
         idx_min =i;
  if(a[idx_min]<a[k])
  {
    temp=a[k];
    a[k]=a[idx_min];
    a[idx_min]=temp;
  }
}

Program:

#include<stdio.h>
int main()
{
int a[50],n,i,k,temp,idx_min;
/* accepting elements into array*/
printf("How many elements?");
scanf("%d",&n);
printf("Enter %d elements:\n",n);
for(i=0;i<n;i++)
   scanf("%d",&a[i]);
/* sorting the elements */
for(k=0;k<n-1;k++)
{
  idx_min =k+1;
  for(i=k+1;i<n;i++)
     if(a[i]<a[idx_min])
        idx_min =i;
  if(a[idx_min]<a[k])
  {
     temp=a[k];
     a[k]=a[idx_min];
     a[idx_min]=temp;
  }
}
/* printing the array elements */
printf("Elements in ascending order:\n");
for(i=0;i<n;i++)
    printf("%5d",a[i]);
return 0;
}

Execution:
How many elements?5
Enter 5 elements:
25      20      22      11      8       18
Elements in ascending order:
8   11   20   22   25

Sorting array elements in descending order using Selection sort:

Algorithm need to be changed a bit to arrange the elements in descending order. Here the algorithm first selects the biggest element in the array x and places it at a[0]; then selects next biggest element in the array a and places at a[1]. The same procedure continues until the last element is the biggest element.

Program:

#include<stdio.h>
int main()
{
int a[50],n,i,k,temp,idx_max;
/* accepting elements into array*/
printf("How many elements?");
scanf("%d",&n);
printf("Enter %d elements:\n",n);
for(i=0;i<n;i++)
   scanf("%d",&a[i]);
/* sorting the elements */
for(k=0;k<n-1;k++)
{
    idx_max =k+1;
    for(i=k+1;i<n;i++)
      if(a[i]>a[idx_max])
          idx_max =i;
    if(a[idx_max]>a[k])
    {
      temp=a[k];
      a[k]=a[idx_max];
      a[idx_max]=temp;
    }
}
/* printing the array elements */
printf("Elements in descending order:\n");
for(i=0;i<n;i++)
     printf("%5d",a[i]);
return 0;
}

Execution:
How many elements?5
Enter 5 elements:
22  34  11   21   55
Elements in descending order:
55   34   22   21   11

Previous post:

Next post: