Selection Sort in C++
What is Selection Sort in C++?
Selection sort is another algorithm that is used for sorting i.e. arranging the given data in logical order. This sorting algorithm, iterates through the list and finds the smallest element in the list and swaps it with the first element. And this process is repeated until the list is sorted. In this article, we will learn more about selection sort in C++. This article also contains steps, algorithm and implementation details for the same.
| Time Complexity (Best) | Ω(n2) |
| Time Complexity (Avg) | Θ(n2) |
| Time Complexity (Worst) | O(n2) |
| Space Complexity | O(1) |
Steps for Selection Sort
There are the following Steps of the selection sort algorithm in C++.
- From the given list find the smallest element.
- Swap first element in the list with smallest element from the the list.
- Now exclude the first element and select the smallest element from the remaining list.
- Now repeat above steps till the list is sorted.
An alternate way of looking at the same algorithm
At any given point during the selection sort algorithm. The array will be divided into one sorted part and another unsorted part.
- Pick the smallest element from the unsorted part
- Swap with the first item in the unsorted part of the array
- Now we will have one more item in sorted part and one lesser item in unsorted part of the array
C++ programming code for selection sort
#include<iostream>
using namespace std;
//Display function to print values.
void display(int array[], int size)
{
int i;
for (i = 0; i < size; i++)
cout << array[i] << "\t";
cout << "\n";
}
//The main function to drive other functions.
int main()
{
int array[] = {5, 3, 1, 9, 8, 2, 4, 7};
int size = sizeof(array)/sizeof(array[0]);
cout << "Before sorting: \n";
display(array, size);
int i, j, min_idx,temp;
//Loop to iterate elements of array.
for (i = 0; i < size-1; i++)
{
//Here we try to find the min element in array.
min_idx = i;
for (j = i+1; j < size; j++){
if (array[j] < array[min_idx])
min_idx = j;
}
// Here we interchange the min element with first one.
temp = array[min_idx];
array[min_idx] = array[i];
array[i] = temp;
}
cout << "After sorting: \n";
display(array, size); //Using dispaly function to print sorted array.
return 0;
}Output
Before sorting: 5 3 1 9 8 2 4 7 After sorting: 1 2 3 4 5 7 8 9
Selection sort Highlights
Advantages
- It gives the same time complexity regardless of arrangements of items in the array or data set
- Since number of operations(swapping, size – 1) are less, so its favorable to use when swapping operations are costly in system
Disadvantages
- The time complexity is quiet high i.e. O(n2) thus not good
Time Complexity
For Selection Sort
Best
Ω(n2)
Average
Θ(n2)
Worst
O(n2)
Space Complexity
O(1)
Sorting
Sorting algorithms are easy to learn but are really important for college semester exams and companies offering package between 3 – 6 LPA would ask direct searching questions in online test/ interviews.
Sorting
Sorting algorithms are easy to learn but are really important for college semester exams and companies offering package between 3 – 6 LPA would ask direct searching questions in online test/ interviews.
Login/Signup to comment