Selection sort requires (n-1) passes to sort an array. In the first pass, we find the smallest element from a[0], a[1], a[2], … a[n-1] and swap it with the first element, i.e. a[0]. In the second pass, we find the smallest element from a[1], a[2], a[3]….a[n-1] and swap it with a[1] and so on.

Pass1.

  1. Find the location loc of the smallest element in the entire array, i.e. a[0],[1],a[2]…a[n-1].
  2. Interchange a[0] & a[loc]. Then, a[0] is trivially sorted.

Pass2.

  1. Find the location loc of the smallest element in the entire array, i.e. a[1],a[2]…a[n-1].
  2. Interchange a[1] & a[loc]. Then a[0], a[1] are sorted.

Pass k.

  1. Find the location loc of the smallest element in the entire array, i.e. a[k],a[k+1],a[k+2]…a[n-1].
  2. Interchange a[k] & a[loc]. Then a[0],a[1],a[2],…a[k] are sorted.

Pass n-1.

  1. Find the location loc of the smaller of the elements a[n-2],a[n-1].
  2. Interchange a[n-2] & a[loc]. Then elements a[0],a[1],a[2]….a[n-1] are sorted.

Selection sort pass 1 Selection sort pass 2, 3, 4 Selection sort pass 5, 6

Analysis of Selection Sort

  • The first pass requires n-1 comparisons to find the location of the smallest element.
  • The second pass requires n-2 comparisons.
  • The kth pass requires n-k comparisons.
  • The last pass requires only one comparison.

Therefore, the total number of comparisons are: F(n)=(n-1)+(n-2)+……+(n-k)+…3+2+1 =n(n-1)/2 Thus, the complexity is O(n2)

Sub Algorithm to Find the Smallest Element in the Array

Smallestelement(a,n,k,loc) Here a is linear array of size n. This sub algorithm finds the location loc of smallest element among a[k-1],a[k+1],a[k+2]…a[n-1]. A temporary variable "small" is used to hold the current smallest element and j is used as the loop control variable.

Begin set small=a[k-1] set loc=k-1 for j=k to (n-1) by 1 do if(a[j]<small) then set small = a[j] set loc=j endif endfor end

Selection Sort Algorithm

Selectionsort(a,n) Here a is the linear array with n elements. This algorithm sorts elements into ascending order. It uses a temporary variable temp to facilitate the exchange of two values and variable i is used as a loop control variable

Begin for i=1 to (n-1) by 1 do call Smallestelement(a,n,I,loc) set temp=a[i-1] set a[i-1]=a[loc] set a[loc]=temp endfor end

Complete Program

.cf { font-family: Lucida Console; font-size: 9pt; color: black; background: white; } .cl { margin: 0px; } .cb1 { color: green; } .cb2 { color: blue; } .cb3 { color: maroon; }

/**
 * Selection Sort
 * http://www.byteguide.com
 */
 
#include <stdio.h>
 
void selectionsort(int [], int );
 
int main()
{
 int a[50], n, i;
 printf("How many elements do you want to create the array with?"
 "(max 50): ");
 scanf("%d", &n);
 fflush(stdout);
 puts("Enter the array elements");
 for (i=0; i<n; i++)
 scanf("%d", &a[i]);
 selectionsort(a, n);
 puts("--------Sorted Array--------");
 for (i=0; i<n; i++)
 printf("%dn", a[i]);
 printf("n");
 
 return 0;
}
 
void selectionsort(int arr[], int size)
{
 int small, pos, tmp, i, j;
 for (i=0; i<size; i++)
 {
 small = arr[i];
 pos = i;
 for (j=i+1; j<size; j++)
 {
 if (arr[j] < small)
 {
 small = arr[j];
 pos = j;
 }
 }
 tmp = arr[i];
 arr[i] = arr[pos];
 arr[pos] = tmp;
 }
}

Output

How many elements do you want to create the array with?(max 50): 6 Enter the array elements 3 67 85 89 56 44 ——–Sorted Array——– 3 44 56 67 85 89