Selection Sort

In each iteration of the selection sort algorithm, the smallest item from an unsorted list is chosen and placed at the top of the unsorted list.

Algorithm of Selection Sorting

In order to sort an array of n elements in increasing order, use the following commands:

selectionSort(array, size)
  repeat (size - 1) times
  set the first unsorted element as the minimum
  for each of the unsorted elements
    if element < currentMinimum
      set element as new minimum
  swap minimum with first unsorted position
end selectionSort

How Selection Sort Works?

Assume we're attempting to organise the components ascending.

• Consider the first element the smallest.

• Compare the first and second elements. If the next element is less than the minimum, it should be the minimum.   Compare the third element to the minimum. If the third element is lesser, assign the minimum value to it; otherwise, do nothing. The process continues until the final element is added.

• Minimum is moved to the front of the unsorted list after each iteration.

• Indexing begins with the first unsorted element in each iteration. Steps 1–3 are repeated until all of the elements are in their proper places.

Code for Selection Sort in C

// Selection sort in C


#include <stdio.h>


// function to swap the the position of two elements
void swap(int *a, int *b) {
  int temp = *a;
  *a = *b;
  *b = temp;
}


void selectionSort(int array[], int size) {
  for (int step = 0; step < size - 1; step++) {
    int min_idx = step;
    for (int i = step + 1; i < size; i++) {


      // To sort in descending order, change > to < in this line.
      // Select the minimum element in each loop.
      if (array[i] < array[min_idx])
        min_idx = i;
    }


    // put min at the correct position
    swap(&array[min_idx], &array[step]);
  }
}


// function to print an array
void printArray(int array[], int size) {
  for (int i = 0; i < size; ++i) {
    printf("%d  ", array[i]);
  }
  printf("\n");
}


// driver code
int main() {
  int data[] = {20, 12, 10, 15, 2};
  int size = sizeof(data) / sizeof(data[0]);
  selectionSort(data, size);
  printf("Sorted array in Acsending Order:\n");
  printArray(data, size);
}

The following output should be generated by this programme:

Output

Array Sorted in Ascending Order:
-12 -9 0 17 46

Complexity for Selection Sort

Detail-oriented complexity

The nearby components are compared in Selection Sort.

As a result, the number of iterations is:

( n-1 ) + ( n-2 ) + ( n-3 ) + ..... + 1 = n ( n-1 ) / 2

That almost equals n²

As a result, Complexity: O (n²)

Also, as we can see from the code, Selection sort necessitates two loops. As a result, the complexity is n*n = n².

Complexities of Time

• Complexity in the worst-case scenario: O (n²)
  • The worst case scenario happens if we wish to sort in ascending order but the array is in descending order.
• Complexity in the Best-Case Scenario: O (n)
  • When the array has already been sorted, the outer loop repeats n times, but the inner loop does not. As a result, there are only n possible comparisons. As a result, complexity follows a linear pattern.
• Case Complexity on the Average: O (n²)
  • When the items of an array are jumbled together, this happens (neither ascending nor descending).

The selection sort's time complexity is the same in all cases. At each step, you must identify the bare minimum and place it in the appropriate location. The minimum element is unknown until the array's end has not been reached.

Complexity of Space

• Because an additional variable is utilised for swapping, the space complexity is O(1).

Applications for Selection Sorting

When using the selection sort,

• Sorting a small list is considered necessary.
• The cost of swapping is irrelevant.
• It is necessary to check all of the elements.
• In flash memory, the cost of writing to memory matters (number of writes/swaps is O(n) versus O(n²) for bubble sort).