Selection Sort Algorithm in C++
Selection sort algorithm was developed using comparison algorithm.
This algorithm picks an element from the left-hand side and finds the smallest element on the right-hand side,
finally it swaps the smallest element to its position and it continues the process for each element with direction left to right except the last element.
But it's not an efficient on medium or large data sets.
Time Complexity
- Best complexity: n^2
- Average complexity: n^2
- Worst complexity: n^2
Selection Sort Implementation in C++
C++ Input Screen
#include <iostream>
using namespace std;
class SelectionSortExample
{
// Access specifier
public:
void selectionSort(int arr[], size_t size) {
for(size_t i = 0; i < size - 1; i++) {
int minIndex = i;
for(size_t j = i + 1; j < size; j++) {
if(arr[minIndex] > arr[j]) {
minIndex = j;
}
}
int temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
}
void printArray(const int arr[], size_t size) {
for(size_t i = 0; i < size; i++) {
cout << arr[i] << " ";
}
cout << endl;
}
};
int main(int argc, const char * argv[])
{
// Declare an object of class geeks
SelectionSortExample obj;
int arr[] = { 15, 3, 12, 6, -9, 9, 0 };
const size_t SIZE = sizeof(arr) / sizeof(*arr);
cout << "Before Sorting: ";
obj.printArray(arr, SIZE);
obj.selectionSort(arr, SIZE);
cout << "After Sorting: ";
obj.printArray(arr, SIZE);
return 0;
}
C++ Output Screen
Before Sorting: 15 3 12 6 -9 9 0
After Sorting: -9 0 3 6 9 12 15
Selection sort implementation steps:
Let's take the input array as { 15, 3, 12, 6, -9, 9, 0 } and we can see how the Selection sort is sorting the array.
- Select an index of an element from the left hand-side (i.e. initially an index 0)
- Search an index of the smallest element comparing with all other right-hand side elements with the value of the currently selected index
- Swap the value of the smallest element to the currently selected index
- Apply step 1, 2 and 3, by picking the rest of the element except the last element of an array by incrementing the index value by 1.
Selection Sort Implementation in C++ with explanation
C++ Input Screen
#include <iostream>
using namespace std;
class SelectionSortExample
{
// Access specifier
public:
void selectionSort(int arr[], size_t size) {
// Loop all the element in an array except the last element
for(size_t i = 0; i < size - 1; i++) {
int minIndex = i;
// Find an index of a lowest element in the right-hand side
// corresponding to the element arr[i].
for(size_t j = i + 1; j < size; j++) {
if(arr[minIndex] > arr[j]) {
minIndex = j;
}
}
// Swap the lowest element with the current element (i.e. arr[i] <=> arr[minIndex])
int temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
}
void printArray(const int arr[], size_t size) {
// Loop the item and print each item in the console with white space seperated
for(size_t i = 0; i < size; i++) {
cout << arr[i] << " ";
}
cout << endl;
}
};
int main(int argc, const char * argv[])
{
// Declare an object of class geeks
SelectionSortExample obj;
int arr[] = { 15, 3, 12, 6, -9, 9, 0 };
const size_t SIZE = sizeof(arr) / sizeof(*arr);
cout << "Before Sorting: ";
obj.printArray(arr, SIZE);
obj.selectionSort(arr, SIZE);
cout << "After Sorting: ";
obj.printArray(arr, SIZE);
return 0;
}
C++ Output Screen
Before Sorting: 15 3 12 6 -9 9 0
After Sorting: -9 0 3 6 9 12 15
BBMINFO
