Back to Course

0% Complete
0/0 Steps

Lesson 31 of 48
In Progress

# Selection Sort in C++

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

// 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);

// 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);

// 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);

// 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);

// 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* 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;
}
}

// Utility function to print the linked list
{
{
cout << head->data << " ";
}
cout << endl;
}

// Driver function
int main()
{

// Print the unsorted linked list
cout << "Unsorted list: ";

// Sorted list:   1 2 3 4 5