Open-Source Internship opportunity by OpenGenus for programmers. Apply now.
Introduction:
Selection Sort is a simple comparison-based sorting algorithm that works by repeatedly selecting the minimum (or maximum) element from an unsorted part of the array and swapping it with the first unsorted element. In this article at OpenGenus, we will explore how to implement Selection Sort in C++ using the principles of object-oriented programming (OOP) and templates. We will define both recursive and iterative approaches to the algorithm.
Table of Contents:
- OOP Concepts
- What is Selection Sort?
- Recursive Selection Sort in C++ using Templates
- Iterative Selection Sort in C++ using Templates
- Advantages of Selection Sort
- Conclusion
- Complete Code of Selection Sort in C++ using Templates
OOP Concepts:
Before we proceed with the implementation of Selection Sort using templates, let's briefly review the OOP concepts we'll utilize:
Inheritance:
Inheritance is the process of creating a new class (subclass) from an existing class (base class). The subclass inherits the properties and methods of the base class, promoting code reuse and extensibility.
What is Selection Sort?
Selection Sort is a straightforward sorting algorithm that repeatedly selects the smallest element from the unsorted part of the array and swaps it with the first unsorted element. The sorted part of the array grows from left to right with each iteration.
Recursive Selection Sort in C++ using Templates:
To implement the recursive version of Selection Sort using templates, we can define a base class called Sort with a virtual function sortArray. The SelectionSort class will be derived from the Sort class and will override the sortArray function to implement the recursive Selection Sort algorithm.
Let's define the Sort base class with templates:
template <typename T>
class Sort {
public:
virtual void sortArray(T arr[], int size) = 0;
};
Next, let's define the SelectionSort class that inherits from the Sort base class:
template <typename T>
class SelectionSort : public Sort<T> {
private:
void swap(T& a, T& b);
int findMinIndex(T arr[], int start, int size);
public:
void sortArray(T arr[], int size) override;
};
In the SelectionSort class, we define a private swap function to swap two elements in the array and a private findMinIndex function to find the index of the minimum element from a given starting point.
Now, let's implement the recursive sortArray function in the SelectionSort class:
template <typename T>
void SelectionSort<T>::sortArray(T arr[], int size) {
if (size <= 1) {
return; // Base case: Array with 0 or 1 element is already sorted
}
int minIndex = findMinIndex(arr, 0, size);
if (minIndex != 0) {
swap(arr[0], arr[minIndex]);
}
sortArray(arr + 1, size - 1); // Recursively sort the remaining array
}
In the recursive sortArray function, we first check if the size of the array is 0 or 1, in which case the array is already sorted, and we return. Otherwise, we find the index of the minimum element from the whole array (starting at index 0) using the findMinIndex function. If the minimum element is not at the beginning, we swap it with the element at index 0.
Then, we recursively call the sortArray function on the remaining part of the array (excluding the first element), effectively sorting the array from left to right.
Iterative Selection Sort in C++ using Templates:
To implement the iterative version of Selection Sort using templates, we can define a separate class called IterativeSelectionSort that does not use inheritance.
Let's define the IterativeSelectionSort class with templates:
template <typename T>
class IterativeSelectionSort {
private:
void swap(T& a, T& b);
int findMinIndex(T arr[], int start, int size);
public:
void sortArray(T arr[], int size);
};
The IterativeSelectionSort class contains the same private swap and findMinIndex functions as the SelectionSort class.
Next, let's implement the iterative sortArray function in the IterativeSelectionSort class:
template <typename T>
void IterativeSelectionSort<T>::swap(T& a, T& b) {
T temp = a;
a = b;
b = temp;
}
template <typename T>
int IterativeSelectionSort<T>::findMinIndex(T arr[], int start, int size) {
int minIndex = start;
for (int i = start + 1; i < size; ++i) {
if (arr[i] < arr[minIndex]) {
minIndex = i;
}
}
return minIndex;
}
template <typename T>
void IterativeSelectionSort<T>::sortArray(T arr[], int size) {
for (int i = 0; i < size - 1; ++i) {
int minIndex = findMinIndex(arr, i, size);
if (minIndex != i) {
swap(arr[i], arr[minIndex]);
}
}
}
In the iterative sortArray function, we use a for loop to iterate over the array. In each iteration, we find the index of the minimum element from the unsorted part of the array (starting at the current index i) using the findMinIndex function. If the minimum element is not at the current index i, we swap it with the element at index i.
Advantages of Selection Sort:
- Simplicity: Selection Sort is easy to understand and implement, making it suitable for small arrays and educational purposes.
- Space Efficiency: Selection Sort performs sorting in-place, meaning it does not require additional memory for sorting.
- Stable: Selection Sort is a stable sorting algorithm, preserving the relative order of equal elements.
Conclusion:
Selection Sort is a straightforward sorting algorithm that works well for small datasets and when the extra memory is limited. In this article, we explored how to implement Selection Sort in C++ using the principles of object-oriented programming (OOP) and templates. We defined both recursive and iterative approaches to the algorithm, providing code snippets and explanations for each.
Complete Code of Selection Sort in C++ using Templates:
#include <iostream>
template <typename T>
class Sort {
public:
virtual void sortArray(T arr[], int size) = 0;
};
template <typename T>
class SelectionSort : public Sort<T> {
private:
void swap(T& a, T& b);
int findMinIndex(T arr[], int start, int size);
public:
void sortArray(T arr[], int size) override;
};
template <typename T>
void SelectionSort<T>::swap(T& a, T& b) {
T temp = a;
a = b;
b = temp;
}
template <typename T>
int SelectionSort<T>::findMinIndex(T arr[], int start, int size) {
int minIndex = start;
for (int i = start + 1; i < size; ++i) {
if (arr[i] < arr[minIndex]) {
minIndex = i;
}
}
return minIndex;
}
template <typename T>
void SelectionSort<T>::sortArray(T arr[], int size) {
if (size <= 1) {
return; // Base case: Array with 0 or 1 element is already sorted
}
int minIndex = findMinIndex(arr, 0, size);
if (minIndex != 0) {
swap(arr[0], arr[minIndex]);
}
sortArray(arr + 1, size - 1); // Recursively sort the remaining array
}
template <typename T>
class IterativeSelectionSort {
private:
void swap(T& a, T& b);
int findMinIndex(T arr[], int start, int size);
public:
void sortArray(T arr[], int size);
};
template <typename T>
void IterativeSelectionSort<T>::swap(T& a, T& b) {
T temp = a;
a = b;
b = temp;
}
template <typename T>
int IterativeSelectionSort<T>::findMinIndex(T arr[], int start, int size) {
int minIndex = start;
for (int i = start + 1; i < size; ++i) {
if (arr[i] < arr[minIndex]) {
minIndex = i;
}
}
return minIndex;
}
template <typename T>
void IterativeSelectionSort<T>::sortArray(T arr[], int size) {
for (int i = 0; i < size - 1; ++i) {
int minIndex = findMinIndex(arr, i, size);
if (minIndex != i) {
swap(arr[i], arr[minIndex]);
}
}
}
int main() {
// Test the recursive Selection Sort
int arr1[] = {64, 34, 25, 12, 22, 11, 90};
int size1 = sizeof(arr1) / sizeof(arr1[0]);
SelectionSort<int> selectionSortRecursive;
selectionSortRecursive.sortArray(arr1, size1);
std::cout << "Recursive Selection Sort: ";
for (int i = 0; i < size1; ++i) {
std::cout << arr1[i] << " ";
}
std::cout << std::endl;
// Test the iterative Selection Sort
int arr2[] = {64, 34, 25, 12, 22, 11, 90};
int size2 = sizeof(arr2) / sizeof(arr2[0]);
IterativeSelectionSort<int> selectionSortIterative;
selectionSortIterative.sortArray(arr2, size2);
std::cout << "Iterative Selection Sort: ";
for (int i = 0; i < size2; ++i) {
std::cout << arr2[i] << " ";
}
std::cout << std::endl;
return 0;
}
In this complete code, we test both the recursive and iterative Selection Sort implementations on integer arrays. We create instances of SelectionSort and IterativeSelectionSort with int as the template parameter and call the sortArray function to sort the arrays. The sorted arrays are then printed to the console.
