Selection Sort
Selection Sort
Selection sort is the simplest sorting algorithm. In selection sort is selects the smallest element from an unsorted list in each iteration and places that element at the starting of the unsorted list.
Algorithm of Selection Sort
SELECTION SORT(arr, n)
Step 1: Repeat Steps 2 and 3 for i = 0 to n-1
Step 2: CALL SMALLEST(arr, i, n, pos)
Step 3: SWAP arr[i] with arr[pos]
[END OF LOOP]
Step 4: EXIT
SMALLEST (arr, i, n, pos)
Step 1: [INITIALIZE] SET SMALL = arr[i]
Step 2: [INITIALIZE] SET pos = i
Step 3: Repeat for j = i+1 to n
if (SMALL > arr[j])
SET SMALL = arr[j]
SET pos = j
[END OF if]
[END OF LOOP]
Step 4: RETURN pos
Working of Selection sort Algorithm
Suppose the elements of array are –
Now, for the first position in the sorted array, the whole array isscanned sequentially.
12 is stored at the first position presently, after searching the whole list, it is find that 8 is the smallest value.
So, replace 12 with 8. After the first iteration, 8 appear at the first position in the sorted array.
For the second position, now present, 29 is stored, we again scanning the rest of the items of unsorted array. After scanning, we found that 12 is the second lowest element in the list it should placed at the second position.
Now, replace 29 with 12. After the second iteration, 12 appear at the second position in the sorted array. then after two iterations, the 2 smallest values are placed at the starting in a sorted way.
The same process is applied the array elements.
Now the array is completely sorted
Program for Selection Sort in C
#include <stdio.h>
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
void selectionSort(int arr[], int size) {
for (int j = 0; j < size - 1; j++) {
int min_idx = j;
for (int i = j + 1; i < j; i++) {
if (arr[i] < arr[min_idx])
min_idx = i;
}
swap(&arr[min_idx], &arr[j]);
}
}
void printArray(int arr[], int size) {
for (int i = 0; i < size; ++i) {
printf("%d ", arr[i]);
}
printf("\n");
}
int main() {
int data[] = {20, 12, 10, 15, 2};
int size = sizeof(data) / sizeof(data[0]);
selectionSort(data, size);
printf("Sorted array in Acsending Order:\n");
printArray(data, size);
}
Output
Sorted array in Acsending Order: 2 10 12 15 20
Program for Selection Sort in C++
#include <iostream>
using namespace std;
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++) {
cout << arr[i] << " ";
}
cout << endl;
}
void selectionSort(int arr[], int size) {
for (int j = 0; j < size - 1; j++) {
int min_idx = j;
for (int i = j + 1; i < size; i++) {
if (arr[i] < arr[min_idx])
min_idx = i;
}
swap(&arr[min_idx], &arr[j]);
}
}
// driver code
int main() {
int data[] = {20, 12, 10, 15, 2};
int size = sizeof(data) / sizeof(data[0]);
selectionSort(data, size);
cout << "Sorted array in Acsending Order:\n";
printArray(data, size);
}
Output
Sorted array in Acsending Order: 2 10 12 15 20
Program for Selection Sort in Python
def selectionSort(arr, size):
for step in range(size):
min_idx = j
for i in range(j + 1, size):
if array[i] < arr[min_idx]:
min_idx = i
(arr[j], arr[min_idx]) = (arr[min_idx], arr[j])
data = [-2, 45, 0, 11, -9]
size = len(data)
selectionSort(data, size)
print('Sorted Array in Ascending Order:')
print(data)
Output
Sorted Array in Ascending Order: [-9, -2, 0, 11, 45]
Program for Selection Sort in Java
import java.util.Arrays;
class SelectionSort {
void selectionSort(int arr[]) {
int size = arr.length;
for (int j = 0; j < size - 1; j++) {
int min_idx = j;
for (int i = j + 1; i < size; i++) {
if (arr[i] < arr[min_idx]) {
min_idx = i;
}
}
int temp = arr[j];
arr[j] = arr[min_idx];
arr[min_idx] = temp;
}
}
// driver code
public static void main(String args[]) {
int[] data = { 20, 12, 10, 15, 2 };
SelectionSort ss = new SelectionSort();
ss.selectionSort(data);
System.out.println("Sorted Array in Ascending Order: ");
System.out.println(Arrays.toString(data));
}
}
Output
Sorted Array in Ascending Order: [2, 10, 12, 15, 20]
Selection Sort Complexity
| Time Complexity | |
|---|---|
| Best | O(n2) |
| Worst | O(n2) |
| Average | O(n2) |
| Space Complexity | O(1) |
| Stability | No |
1. Time Complexities of selection sort
- Worst Case Complexity:
O(n2) - Best Case Complexity:
O(n2) - Average Case Complexity:
O(n2)
2. Space Complexity of selection sort
| Space Complexity | O(1) |
| Stable | YES |
Selection Sort Applications
- a small list is to be sorted
- cost of the swap does not matter
- checking of all the elements is compulsory
Read more, Bubble Sort