**Sorting** means arranging a set of data in an order. There’re various algorithms to sort the data (in a data structure) in increasing or decreasing order. These algorithms can be divided on basis of various factors:

**Inplace sorting****&****External sorting**

**Inplace** sorting means that all the data which is to be sorted can be accommodated at a time in memory. Examples of inplace sorting algorithms are Selection sort, Bubble sort etc. This means, it needs only O(1) extra space and have O(1) space complexity.

**External** sorting means the data that is to be sorted is partially present in memory and remaining is present in auxiliary (extra) memory. Merge sort is a good example of external sorting. Merge sort has O(n) space complexity, where n is the size of input.

**Time Complexity**

**Time Complexity** also known as *running time* of an algorithm is the number of primitive operations executed on a particular input.

Sorting algorithms like Selection sort, Insertion sort have worst case time complexity of O(n^{2}) . Whereas, algorithms like Merge sort and Heap sort have worst case time complexity of O(nlog(n)).

###### Selection sort

Selection sort is an in-place comparison sorting algorithm. It has a worst case time complexity of O(n^{2}). However, we’ve sorting algorithms like Merge sort and Heap sort which have a better time complexity ie. O(nlog(n)). But selection sort has performance advantages over above complicated algorithms in certain situations, particularly where auxiliary memory is limited.

One advantage that Selection sort has over other sorting algorithms is that it makes the minimum possible number of swaps, ie. n − 1 in the worst case, for an input of size n

**Selection sort algorithm (Pseudocode)**

Consider an integer array, arr of size n.

```
Selection sort (arr, n)
for each i = 0 to n - 2:
indexMin = i
for each j = i+1 to n-1:
if arr[j] < arr[indexMin]:
indexMin = j;
end
end
if indexMin != i:
swap arr[indexMin] and arr[i]
end
end
end
```

###### Analysis of Selection Sort

As we could understand from the pseudocode that in each iteration from i = 0 to i = n – 2, there’s only one swap, at end of the *iteration* of first *for loop* (i = 0, n-2).

At the end of the eachithiterationof the firstfor loop,ith(smallest) number is placed at theithplace.

**Code Implementation**

```
//
// main.cpp
// Selection Sort
//
// Created by Himanshu on 29/08/21.
//
#include <iostream>
using namespace std;
void printArray (int arr[], int n) {
for (int i=0; i<n; i++) {
cout<<arr[i]<<" ";
}
cout<<endl;
}
void selectionSort(int arr[], int n) {
cout<<"Initial array:"<<endl;
printArray(arr, n);
cout<<"Selection sort"<<endl;
for (int i=0; i<n-1; i++) {
int indexMin = i;
for (int j=i+1; j<n; j++) {
if (arr[j] < arr[indexMin]) {
indexMin = j;
}
}
if (indexMin != i) {
swap(arr[i], arr[indexMin]);
}
cout<<"Array after "<<(i+1)<<" iteration: "<<endl;
printArray(arr, n);
}
}
int main() {
int arr[] = {21, 15, 30, 13 , 2};
int n = 5;
selectionSort(arr, n);
return 0;
}
```

**Output**

Initial array: 21 15 30 13 2 Selection sort Array after 1 iteration: 2 15 30 13 21 Array after 2 iteration: 2 13 30 15 21 Array after 3 iteration: 2 13 15 30 21 Array after 4 iteration: 2 13 15 21 30

Here’s a working example: Selection Sort

###### Application of Selection sort

- It is very useful when
.**memory write is a costly operation** - Number of swaps (writes) can be a very important factor if writes are significantly more expensive than reads, such as with
**EEPROM or Flash memory**, where each write reduces the lifespan of the Flash memory.

## One thought on “Which sorting algorithm makes minimum number of swaps?”