C++ Program to Implement Selection Sort
Introduction
In this C++ program, we will learn how to implement Selection Sort.
Selection Sort is a simple comparison-based sorting algorithm that repeatedly finds the
smallest element from the unsorted portion of the array and places it at the
correct position.
In each pass, the algorithm selects the smallest element from the remaining unsorted
elements and swaps it with the element at the current position.
This process continues until the entire array is sorted in ascending order.
Selection Sort is easy to understand and implement, making it useful for learning the
basic concepts of sorting algorithms.
C++ Program
#include <iostream>
using namespace std;
int main()
{
int n, arr[100];
cout << "Enter number of elements: ";
cin >> n;
cout << "Enter " << n << " elements:" << endl;
for(int i = 0; i < n; i++)
{
cin >> arr[i];
}
// Selection Sort
for(int i = 0; i < n - 1; i++)
{
int minIndex = i;
// Find the smallest element
for(int j = i + 1; j < n; j++)
{
if(arr[j] < arr[minIndex])
{
minIndex = j;
}
}
// Swap
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
cout << "Sorted Array: ";
for(int i = 0; i < n; i++)
{
cout << arr[i] << " ";
}
return 0;
}
Sample Output
Enter number of elements: 6
Enter 6 elements:
64 25 12 22 11 90
Sorted Array: 11 12 22 25 64 90
Explanation
Step 1: Declare Variables
First, we declare an integer variable n to store the number of elements
and an integer array arr[100] to store the elements.
int n, arr[100];
The array can store a maximum of 100 elements.
Step 2: Read the Number of Elements
The program asks the user to enter the number of elements.
cout << "Enter number of elements: ";
cin >> n;
For example, if the user enters 6, the program will work with six array elements.
Step 3: Read Array Elements
The program uses a for loop to read all the elements into the array.
cout << "Enter " << n << " elements:" << endl;
for(int i = 0; i < n; i++)
{
cin >> arr[i];
}
For example, the input array can be:
64 25 12 22 11 90
Step 4: Start Selection Sort
The outer loop controls the position where the smallest element should be placed.
for(int i = 0; i < n - 1; i++)
{
int minIndex = i;
The variable i represents the current position.
At the beginning of every pass, we assume that the element at index i
is the smallest element.
The variable minIndex stores the index of the smallest element found so far.
For example:
Array:
64 25 12 22 11 90
i = 0
minIndex = 0
Assume 64 is the smallest element.
Step 5: Find the Smallest Element
The inner loop checks the remaining unsorted elements to find the smallest element.
for(int j = i + 1; j < n; j++)
{
if(arr[j] < arr[minIndex])
{
minIndex = j;
}
}
The loop starts from i + 1 because the element at index
i is already considered the current minimum.
Whenever a smaller element is found, minIndex is updated.
For example:
64 25 12 22 11 90
Current minimum = 64
25 < 64 → minIndex = 1
12 < 25 → minIndex = 2
22 < 12 → No change
11 < 12 → minIndex = 4
90 < 11 → No change
Therefore, the smallest element is 11 at index 4.
Step 6: Swap the Elements
After finding the smallest element, the program swaps it with the element at the current
position.
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
For the first pass:
Before swapping:
64 25 12 22 11 90
Smallest element = 11
After swapping:
11 25 12 22 64 90
Now, the first position contains the smallest element and is considered sorted.
Step 7: Repeat the Process
The outer loop moves to the next position and repeats the same process.
Each pass places one element into its correct position.
For example:
Pass 1:
11 25 12 22 64 90
Pass 2:
11 12 25 22 64 90
Pass 3:
11 12 22 25 64 90
Pass 4:
11 12 22 25 64 90
Pass 5:
11 12 22 25 64 90
After all passes, the array is sorted in ascending order.
Step 8: Display the Sorted Array
Finally, the program uses a for loop to display the sorted array.
cout << "Sorted Array: ";
for(int i = 0; i < n; i++)
{
cout << arr[i] << " ";
}
The output will be:
Sorted Array: 11 12 22 25 64 90
Dry Run
Input
Array = {64, 25, 12, 22, 11, 90}
Selection Sort Processing
| Pass |
Current Position |
Smallest Element |
Swap |
Array After Pass |
| 1 |
0 |
11 |
64 ↔ 11 |
11 25 12 22 64 90 |
| 2 |
1 |
12 |
25 ↔ 12 |
11 12 25 22 64 90 |
| 3 |
2 |
22 |
25 ↔ 22 |
11 12 22 25 64 90 |
| 4 |
3 |
25 |
No change |
11 12 22 25 64 90 |
| 5 |
4 |
64 |
No change |
11 12 22 25 64 90 |
Final Sorted Array
| Index |
Value |
| 0 | 11 |
| 1 | 12 |
| 2 | 22 |
| 3 | 25 |
| 4 | 64 |
| 5 | 90 |
How Selection Sort Works
Selection Sort divides the array into two parts:
- Sorted portion – Elements that are already in their correct positions.
- Unsorted portion – Elements that still need to be sorted.
During every pass, the algorithm finds the smallest element from the unsorted portion
and moves it to the beginning of that portion.
For example:
64 25 12 22 11 90
↑
Sorted portion starts here
After Pass 1:
11 | 25 12 22 64 90
----------------
Unsorted portion
After Pass 2:
11 12 | 25 22 64 90
After Pass 3:
11 12 22 | 25 64 90
After Pass 4:
11 12 22 25 | 64 90
After Pass 5:
11 12 22 25 64 | 90
Finally, the complete array becomes sorted.
Time Complexity
| Case |
Time Complexity |
| Best Case |
O(n²) |
| Average Case |
O(n²) |
| Worst Case |
O(n²) |
Selection Sort always scans the remaining unsorted elements to find the minimum element.
Therefore, even if the array is already sorted, it still performs the comparisons.
Overall Time Complexity: O(n²)
Space Complexity
Selection Sort performs sorting directly inside the original array.
It uses only a few additional variables such as i,
j, minIndex, and temp.
- Array Storage: O(n)
- Extra Space: O(1)
Auxiliary Space Complexity: O(1)
Therefore, Selection Sort is an in-place sorting algorithm.
Key Points
- Selection Sort is a simple comparison-based sorting algorithm.
- It repeatedly finds the smallest element from the unsorted portion.
- The smallest element is swapped with the element at the current position.
- The array is divided into sorted and unsorted portions.
- Each pass places one element into its correct position.
- Selection Sort performs O(n²) comparisons in all cases.
- Its auxiliary space complexity is O(1).
- Selection Sort is an in-place sorting algorithm.
- It is easy to understand and implement, making it useful for beginners.
Advantages of Selection Sort
- Simple and easy to implement.
- Requires very little extra memory.
- Works directly on the original array.
- Performs a limited number of swaps compared with some other simple sorting algorithms.
- Useful for understanding the basic concept of comparison-based sorting.
Disadvantages of Selection Sort
- Its time complexity is O(n²).
- It is inefficient for large datasets.
- It performs many comparisons even when the array is already sorted.
- Faster algorithms such as Merge Sort and Quick Sort are generally preferred for large datasets.
Keywords
Selection Sort in C++, C++ Selection Sort Program, Selection Sort Algorithm,
Selection Sort Example, Selection Sort Implementation in C++, Selection Sort Dry Run,
Selection Sort Time Complexity, Selection Sort Space Complexity, Sorting Algorithms in C++,
C++ Sorting Programs, Selection Sort DSA, C++ DSA Programs, Sorting Algorithm in C++,
Selection Sort Interview Questions, C++ Coding Practice.
Conclusion
This program demonstrates how to implement Selection Sort in C++.
The algorithm repeatedly searches for the smallest element from the unsorted portion
of the array and swaps it with the element at the current position.
Selection Sort is simple to understand and requires only O(1)
auxiliary space because it sorts the elements directly within the original array.
However, its time complexity is O(n²), which makes it less suitable
for large datasets.
Although Selection Sort is not the fastest sorting algorithm, it is an important
algorithm for understanding the fundamentals of sorting and comparison-based algorithms.
Comments
Post a Comment