Selection sort is noted for its simplicity, specially an in-place comparison sort. It has O(n^2) time complexity, inefficient on larger lists.
The algorithm proceeds to find out the minimum element from the list and exchanged with the left most element and similarly finds second minimum element and exchanged with the second left element and so on.
This algorithm is called selection sort because it repeatedly selects the next-smallest element and swaps it into place.
Let’s understand the algorithm through pseudo code and see the steps.
Pseudo Code:
selectionSort(array, size)
repeat (size - 1) times
set the first unsorted element as the minimum
for each of the unsorted elements
if element < currentMinimum
set element as new minimum
swap minimum with first unsorted position
end selectionSort
Algorithm Steps :
Implementation:
C
# Selection sort in C
#include <stdio.h>
// Function for swapping array
void swap(int *a, int *b)
{
int temp = *a;
*a = *b;
*b = temp;
}
void selectionSort(int array[], int size)
{
for (int step = 0; step < size - 1; step++)
{
int min_idx = step;
for (int i = step + 1; i < size; i++)
{
if (array[i] < array[min_idx])
min_idx = i;
}
swap(&array[min_idx], &array[step]);
}
}
// Function for printing array
void printArray(int array[], int size)
{
for (int i = 0; i < size; ++i)
{
printf("%d ", array[i]);
}
printf("\n");
}
int main()
{
int data[] = {2 , 11 , 5 ,2};
int size = sizeof(data) / sizeof(data[0]);
selectionSort(data, size);
printf("Selection Sort \n");
printArray(data, size);
}
Java
import java.util.Arrays;
class SelectionSort {
void selectionSort(int array[]) {
int size = array.length;
for (int step = 0; step < size - 1; step++) {
int min_idx = step;
for (int i = step + 1; i < size; i++) {
if (array[i] < array[min_idx]) {
min_idx = i;
}
}
int temp = array[step];
array[step] = array[min_idx];
array[min_idx] = temp;
}
}
public static void main(String args[]) {
int[] data = { 20, 12, 10, 15, 2 };
SelectionSort ss = new SelectionSort();
ss.selectionSort(data);
System.out.println("Selction Sort: ");
System.out.println(Arrays.toString(data));
}
}
Python
def selectionSort(array, size):
for step in range(size):
min_idx = step
for i in range(step + 1, size):
# To sort in descending order, change > to <.
if array[i] < array[min_idx]:
min_idx = i
(array[step], array[min_idx]) = (array[min_idx], array[step])
data = [2, 11, 5, 2]
size = len(data)
selectionSort(data, size)
print('Selection Sort:\n')
print(data)
C++
/* Selection sort in C++ */
#include <iostream>
using namespace std;
/* Function for swapping array position */
void swap(int *a, int *b)
{
int temp = *a;
*a = *b;
*b = temp;
}
/* Function for printing array */
void printArray(int array[], int size)
{
for (int i = 0; i < size; i++)
{
cout << array[i] << " ";
}
cout << endl;
}
void selectionSort(int array[], int size)
{
for (int step = 0; step < size - 1; step++)
{
int min_idx = step;
for (int i = step + 1; i < size; i++)
{
if (array[i] < array[min_idx])
min_idx = i;
}
swap(&array[min_idx], &array[step]);
}
}
int main()
{
int data[] = {2, 11, 5, 2};
/* Calculating size of a particular array. */
int size = sizeof(data) / sizeof(data[0]);
selectionSort(data, size);
cout << "Sorted array in Acsending Order:\n";
printArray(data, size);
}
Few Interview questions on Selection Sort:
Question-What will be the time complexity of selection sort in worst case?
Answer: The time complexity will be O(n^2) .
Question– Explain Selection Sort in layman’s term ?
Answer:
- Find the smallest element. Swap it with the first element.
- Find the second-smallest element. Swap it with the second element.
- Find the third-smallest element. Swap it with the third element.
- Repeat finding the next-smallest element, and swapping it into the correct position until the array is sorted.
That’s all I have and thanks a lot for reading. Please let me know if any corrections/suggestions. Please do share and comments if you like the post. Thanks in advance… 😉
Thanks Abhijeet Gupta for helping us to grow day by day. Abhijeet is expert in Data Structure and loves to solve competitive problems.
0 Comments