In this series of tutorials, we will learn about sorting algorithms. This tutorial will focus on the selection sort sorting algorithm. We will see an example in C programming.

## Sorting Algorithms Introduction

Sorting is a concept deeply embedded in a lot of things we do. It is quite often that we like to arrange things or data in a certain order. Sometimes this is done to improve the credibility of that data or to able to extract some information quickly out of that data.

For example, if we are playing a card game. Even though the number of cards in our hand are less but we still prefer to keep our hand of cards sorted by rank or suit.

Let’s say this is our hand of cards:

We would like to sort the cards in increasing order of rank. Then, the arrangement will be something like this:

### Sorting Examples

Sorting is a really helpful feature even in our daily lives. There are so many places when we want to keep our data sorted. For example language dictionary or a sports ranking chart. In the former we want to keep the words sorted so that searching a word in the dictionary is easy. The latter shows the teams with good performance at the top of the list.

To define sorting in a formal manner: Sorting is arranging the elements in a list or collection in increasing/decreasing order of some property.

The list should be homogenous i.e. all the elements in the list should be of the same type. To study sorting algorithms, most of the time we use a list integers. Typically we sort the list of integers in increasing order of values. Lets say we have the following list of integers: 2,4,8,1,5 then sorting it in increasing order of value will be rearranging the elements like this: 1,2,4,5,8. Sorting the same list in decreasing order of value will be 8,5,4,2,1.

As we have said in the definition we can sort on any property. If we want to sort this list on the basis of increasing number of factors so the number with lesser numbers of factors will be towards the beginning of the list. 1(one factor), 2(two factors),5(2 factors),4(3 factors),8(4 factors).

A sorted list is a permutation of the original list. When we sort a list, we just rearrange the elements.

We can have a list of any data type. Let us sort a list of strings in lexicographical order (the order in which they will be found in a dictionary). For example: “hot”, “anxious”, ‘trot”, “aperture”, “cattle” will be rearranged as “anxious”, “aperture”, “cattle”, “hot”, “trot”.

### Linear Search

If a list is stored in the computer’s memory as unsorted, then to search something in this list we will have to run a linear search. In linear search we start at the first element in the list and keep scanning the whole list until we reach the element we are looking for. In the worst case, when an element will not be there in the list we will compare it with all the elements in the list. Suppose, if there are ‘n’ elements in the list, we will make ‘n’ comparisons in the worst case. If we take ‘n’ equal to 2^64 and imagine that 1 comparison takes one millisecond then we will take 2^64 milliseconds to complete the whole process. This constitutes to several years.

### Binary Search

However, if our list is sorted we can use binary search. With binary search, if the size of the list is equal to ‘n’ it will take only log₂(n) comparisons to perform a search. So if n=2^64, we will take only 64 milliseconds to complete the search in the worst case scenario.

### Sorting Algorithms

Sorting as a problem is well studied and a great deal of research has gone into devising efficient algorithms for sorting. We will analyse and compare different sorting algorithms in the upcoming tutorials. Some of the sorting algorithms include:

- Bubble Sort
- Selection Sort
- Insertion Sort
- Merge Sort
- Quick Sort
- Heap Sort
- Counting Sort
- Radix Sort

## Classification of Sorting Algorithms

We often classify sorting algorithms based on some parameters. These are briefly mentioned below:

- The first parameter that we want to classify upon is
**time complexity**. This is the measure of the rate of growth of the time taken by an algorithm with respect to input size. Some algorithms will be relatively faster than others.

- The second parameter that we use for classification is space
**complexity or memory usage**. Some sorting algorithms use a constant amount of extra memory to rearrange the elements in the list while others like merge sort use extra memory to temporarily store the data. Thus, the memory usage grows with input size.

- The third parameter is
**stability**. Suppose we have a set of cards like the ones shown below:

We want to sort these cards in increasing order of rank. We have one 5 of Hearts, one 2 of clubs, one 8 of Diamond, one 5 of spades and one 7 of spades. One permutation will be this:

The cards are sorted by increasing order of rank: 2,5,5,7 and 8 but if you see in the original list 5 of Hearts was coming earlier than 5 of Spades. In our sorted arrangement 5 of Spades has been placed before 5 of Hearts.

A stable sorting algorithm in the case of equality of key, or the property upon which we are sorting, preserves the relative order of elements. So if the key is equal. if an element was coming before in an original list it will also come before in the sorted list. A stable sorted also guarantees that.

If we will use this kind of sorting algorithm we will get this particular permutation where 5 of Hearts will be placed before 5 of Spades:

- The next parameter of classification is whether
**a sort is internal or external**. When all the records that need to be sorted are in the main memory or RAM then such a sort is known as internal sort. If the records are on the auxiliary storage like disk then such a sort is known as external sort.

- The last parameter of classification is whether the algorithm is recursive or non recursive. Some sorting algorithms like quick sort and merge sort are recursive while others like insertion sort and selection sort are non recursive in nature.

## Selection Sort Algorithm

Selection sort is one of the simplest sorting algorithm. In this algorithm, we find the minimum element from the list in every iteration and place it in the array beginning from the first index. It uses in-place sorting algorithm and has a time complexity of O(n^2). This makes it inefficient while sorting larger lists as the running time is not very fast.

### Playing Card Example

Let’s say we have a set of playing cards and we want to arrange them in increasing order of rank.

One simple thing we can do is initially keep all the cards in our left hand and then first we can select the minimum value of the card out of all the cards and move it to the right hand.

Now once again whatever card is left in the left hand, we will select the minimum from it and move it to the right hand, next to the previous cards in the right.

We can go repeating this process.

At any stage during the process, the left hand will be an unsorted set of cards and the right hand will be the sorted set of cards. In the end, the right hand will be a sorted arrangement of cards. The cards will be sorted in increasing order of rank.

## Sorting list of integers with Selection Sort

Lets see how to sort a list of integers given to us in a form of an array.

Suppose we have an array of 5 integers named X with unordered numbers. Let’s see it in memory.

To sort this list, we can do something similar to what we did with the playing cards example. We can create another array of the same size as ‘X.’ Thus, we have created another array ‘Y’ of size 5.

We can start creating ‘Y’ as a sorted list by selecting the minimum from ‘X.’ At each step there will be multiple passes on ‘X’. In the first pass, ‘1’ is the minimum so 1 will go at index 0 in Y. There should be a way to mark that 1 has already been selected so it is not considered again. One way to do this can be by replacing the selected element by some very large integer that is guaranteed to be the maximum in the array in each step. We can choose this MAX to be something like the largest possible value in a 32 bit integer.

Now we will scan ‘X’ again for the second largest element that will go the index 1 in ‘Y’. That element is ‘2’. ‘2’ again will be replaced by MAX and shifted to array ‘Y.’

Now the minimum in ‘X’ is ‘3’ and we will keep on doing this until all the positions in ‘Y’ are filled.

In the end we can copy the contents of ‘Y’ back to ‘X’ so ‘X’ itself will become a sorted arrangement of its initial elements

This logic will work fine. But there is a disadvantage. There is this extra memory requirement for the auxiliary array ‘Y’ that we are creating. Larger the size of ‘X’, larger is the extra memory required for the creation of this temporary array ‘Y.’ So this is not an in-place sorting algorithm. An in-place sorting algorithm takes constant amount of extra memory for sorting a collection. In this case, the amount of extra memory will be proportional to the size of the input array in our case ‘X.’

## In-place Sorting Algorithm

We can do something similar where we will select the minimum element at each step but we will not have to use this extra array ‘Y.’ The algorithm will then be in-place.

This time again we will look for the minimum value in the array to sort it in increasing order of rank.

First, we will scan the whole array to find the minimum. The minimum in the array is ‘1’. Now instead of filling ‘1’ at index 0 at another array ‘Y,’ we will swap ‘1’ with the element at index 0. ‘1’ will move to index 0 and the value at index 0 which is ‘4’ will move to index 1.

Now we will look for the next minimum value. ‘1’ will not be considered in this case. We will scan all the elements from index 1 to index 4 in order to find the second minimum. It is ‘2’ at index 3. Now ‘2’ will be placed at index 1 by swapping ‘2’ with the element at index 1 which is ‘4’.

So the second minimum went at the second position which is index 1. Now we have to look for the next minimum value in from index 2 to index 4 which is ‘3’. It is found at index 4. So it will be placed at index 2 by swapping ‘3’ with the element at index 2 which is ‘5’.

As you can see in each pass we are finding out the element that should go to a particular position. At any point during this whole process, the array is divided into two parts. One part is sorted and the other is un-sorted. With each pass we add one more cell to the sorted part. Eventually, the whole array will be sorted.

If we have ‘n’ elements, after ‘n-1’ passes we will have one more cell left but it will be ta its appropriate position.

This particular in-place logic of selecting the minimum in each pass and putting it at its appropriate position is ‘Selection Sort Algorithm.’

## Selection Sort Example Code in C and C++

Now let us look at a C++ program where we will sort the same array as in the above example using selection sort.

```
#include <iostream>
using namespace std;
void SelectionSort(int X[],int n)
{
for(int i=0;i< n-1;i++){
int iMin = i;
for(int j= i+1;j<n;j++){
if (X[j] < X[iMin])
iMin = j;
}
int y = X[i];
X[i] = X[iMin];
X[iMin] = y;
}
}
int main(){
int X[] ={4,1,5,2,3};
SelectionSort(X,5);
for(int i=0; i<5;i++){
cout<<X[i]<<" ";
}
}
```

```
#include <stdio.h>
void SelectionSort(int X[],int n)
{
for(int i=0;i< n-1;i++){
int iMin = i;
for(int j= i+1;j<n;j++){
if (X[j] < X[iMin])
iMin = j;
}
int y = X[i];
X[i] = X[iMin];
X[iMin] = y;
}
}
int main(){
int X[] ={4,1,5,2,3};
SelectionSort(X,5);
for(int i=0; i<5;i++){
printf("%d", X[i]);
}
}
```

### How the Code Works?

In the main() method, we have created an array ‘X’ of five elements. We are calling the SelectionSort() function and passing the array and the number of elements as arguments inside it. Then we will print the elements as the output.

```
int main(){
int X[] ={4,1,5,2,3};
SelectionSort(X,5);
for(int i=0; i<5;i++){
cout<<X[i]<<" ";
}
```

We will write a function named SelectionSort() that will take the array and the number of elements in the array as arguments. We will run one loop with a variable ‘i’ starting zero all the way till (n-1). In each iteration of this loop we will set the element at i-th position appropriately. First, we will put the minimum at index 0 then we will put the second minimum at index 1 and so on. In fact we only need to run this loop till (n-2). This is because once we are done with all ‘i’s’ till (n-2), the element at position (n-1) will anyway be appropriate at the correct position.

```
void SelectionSort(int X[],int n)
{
for(int i=0;i< n-1;i++){
int iMin = i;
for(int j= i+1;j<n;j++){
if (X[j] < X[iMin])
iMin = j;
}
int y = X[i];
X[i] = X[iMin];
X[iMin] = y;
}
}
```

Inside the next, for() loop we will have another variable ‘j’ that will store the index of the minimum element. For i-th element to find the minimum, we will scan the array from i till (n-1). Initially, the i-th element is the minimum element then after running the loop from (i+1) till (n-1) and while scanning if we find any ‘j’ that is having an element lesser than the current minimum we will update this particular variable iMin. When we will come out of this second for loop, iMin will have the index of the minimum element. Now we will have to swap it with element at i-th index. We will do so by using a temporary variable ‘y’.

### Output

Now let’s see the code output. After the compilation of the above code, you will get the following output.

As you will see our numbers have been sorted in increasing values.

### Time Complexity

The time complexity of selection sort is O(n^2). The running time is the total running time of all the statements.

Lets say this particular statement will take C1 constant time in worst case to execute. It will be executed exactly (n-1) times.

` int iMin = i;`

The next statements in the for loop will take at max C2 to execute:

```
if (X[j] < X[iMin])
iMin = j;
```

Also, the last three statements will take C3 time in the worst case. It will be executed exactly (n-1) times.

```
int y = X[i];
X[i] = X[iMin];
X[iMin] = y;
```

Overall time taken can be calculated below as:

```
T(n) = (n-1)C1 + [n(n-1)]C2/2 + (n-1)C3
= an^2 + bn + c
```

It belongs to the set O(n^2).

Selection sort has a slow performance as O(n^2) is not one of the best running time for a sorting algorithm.