Selection Sort is a sorting algorithm that is used to arrange elements of an array in a specific order. It is one of the most basic sorting algorithms and is often taught in courses on Data Structures and Algorithms with C++. In this article, we will discuss the Selection Sort algorithm, its time complexity, and its space complexity. We will also provide code examples to illustrate the Selection Sort algorithm in action.
What is Selection Sort?
Selection Sort is an in-place comparison sorting algorithm that runs in O(n²) time and can be used to sort elements in an array or a list. It works by selecting the smallest element in the array and swapping it with the first element. Then, it selects the second-smallest element and swaps it with the second element. This process continues until the array is sorted in ascending order.
Selection Sort in C++
Now let’s look at an example of Selection Sort in C++. The following code shows a basic implementation of the Selection Sort algorithm.
#include <iostream>
using namespace std;
// Function to sort an array using Selection Sort algorithm
void selectionSort(int array[], int size)
{
int i, j, min;
// Loop through the array
for (i = 0; i < size - 1; i++)
{
// Find the minimum element in the array
min = i;
for (j = i + 1; j < size; j++)
{
if (array[min] > array[j])
{
min = j;
}
}
// Swap the minimum element with the current element
int temp = array[i];
array[i] = array[min];
array[min] = temp;
}
}
// Driver function
int main()
{
// Array to be sorted
int array[] = {5, 2, 1, 4, 3};
// Size of the array
int size = sizeof(array) / sizeof(array[0]);
// Sort the array
selectionSort(array, size);
// Print the sorted array
for (int i = 0; i < size; i++)
cout << array[i] << " ";
return 0;
}
// Output
// 1 2 3 4 5
As we can see, the Selection Sort algorithm is fairly straightforward and easy to understand.
Time Complexity of Selection Sort
The time complexity of Selection Sort is O(n²). This means that the algorithm takes O(n²) comparisons to sort an array of n elements. The best-case time complexity of Selection Sort is also O(n²). This occurs when the array is already sorted or nearly sorted. The average-case time complexity of Selection Sort is also O(n²). This occurs when the elements in the array are distributed randomly. The worst-case time complexity of Selection Sort is also O(n²). This occurs when the array is sorted in reverse order.
Space Complexity of Selection Sort
The space complexity of Selection Sort is O(1). This means that the algorithm does not require any additional space for sorting an array of n elements.
Conclusion
In this article, we discussed Selection Sort, an in-place comparison sorting algorithm. We discussed its time complexity and space complexity, and we provided a code example to illustrate how it works. Selection Sort is a simple and straightforward algorithm that runs in O(n²) time and O(1) space.
Exercises
Write a C++ program to sort an array of 10 integers using Selection Sort.
#include <iostream>
using namespace std;
// Function to sort an array using Selection Sort algorithm
void selectionSort(int array[], int size)
{
int i, j, min;
// Loop through the array
for (i = 0; i < size - 1; i++)
{
// Find the minimum element in the array
min = i;
for (j = i + 1; j < size; j++)
{
if (array[min] > array[j])
{
min = j;
}
}
// Swap the minimum element with the current element
int temp = array[i];
array[i] = array[min];
array[min] = temp;
}
}
// Driver function
int main()
{
// Array to be sorted
int array[] = {5, 2, 6, 1, 9, 8, 3, 4, 7, 10};
// Size of the array
int size = sizeof(array) / sizeof(array[0]);
// Sort the array
selectionSort(array, size);
// Print the sorted array
for (int i = 0; i < size; i++)
cout << array[i] << " ";
return 0;
}
// Output
// 1 2 3 4 5 6 7 8 9 10
Write a C++ program to sort an array of characters using Selection Sort.
#include <iostream>
using namespace std;
// Function to sort an array using Selection Sort algorithm
void selectionSort(char array[], int size)
{
int i, j, min;
// Loop through the array
for (i = 0; i < size - 1; i++)
{
// Find the minimum element in the array
min = i;
for (j = i + 1; j < size; j++)
{
if (array[min] > array[j])
{
min = j;
}
}
// Swap the minimum element with the current element
char temp = array[i];
array[i] = array[min];
array[min] = temp;
}
}
// Driver function
int main()
{
// Array to be sorted
char array[] = {'d', 'a', 'g', 'c', 'f', 'b', 'e'};
// Size of the array
int size = sizeof(array) / sizeof(array[0]);
// Sort the array
selectionSort(array, size);
// Print the sorted array
for (int i = 0; i < size; i++)
cout << array[i] << " ";
return 0;
}
// Output
// a b c d e f g
Write a C++ program to sort an array of strings using Selection Sort.
#include <iostream>
#include <string>
using namespace std;
// Function to sort an array using Selection Sort algorithm
void selectionSort(string array[], int size)
{
int i, j, min;
// Loop through the array
for (i = 0; i < size - 1; i++)
{
// Find the minimum element in the array
min = i;
for (j = i + 1; j < size; j++)
{
if (array[min] > array[j])
{
min = j;
}
}
// Swap the minimum element with the current element
string temp = array[i];
array[i] = array[min];
array[min] = temp;
}
}
// Driver function
int main()
{
// Array to be sorted
string array[] = {"cat", "dog", "bird", "fish", "turtle"};
// Size of the array
int size = sizeof(array) / sizeof(array[0]);
// Sort the array
selectionSort(array, size);
// Print the sorted array
for (int i = 0; i < size; i++)
cout << array[i] << " ";
return 0;
}
// Output
// bird cat dog fish turtle
Write a C++ program to sort an array of floating-point numbers using Selection Sort.
#include <iostream>
using namespace std;
// Function to sort an array using Selection Sort algorithm
void selectionSort(float array[], int size)
{
int i, j, min;
// Loop through the array
for (i = 0; i < size - 1; i++)
{
// Find the minimum element in the array
min = i;
for (j = i + 1; j < size; j++)
{
if (array[min] > array[j])
{
min = j;
}
}
// Swap the minimum element with the current element
float temp = array[i];
array[i] = array[min];
array[min] = temp;
}
}
// Driver function
int main()
{
// Array to be sorted
float array[] = {3.14, 6.28, 1.41, 2.82, 5.66};
// Size of the array
int size = sizeof(array) / sizeof(array[0]);
// Sort the array
selectionSort(array, size);
// Print the sorted array
for (int i = 0; i < size; i++)
cout << array[i] << " ";
return 0;
}
// Output
// 1.41 2.82 3.14 5.66 6.28
Write a C++ program to sort a linked list using Selection Sort.
#include <iostream>
using namespace std;
// Node structure
struct node {
int data;
node* next;
};
// Function to sort a linked list using Selection Sort algorithm
node* selectionSort(node* head)
{
node* current = head;
node* min = NULL;
node* prev = NULL;
while (current != NULL)
{
// Set min and prev to current node
min = current;
prev = current;
node* search = current;
while (search != NULL)
{
// Find the minimum node in the list
if (search->data < min->data)
{
min = search;
prev = search->next;
}
search = search->next;
}
// Swap the minimum node with the current node
int temp = current->data;
current->data = min->data;
min->data = temp;
// Move current node to the next
current = current->next;
}
return head;
}
// Utility function to print the linked list
void printList(node* head)
{
while (head != NULL)
{
cout << head->data << " ";
head = head->next;
}
cout << endl;
}
// Driver function
int main()
{
// Create a linked list
node* head = NULL;
head = new node;
head->data = 5;
head->next = new node;
head->next->data = 2;
head->next->next = new node;
head->next->next->data = 1;
head->next->next->next = new node;
head->next->next->next->data = 4;
head->next->next->next->next = new node;
head->next->next->next->next->data = 3;
// Print the unsorted linked list
cout << "Unsorted list: ";
printList(head);
// Sort the linked list
head = selectionSort(head);
// Print the sorted linked list
cout << "Sorted list: ";
printList(head);
return 0;
}
// Output
// Unsorted list: 5 2 1 4 3
// Sorted list: 1 2 3 4 5