Selection Sort in Depth

This chapter discusses selection sort in depth. The chapter Selection Sort discussed about basic concepts of the selection sort.

Selection Sort C Code

#include <stdio.h>
#include <stdbool.h>
#define MAX 7

int intArray[MAX] = {4,6,3,2,1,9,7};

void printline(int count) {
   int i;
	
   for(i = 0;i < count-1;i++) {
      printf("=");
   }
	
   printf("=\n");
}

void display() {
   int i;
   printf("[");
	
   // navigate through all items 
   for(i = 0;i < MAX;i++) {
      printf("%d ", intArray[i]);
   }
	
   printf("]\n");
}

void selectionSort() {
   int indexMin,i,j;
	
   // loop through all numbers 
   for(i = 0; i < MAX-1; i++) { 
	
      // set current element as minimum 
      indexMin = i;
		
      // check the element to be minimum 
      for(j = i+1;j < MAX;j++) {
         if(intArray[j] < intArray[indexMin]) {
            indexMin = j;
         }
      }

      if(indexMin != i) {
         printf("Items swapped: [ %d, %d ]\n" , intArray[i], intArray[indexMin]); 
			
         // swap the numbers 
         int temp = intArray[indexMin];
         intArray[indexMin] = intArray[i];
         intArray[i] = temp;
      }          

      printf("Iteration %d#:",(i+1));
      display();
   }
}  

void main() {
   printf("Input Array: ");
   display();
   printline(50);
   selectionSort();
   printf("Output Array: ");
   display();
   printline(50);
}

Output

Input Array: [4 6 3 2 1 9 7 ]
==================================================
Items swapped: [ 4, 1 ]
Iteration 1#:[1 6 3 2 4 9 7 ]
Items swapped: [ 6, 2 ]
Iteration 2#:[1 2 3 6 4 9 7 ]
Iteration 3#:[1 2 3 6 4 9 7 ]
Items swapped: [ 6, 4 ]
Iteration 4#:[1 2 3 4 6 9 7 ]
Iteration 5#:[1 2 3 4 6 9 7 ]
Items swapped: [ 9, 7 ]
Iteration 6#:[1 2 3 4 6 7 9 ]
Output Array: [1 2 3 4 6 7 9 ]
==================================================

Selection sort is an unstable sort i.e it might change the occurrence of two similar elements in the list while sorting. But it can also work as a stable sort when it is implemented using linked list.

Another version of Selection Sort

#include <stdio.h>

// Utility function to swap values at two indices in the array
void swap(int arr[], int i, int j)
{
	int temp = arr[i];
	arr[i] = arr[j];
	arr[j] = temp;
}

// Function to perform selection sort on arr[]
void selectionSort(int arr[], int n)
{   
    int i,j; 
	// run (n - 1) times
	for (i = 0; i < n - 1; i++)
	{
		// find the minimum element in the unsorted subarray[i..n-1]
		// and swap it with arr[i]
		int min = i;

		for (j = i + 1; j < n; j++)
		{
			// if arr[j] element is less, then it is the new minimum
			if (arr[j] < arr[min])
				min = j;	// update index of min element
		}

		// swap the minimum element in subarray[i..n-1] with arr[i]
		swap(arr, min, i);
	}
}

// Function to print n elements of the array arr
void printArray(int arr[], int n)
{
	int i;
	for (i = 0; i < n; i++) {
		printf("%d ", arr[i]);
	}
}

int main(void)
{
	int arr[] = { 3, 5, 8, 4, 1, 9, -2 };
	int n = sizeof(arr) / sizeof(arr[0]);

	selectionSort(arr, n);
	printArray(arr, n);

	return 0;
}

Recursive version of Selection Sort

#include <stdio.h>

// Utility function to swap values at two indices in the array
void swap(int arr[], int i, int j)
{
	int temp = arr[i];
	arr[i] = arr[j];
	arr[j] = temp;
}

// Recursive function to perform selection sort on subarray arr[i..n-1]
void selectionSort(int arr[], int i, int n)
{
	int j;
	// find the minimum element in the unsorted subarray[i..n-1]
	// and swap it with arr[i]
	int min = i;
	for (j = i + 1; j < n; j++)
	{
		// if arr[j] element is less, then it is the new minimum
		if (arr[j] < arr[min])
			min = j;	// update index of min element
	}

	// swap the minimum element in subarray[i..n-1] with arr[i]
	swap(arr, min, i);

	if (i + 1 < n) {
		selectionSort(arr, i + 1, n);
	}
}

// Function to print n elements of the array arr
void printArray(int arr[], int n)
{
	int i;
	for (i = 0; i < n; i++) {
		printf("%d ", arr[i]);
	}
}

int main()
{
	int arr[] = { 3, 5, 8, 4, 1, 9, -2 };
	int n = sizeof(arr) / sizeof(arr[0]);

	selectionSort(arr, 0, n);
	printArray(arr, n);

	return 0;
}

Selection Sort using Pointer Notation

#include <stdio.h>
<stdlib.h>
int selectionsort(int *,int);

int selectionsort(int *arr,int n)
{
    int i,j,temp;

for(i=0;i < n;i++)
        for(j=i+1;j < n;j++)
        {
            if(*(arr+i) > *(arr+j))
            {
                temp=*(arr+j);
                *(arr+j)=*(arr+i);
                *(arr+i)=temp;
            }
        }
    return 0;
}
 
int main()
{
    int *arr,n,i;
    printf("Enter no. of elements\n");
    scanf("%d",&n);
    arr=(int *)malloc(n*sizeof(int));
    printf("Enter elements\n");

    for(i=0;i < n;i++)
        scanf("%d",(arr+i));

    selectionsort(arr,n);

    printf("Sorted elements are\n");
    for(i=0;i < n;i++)
        printf("%d\n",*(arr+i));

    return 0;
}

Analysis of Selection Sort

Selection sort is among the simplest of sorting techniques and it works very well for small files. It has a quite important application as each item is actually moved at the most once.

Selection sort is a simple sorting algorithm. This sorting algorithm is an in-place comparison-based algorithm in which the list is divided into two parts, the sorted part at the left end and the unsorted part at the right end. Initially, the sorted part is empty and the unsorted part is the entire list.

The smallest element is selected from the unsorted array and swapped with the leftmost element, and that element becomes a part of the sorted array. This process continues moving unsorted array boundary from one element to the right.

Section sort is a method of choice for sorting files with very large objects (records) and small keys. The worst case occurs if the array is already sorted in a descending order and we want to sort them in an ascending order.

Nonetheless, the time required by selection sort algorithm is not very sensitive to the original order of the array to be sorted: the test if A[j] < min is executed exactly the same number of times in every case.

Selection sort spends most of its time trying to find the minimum element in the unsorted part of the array. It clearly shows the similarity between Selection sort and Bubble sort.

Bubble sort selects the maximum remaining elements at each stage, but wastes some effort imparting some order to an unsorted part of the array.
Selection sort is quadratic in both the worst and the average case, and requires no extra memory.

For each i from 1 to n-1, there is one exchange and n-i comparisons, so there is a total of n-1 exchanges and

(n − 1) + (n − 2) + ...+ 2 + 1 = n(n − 1)/2 comparisons.