C Programming

# Selection Sort Time Complexity

Selection Sort is a kind of sorting algorithm. An unsorted list can be sorted in ascending order or in descending order. Consider the unsorted list:

55  65 35  15  85  75  25  45

If this list is sorted in ascending order, it would be:

15  25  35  45  55  65  75  85

If the list is sorted in descending order, it would be:

85  75  65  55  45  35  25  15

In this article, only sorting in ascending order is considered. Selection sort sorts by looking for small elements and swapping them with the starting elements, beginning from the smallest element, while the replaced starting elements become ascending. A list should be sorted in ascending order at the end of this process.

The article aims to determine the time complexity of the Selection Sort. The following programming is done in the C language.

## Selection Sort Algorithm

The steps for Selection Sort are as follows:

• Assume that the first element is the smallest element.
• Compare this element with the other elements to know the true smallest element.
• Swap the smallest element found with the first element.
• Repeat the previous three steps in order, excluding the first replaced element.
• Continue repeating the previous three steps, excluding the elements toward the left (lower) end that have been replaced.
• Sorting ends when the last element is reached.

There are two main operation types here, which are comparison and swapping. Moving from one element to the next is also an operation, but it takes relatively little time compared with the comparison operation or swapping operation in the Selection Sort.

## O(n2) Time Complexity

Consider the following code:

int result = 0;
for (int i=0; i<8; i++) {
for (int j=0; j<8; j++) {
result = result + 1;
}
}
printf("%i\n", result);

There is an outer and inner loop. Each loop iterates eight times. The one addition operation for both loops is the main operation and operates 64 times. 64 = 8 x 8 = 82. The output is 64.

This code is considered to have 82 main operations. If 8 is replaced by n, then the time complexity would be given as:

O(n2)

This uses the Big-O notation. The notation begins with O in uppercase, followed by parentheses. Inside the parentheses is the number of main operations for the code.

Consider the following code:

int result = 0;
for (int i=0; i<8; i++) {
for (int j=i; j<8; j++) {
result = result + 1;
}
}
printf("%i\n", result);

The outer loop iterates eight times. The inner loop iterates up to the eighth time but begins from i, which is the iteration number of the outer loop. The output is 36. The one addition operation operates 36 times and not 64 times. Well, this is still considered as O(n2) time complexity. The working of selection sort is similar to this code. In other words, the Selection Sort is considered to have O(n2) time complexity.

## Coding in C

Selection Sort will always give O(n2) time complexity. It does not matter how the elements of the array are arranged. This is because all the elements are first scanned; then the rest of the elements without the first are scanned next; scanning of the rest of the elements without the first two follows, and so on. Scanning has to be completed before swapping.

The list to sort is:

P    O    I    U    Y    T    R    E    W    Q

The C program sorts in ascending order. Essentially, the program begins with:

#include <stdio.h>

void selectioSort (char A[], int N) {
for (int i=0; i<N; i++) {
int minIndx = i;
for (int j=i+1; j<N; j++) {
if (A[j] < A[minIndx])
minIndx = j;
}
char temp = A[i]; A[i] = A[minIndx]; A[minIndx] = temp;  //swapping
}
}

The library responsible for input from the keyboard and output to the monitor is included. Then, there is the definition of the selection sort function. This function as parameters has the array(reference) with the list and the number of elements in the array.

There are two for-loops; one is nested inside the other. The outer for-loop iterates over all the elements beginning from the first. While the outer for-loop is at an index, the inner for-loop iterates over the rest of the elements, excluding the preceding element. The main operation is the comparison operation in the nested for-loop.

Swapping is done for each iteration of the outer loop just after the inner loop completes.

A suitable C main function for the program is:

int main(int argc, char **argv)
{
int n = 10;
char A[] = {'P', 'O', 'I', 'U', 'Y', 'T', 'R', 'E', 'W', 'Q'};

selectioSort(A, n);

for (int i=0; i<n; i++)
printf("%c ", A[i]);
printf("\n");

return 0;
}

The output is:

E I O P Q R T U W Y

sorted.

It begins with the declaration of the number of elements in the array. Then there is the array declaration. There are ten elements in the array. These elements are characters. So, the array declaration begins with “Char”. Next, the insertion sort function is called. The first argument of the function call is the array name. The second argument is the number of elements in the array.

A for-loop follows. This for-loop prints the sorted characters. It uses the printf() function of the stdio.h library. The first argument of this function is a string. This string is a special string but still has characters that would be printed. It also has parameters for arguments. In this case, there is only one parameter, %c. There is also only one argument, A[i]. After all the characters have been printed on one line, the next printf() function takes the output to the next line.

## Conclusion

This article discussed the steps for Selection Sort, which include assuming the first element is the smallest element, comparing this element with the rest of the elements, and knowing the true smallest element. In addition, a user needs to swap the smallest element found with the first element and repeat the previous three steps in order, excluding the first replaced element. The last steps include continuing to repeat the three steps above, excluding the elements toward the left (lower) end that have been replaced; sorting ends when the last element is reached. The time complexity for Selection Sort is O(n2).