Selection sort in C is a good way to start learning algorithms and data structures. This blog post details implementing selection sort in the C programming language with a detailed example.
Sorting algorithms are used to arrange a list or an array in a sequence, i.e., in ascending or descending order. Sorting is useful in large data collections to optimize data searching. It is an in-place comparison sorting algorithm. This means that the selection sort does not require any extra temporary array to store the elements while sorting an array. Here all the comparisons and swappings take place in the array itself.
Selection sort is considered one of the prominent and straightforward sorting algorithms. Although the sorting algorithm resembles the insertion sort , its performance is even worse. The worst and best time complexity for selection sort is O(n 2 ).
For the reason mentioned above, we consider using a selection sort mostly when time complexity is not an issue and auxiliary memory are limited. The selection sort works on the idea that after the completion of each iteration, the minimum element of the array will come to its sorted position.
Selection Sort in C
To understand selection sort in C better, consider the following list of alphabets:
T e c h g e e k b u z z --------> b c e e e g h k t z z
Sorting requires the following operations:
- Comparing 2 values, and deciding which is smaller or greater. Depending on the order we want, we swap them.
- To have some systematic way or method to compare two values to see if they are out of order.
- The number of comparisons to sort the data is a common way to measure a sort procedure. It specifies the total number of times data checks occur to output a sorted array. In algorithm terms, the number of comparisons is (the length of the array-1) times to run the sorting loop.
- If values are not in the right position after comparisons, then swapping occurs. It can be a costly operation, and the total number of exchanges relates to the overall efficiency of the algorithm.
There exist many sorting algorithms to sort any given data. Let us discuss selection sort as one of these algorithms.
What is Selection Sort?
The selection sort is a repetitive comparison method to sort any list or an array. In this method, the algorithm finds the smallest element in the dataset and exchanges it with the first element.
Next, it finds the next smallest entry and exchanges it with the second entry. Thus, in this way, it keeps selecting the elements in ascending order and exchanging them with other elements, respectively, until the array is sorted.
Since the algorithm selects elements before swapping, hence, it is termed a selection sort. Before detailing the selection sort example in C, let's first know the algorithm we will use here.
Selection Sort Algorithm
SelectionSort (arr, length)
for i=0 to length do:
min_element = arr[i]
for unsorted elements of the array:
if element < min_element
set min_element = element
swap(arr[i], min_element)
return arr
Working and Detailed Example of Selection Sort in C
Here the basic idea is to find the minimum element and push it to the front by swapping. After one complete iteration of the inner loop, we get the minimum element from the array and then swap it with the position indicated by the outer loop.
Suppose we have an array: [21, 13, 11, 16, 3]. Then the length of the given array is 5, so the outer loop iterates five times, and the inner loop will only iterate for the unsorted array.
Let's see it in detail:
With the 1st iteration of Outer Loop Outer = 0
The inner loop will iterate 5 times:
[21, 13, 11, 16, 3]
Here, the minimum value is 21 after the 1st iteration.
[21, 13, 11, 16, 3]
Likewise, the minimum value is 13 after the 2nd iteration.
[21, 13, 11, 16, 3]
Now, the minimum value changes to 11 after the 3rd iteration.
[21, 13, 11, 16, 3]
Next, the minimum value remains 11 in the fourth iteration as 11<16.
[21, 13, 11, 16, 3]
Finally, in the last iteration, the minimum value is 3. The minimum value is swapped with Arr[outer_loop value] arr[0]. Swap with the index value of minimum element arr[4] with the end of Loop Outer = 0. We have an array after the first run(steps = 0) of the outer loop:
[3, 21, 13, 11, 16]
With the 2nd iteration of the outer loop (Steps = 1)
The inner loop will iterate only 4 times because 3 is already sorted:
[3, 21, 13, 11, 16]
Here, the minimum value is 21 for the inner loop's first iteration(i=1). for i= 2, min_val = 13
[3, 21, 13, 11, 16]
Now, for i= 3, min_val = 11
[3, 21, 13, 11, 16]
for i= 4, min_val = 11
[3, 21, 13, 11, 16]
Finally, swap the minimum value with Arr[outer_loop value] arr[1] after the last iteration, and swap with the index value of minimum element arr[3] with the end of Loop Outer = 1.
After the second iteration of the outer loop ends, we have the array:
[3, 11 ,21, 13, 16]
With the 3rd iteration of the outer loop (Steps = 2)
The inner loop will iterate only 3 times because [3,11] is already sorted. So, for the first iteration, i = 0, the minimum value is 21.
[3, 11,21, 13, 16]
for i = 1 , min_val= 13
[3, 11,21, 13, 16]
for i = 2, min_val= 13
[3, 11,21, 13, 16]
After 3 iterations, swap the minimum value with Arr[outer_loop value] arr[2], swap with the index value of the minimum element(13) arr[3] with the end of Loop Outer = 2. After the third iteration of the outer loop ends, we have the array:
[3, 11 ,13, 21, 16]
With the 4th iteration of the outer loop (Steps = 3)
Now, the inner loop will iterate only 2 times because [3,11, 13] is already sorted:
[3, 11 ,13, 21, 16]
Here the minimum value is 21 for the first iteration of the inner loop, i.e., i =0. For i =1, min_val = 16.
[3, 11 ,13, 21, 16]
After two iterations of the inner loop, swap the minimum value with Arr[outer_loop value] arr[3], swap with the index value of the minimum element(16) arr[4] with the end of outer loop = 3. After the fourth iteration of the outer loop ends, we have the array:
[3, 11 ,13, 16, 21]
Although the array is completely sorted, the 5th iteration will still continue as that is the number of times the outer loop is programmed to run based on the length of the original array. Thus, this increases the complexity of the algorithm.
With the 5th iteration of the outer loop (Steps = 4)
The inner loop will iterate only 1 time because [3,11, 13, 16] is already sorted:
[3, 11,13, 16, 21]
Here the minimum value is 21. Swap the minimum value with Arr[outer_loop value] arr[4], and swap with the index value of the minimum element(21) arr[4] with the end of Loop Outer = 4. Finally, the sorted array is displayed in the output as:
[3, 11, 13, 16, 21]
With a total of 5 outer loop iterations and 15 inner loop iterations, we were successfully able to sort an array of 5 elements i.e. [21, 13, 11, 16, 3]
Selection Sort in C Program
As per this program, an array of integer types sorts in ascending order using the section sort. The C code of the algorithm is given below. Let’s have a look at the selection sort in C program:
#include <stdio.h>
int main()
{
int data[100],i,n,steps,temp;
printf("Enter the number of elements of the list to be sorted: ");
scanf("%d",&n);
for(i=0;i<n;++i)
{
printf("%d. Enter element: ",i+1);
scanf("%d",&data[i]);
}
for(steps=0;steps<n;++steps)
for(i=steps+1;i<n;++i)
{
if(data[steps]>data[i])
/* To sort in descending order, change > to <. */
{
temp=data[steps];
data[steps]=data[i];
data[i]=temp;
}
}
printf("In ascending order: ");
for(i=0;i<n;++i)
printf("%d ",data[i]);
return 0;
}
Output
Enter the number of elements to be sorted: 8
Enter element: 25
Enter element: 7
Enter element: 18
Enter element: 4
Enter element: 12
Enter element: 1
Enter element: 29
Enter element: 21
In ascending order: 1 4 7 12 18 21 25 29
In the above example, we have entered the 8 elements in random order in the "data" array. On applying selection sort on the array, the condition “if(data[steps]>data[i])” compares the first two elements of the entered list.
The swapping of elements occurs if the comparison in the conditional statement evaluates to true. The loop goes to the next elements to repeat the same process until the array is sorted in ascending order. In the end, we got the sorted array in ascending order, i.e., 1 4 7 12 18 21 25 29.
Selection Sort in C++
#include <bits/stdc++.h>
using namespace std;
void applySelection(int arr[], int n)
{
int i, j, keyIndex;
for (i = 0; i < n-1; i++)
{
keyIndex = i;
for (j = i+1; j < n; j++)
if (arr[j] < arr[keyIndex])
keyIndex = j;
swap(arr[keyIndex], arr[i]);
}
}
int main()
{
int arr[] = {1, 2, 4, 3};
int n = sizeof(arr)/sizeof(arr[0]);
applySelection(arr, n);
for (int i=0; i < n; i++)
cout<<arr[i]<<" ";
return 0;
}
Output
1 2 3 4
Selection Sort in Python
import sys
arr = [1, 2, 4, 3]
for i in range(len(arr)):
keyIndex = i
for j in range(i+1, len(arr)):
if arr[keyIndex] > arr[j]:
keyIndex = j
arr[i], arr[keyIndex] = arr[keyIndex], arr[i]
for i in range(len(arr)):
print(arr[i], end=" ")
Output
1 2 3 4
Advantages and Disadvantages of Selection Sort
In a classroom, when the class teacher arranges all students according to their heights, in ascending order, they tend to stand in a row. The teacher then starts comparing 2 students for their heights. When they find the taller one, they exchange their places with each other and repeat the same process with the remaining students.
Finally, when the process is repeated with all students, they get them in a row according to their heights, in ascending order. This is the best example of a selection sorting algorithm.
Advantages
- It is the easiest sorting algorithm to start and implement.
- The algorithm is best for small data collection.
- Selection sort is an in-place sorting algorithm; therefore, it doesn’t require extra space in memory to hold the original list or array.
- This sorting algorithm does not depend on the initial arrangements of the data. This means it doesn't matter if we pass a sorted or unsorted array in the selection sort. It will take the same time to evaluate the array and return the result.
Disadvantages
- A major disadvantage of the selection sort algorithm is that it is not efficient for large volumes of data or bigger lists, or an array with many numbers.
- To sort n number of elements of a list requires an n-squared number of steps.
- Data moves are costly in the selection sort.
- Selection sort performs all n comparisons for the sorted input data.
Selection Sort Time Complexity
| Best Time Complexity | O(n 2 ) |
| Average Time Complexity | O(n 2 ) |
| Worse Time Complexity | O(n 2 ) |
Here n represents the total number of elements present in the array.
Conclusion
That sums up this article on selection sort in C. The selection sort is an in-place and stable sorting algorithm but is generally inefficient with large data sets. It divides the array into two parts, namely sorted and unsorted array. With each complete iteration of the child loop, the minimum element of the array gets sorted.
The time complexity of the algorithm is the same for every test case. It does not matter whether you pass a sorted or an unsorted array. The algorithm takes equal time to give the result.
People are also reading: