Friday, May 7, 2021

Straight Selection Sort using C

 Selection sorting refers to a class of algorithms for sorting a list of items using comparisons. These algorithms select successively smaller or larger items from the list and add them to the output sequence. This is an improvement of the Simple Selection Sort and it is called Straight Selection Sort. Therefore, instead of replacing the selected element by a unique value in the i-th pass (as happens in Simple Selection Sort), the selected element is exchanged with the i-th element.

Straight Selection Sort using C

Let’s assume an array “a” with “n” elements. Thus, at the beginning of the i-th pass, the first (i-1) elements of the array are those that have been selected in the previous passes. The smallest element is now searched in the remaining (n-i+1) elements. After (n-1) passes, the sorted array is completely developed in the space occupied by the original array.


The time complexity of this algorithm is O(n^2).


The complete source code of this algorithm is given below:

/* 
 * File:   StraightSelectionSort.c
  */

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

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

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


Testing the Program

Running the above program will give you the following output:

:: Straight 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