Selection Sort

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.

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(n₂)

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.tech-faq.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

Selection Sort, 10.0 out of 10 based on 1 rating