Friday, May 7, 2021

Simple Selection Sort using C

 The simplest possible technique based on the principle of repeated selection makes use of “n” passes over an array elements. In the i-th pass, the i-th smallest element is selected from the given array and it is placed in the i-th position of a separate output array. The already selected element is not selected next time and in order to ensure it, a unique value is put in place of the selected element in the original array.


Simple selection sort has an O(n²) time complexity which makes inefficient for large dataset and generally performs worse than insertion sort.

Simple Selection Sort using C


Time and Space Complexity

Worst complexity: O(n²)

Average complexity: O(n²)

Best complexity: O(n²)

Space complexity: O(1)


Complete Code

The complete source code for this simple selection sort is given below:

/* 
 * File:   SimpleSelectionSort.c
 */

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

void simpleSelectionSort(int a[], int b[], int n) {
    int i = 0, j, k = 0;
    int temp = 999;
    while (i < n) {
        for (j = 0; j < n; j++) {
            if (a[j] < temp) {
                temp = a[j];
                k = j;
            }
        }
        a[k] = 999;
        b[i] = temp;
        temp = 999;
        i++;
    }
    printf("\n");
    printf("\nThe sorted array elements are given below\n");
    for (i = 0; i < n; i++) {
        printf("a[%d]=%d ", i, b[i]);
    }
}

int main() {
    int i, n = 6, b[6];
    int a[] = {15, 8, 17, 12, 38, 19};
    printf("\n:: Simple Selection Sort ::\n");
    printf("\nInput array elements\n");
    for (i = 0; i < n; i++) {
        printf("a[%d]=%d ", i, a[i]);
    }
    simpleSelectionSort(a, b, n);
}


Testing the Program

The above C program will give you the following output:

:: Simple Selection Sort ::

Input array elements
a[0]=15 a[1]=8 a[2]=17 a[3]=12 a[4]=38 a[5]=19 

The sorted array elements are given below
a[0]=8 a[1]=12 a[2]=15 a[3]=17 a[4]=19 a[5]=38



No comments:

Post a Comment