C++ Program Selection Sort Using Dynamic Array

Selection sort is a sorting algorithm that picks the smallest element from an unsorted list and sets it at the top of the unsorted list in each iteration. In this tutorial, we will perform a selection sort algorithm to sort an array.

Selection Sort - Basic Introduction

The concept behind the selection sort algorithm is to identify the smallest element in an array and sort it accordingly. The selection sort algorithm is an in-place comparison-based method that divides the input array into two sections: a sorted array on the left and an unsorted array on the right. Let us have a rough sketch of selection sorting:

1. Assign the minimum value to array index 0
2. Search the Smallest element input in an array
3. Swap with value at the location of minimum value
4. Increment minimum value to point next element
5. Repeat until the array is sorted

Selection Sort Algorithm

As of now, we have a rough understanding of the selection sort. Let us now have a look at the algorithm followed by the code for a better understanding:

1. Create a function Selection_Sort that takes an array as an argument
2. Create a loop with a loop variable I that counts from 0 to the length of the array – 1
3. Declare smallest with the initial value i
4. Create an inner loop with a loop variable j that counts from I + 1 up to the length of the array – 1.
5. if the elements at index j are smaller than the element at index smallest, then set smallest equal to j
6. swap the elements at indexes I and smallest
7. Print the sorted list

C++ Program of Selection Sort

As discussed above in the algorithm, let us now dive into the programming part of the Selection Sort operation influenced by the algorithm. In this program, the user can input the list by giving whitespace in the console part.

#include <iostream>
using namespace std;

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

// function to print an array
void printArray(int array[], int size) {
  for (int i = 0; i < size; i++) {
    cout << array[i] << " ";
  }
  cout << endl;
}

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]);
  }
}

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

Sorted array in Ascending Order

2 10 12 15 20

Conclusion

In this tutorial, we have performed a Selection Sort operation in python to sort an array. The selection can be used to sort the small list. The time complexity of the selection sort is O(n²⁾ and the space complexity is O(1).