Program 8 : Selection Sort

Sort a given set of elements using Selection Sort and determine the time required to sort n elements. Repeat the experiment for different values of n and plot a graph of the time taken versus n

Selection Sort

Find the index of the smallest element per iteration, swap it with the beginning index of that iteration.

#include <stdio.h>

void selectionSort(int arr[], int n) {
    int i, j, minIndex, temp;
    
    for (i = 0; i < n - 1; i++) {
        minIndex = i;
        
        // To Find the index of the minimum element
        for (j = i + 1; j < n; j++) {
            if ( arr[minIndex] > arr[j] )
                minIndex = j;
        }

        // Swap the found minimum element 
        // with the first unsorted element
        if (minIndex != i) {
            temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }
}

void displayArray(int arr[], int n) {
    printf("Sorted array:\n");
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

int main() {
    int arr[100], n;

    printf("Enter number of elements: ");
    scanf("%d", &n);

    printf("Enter %d elements:\n", n);
    for (int i = 0; i < n; i++)
        scanf("%d", &arr[i]);

    selectionSort(arr, n);
    displayArray(arr, n);

    return 0;
}

Making a Version which generates random array on given size

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void selectionSort(int arr[], int n) {
    // remains same
}

void displayArray(int arr[], int n) {
    // same
}

int main() {
    int arr[100], n;

    printf("Enter number of elements: ");
    scanf("%d", &n);

	srand(time(NULL));
	
    printf("Random Generated array is : \n [ ");
    for (int i = 0; i < n; i++){
        arr[i] = rand()%100;
        printf("%d ", arr[i]);
	}
	printf(" ] \n");
	
    selectionSort(arr, n);
    displayArray(arr, n);

    return 0;
}

Selection Sort: Algorithm Steps

Selection sort is a simple comparison-based sorting algorithm.

1. Start from the first element.

2. Find the smallest element in the unsorted part of the array.

3. Swap it with the first unsorted element.

4. Move the boundary of the sorted/unsorted section one element to the right.

5. Repeat until the entire array is sorted.

Example:

Given:
arr = {64, 25, 12, 22, 11}

Pass 1:

• Find minimum from index 0 to 4 → 11

• Swap 64 and 11 → {11, 25, 12, 22, 64}

Pass 2:

• Find minimum from index 1 to 4 → 12

• Swap 25 and 12 → {11, 12, 25, 22, 64}

Pass 3:

• Find minimum from index 2 to 4 → 22

• Swap 25 and 22 → {11, 12, 22, 25, 64}

Pass 4:

• Find minimum from index 3 to 4 → 25

• Already in place → no swap

Sorted array: {11, 12, 22, 25, 64}

---

Time Complexity

• Worst case: O(n²)

• Best case: O(n²)

• Not stable (can be made stable with modification)

• In-place