Selection Sort Algorithm in C

Ever wondered how your favourite music app arranges songs from least to most played or how an online store lists products from cheapest to priciest? At the heart of such operations are sorting algorithms – systematic methods computers use to order data in specific sequences. In this blog, we will understand about selection sort in c!

Sorting algorithms are fundamental algorithms in computer science designed to arrange data in a particular order. The order can be numerical (ascending or descending) or lexicographical. There are several sorting algorithms, each with its advantages, disadvantages, and use cases. Some of the most commonly studied sorting algorithms include bubble sort, insertion sort, selection sort, merge sort, quick sort, heap sort, etc.

Let’s see selection sort algorithm in detail

Table of Content

• What is Selection Sort
• Algorithm of Selection Sort
• Basic concept and working principle
• Implementation of Selection Sort in C
• Complexity Analysis of Selection Sort
• Real-world Example of Selection Sort in C
• Advantages and Disadvantages

What is Selection Sort

Selection Sort is a simple comparison-based sorting algorithm. Its primary idea is to divide the input list into two parts: a sorted sublist and an unsorted sublist. Initially, the sorted sublist is empty, and the unsorted sublist contains all the elements. The algorithm repeatedly selects the smallest (or largest, depending on the sorting order) element from the unsorted sublist and moves it to the end of the sorted sublist. This process continues until the unsorted sublist is empty and the sorted sublist contains all the elements in the desired order.

Algorithm of Selection Sort

Step 1 − Set MIN to location 0
Step 2 − Search the minimum element in the list
Step 3 − Swap with value at location MIN
Step 4 − Increment MIN to point to next element
Step 5 − Repeat until list is sorted

Basic concept and working principle

Let’s see the basic working and principles of the selection sort algorithm using your example array: arr[] = {17, 34, 25, 49, 09}

Selection Sort Working Principle:

1. Initialization: Start with the first element as the current “minimum” (initially assuming it’s the smallest).
2. Search for Minimum: Iterate through the remaining unsorted elements, comparing each one with the current “minimum.” If you find a smaller element, update the current “minimum.”
3. Swap: After completing the iteration and finding the actual minimum among the unsorted elements, swap it with the first unsorted element (the one you started with).
4. Repeat: Repeat steps 1-3 for the next unsorted element, then the next, until the entire array is sorted.

Here’s how selection sort works step-by-step for your array

Let’s consider this pseudocode snippet

procedure selectionSort(arr: array of integer, n: integer)
    declare i, j, minIndex, temp: integer

    for i = 0 to n - 1 do
        minIndex = i
        for j = i + 1 to n - 1 do
            if arr[j] < arr[minIndex] then
                minIndex = j
            end if
        end for
        
        temp = arr[i]
        arr[i] = arr[minIndex]
        arr[minIndex] = temp
    end for
end procedure

Now, from the above pseudocode, let’s understand the algorithm step by step.

Step 0: Consider the Initial Array

arr[] = {17, 34, 25, 49, 09} 

The entire array is currently unsorted. The sorted portion is empty.

Step 1: 1st Iteration

Find the smallest element in the entire array and swap it with the first position.

Dry run

i	j	minIndex	arr[]	Comparison (arr[i] vs arr[j])	Swap?	Updated Array
0	1	0	[17, 34, 25, 49, 9]	17 < 34	No	[17, 34, 25, 49, 9]
0	2	0	[17, 34, 25, 49, 9]	17 < 25	No	[17, 34, 25, 49, 9]
0	3	0	[17, 34, 25, 49, 9]	17 < 49	No	[17, 34, 25, 49, 9]
0	4	4	[17, 34, 25, 49, 9]	17 > 9	Yes	[9, 34, 25, 49, 17]

arr[] = {09, 34, 25, 49, 17}

The first element, 09 is now in its correct position, and the array is divided into a sorted portion {09} and an unsorted portion {34, 25, 49, 17}.

Step 2: 2nd Iteration

Find the smallest element in the remaining unsorted portion {34, 25, 49, 17} and swap it with the second position.

Dry run

i	j	minIndex	arr[]	Comparison (arr[i] vs arr[j])	Swap?	Updated Array
1	2	1	[9, 34, 25, 49, 17]	34 > 25	No	[9, 34, 25, 49, 17]
1	3	1	[9, 34, 25, 49, 17]	34 < 49	No	[9, 34, 25, 49, 17]
1	4	4	[9, 34, 25, 49, 17]	34 > 17	Yes	[9, 17, 25, 49, 34]

arr[] = {09, 17, 25, 49, 34}

Here, sorted portion is {09,17} and unsorted portion is {25,49,34}

Step 3: 3rd Iteration

Find the smallest element in the remaining unsorted portion {25, 49, 34} and swap it with the third position.

Dry run

i	j	minIndex	arr[]	Comparison (arr[i] vs arr[j])	Swap?	Updated Array
2	3	2	[9, 17, 25, 49, 34]	25 < 49	No	[9, 17, 25, 49, 34]
2	4	2	[9, 17, 25, 49, 34]	25 < 34	No	[9, 17, 25, 49, 34]

At the end of this iteration, element 25 is already in its correct position.

arr[] = {09, 17, 25, 49, 34}

Here, sorted portion is {09,17,25} and unsorted portion is {49,34}

Step 4: 4th Iteration

Find the smallest element in the remaining unsorted portion {49, 34} and swap it with the fourth position.

Dry run

i	j	minIndex	arr[]	Comparison (arr[i] vs arr[j])	Swap?	Updated Array
3	4	3	[9, 17, 25, 49, 34]	49 > 34	Yes	[9, 17, 25, 34, 49]

Now, after the 4th iteration, only one element remains 49, which is inherently in its correct place as it’s the last and largest element in the list.

So, at the end of the 4th iteration, the entire array is sorted in ascending order:

arr[] = {09, 17, 25, 34, 49}

That completes the selection sort for the given array.

Implementation of Selection Sort in C

Step 1: Function Declaration

The selectionSort function is declared to sort a given array.

Step 2: Outer Loop

This loop (for (i = 0; i < n – 1; i++)) traverses each element of the array, treating the current element as the boundary between the “sorted” and “unsorted” portions of the array.

The n-1 concept for the outer loop in the implementation of the Selection Sort algorithm has to do with the number of passes/iterations required to sort the array which in this case is 5-1 = 4 iterations (where, n=5)

Step 3: Assume Minimum

Within the outer loop, initially assume that the current element (i-th element) is the smallest (minIndex = i).

Step 4: Inner Loop for Minimum Search

The inner loop (for (j = i + 1; j < n; j++)) searches for the smallest element in the unsorted portion of the array. If a smaller element is found than the assumed minimum, the minIndex is updated.

Step 5: Swap

After the inner loop completes for each pass of the outer loop, the element at the minIndex (smallest in the unsorted portion) is swapped with the first element of the unsorted portion (i-th element).

Step 6: Repeat

The process continues until the outer loop has traversed the entire array, at which point the array will be sorted.

Step 7: Main Function

The main function initializes the array and its size, then calls the selectionSort function to sort the array. Before and after the sorting process, the array is printed to the console for visualization.

Code

Output

Original Array: 17 34 25 49 9 
Sorted Array: 9 17 25 34 49 

Complexity Analysis

Time Complexity

1. Best Case

This occurs when the input array is already sorted. Despite the array being sorted, the Selection Sort algorithm will still go through all its steps trying to find the smallest element in each iteration because it doesn’t have a mechanism to detect an already sorted list. Thus, the best-case time complexity is still: O(n²)

2. Average Case

For an average or random list, Selection Sort will have to go through roughly half of the list for every number. The pattern follows n + (n-1) + (n-2) + … + 2 + 1, which sums up to n(n+1)/2. This simplifies to O(n²) for large values of n.

3. Worst Case

This happens when the input list is sorted in reverse. However, the behaviour of the Selection Sort doesn’t change whether it’s a reverse sorted list or any random list. It still goes through its entire process of finding the smallest element for each iteration. Hence, the worst-case time complexity is O(n²)

Space Complexity

Selection Sort is an in-place sorting algorithm, which means it doesn’t require any additional storage (or “space”) that grows with the input size. It uses a constant amount of extra space for its variables (i, j, minIndex, temp). Hence, the space complexity is O(1)

Real-world Example of Selection Sort in C

Scenario

You’re an IT intern at a small e-commerce startup called “QuickShop.” The company is just getting started, and the website has a feature where sellers can list their products for sale. Each seller has their own dashboard where they can see all the products they’ve listed. The startup is very new, and the software is basic. Sellers have been requesting a feature to sort their products by price so that they can easily identify and modify their lowest-priced products.

However, the dashboard can display a maximum of 10 products at a time due to design constraints. As a result, the sorting operation never deals with more than 10 items for each seller.

Task

Implement a feature that allows sellers to sort and view their products in ascending order of price using the Selection Sort algorithm.

Solution

Given the constraints (sorting small lists), Selection Sort can be a reasonable choice because of its simplicity.

1. Data Collection: Whenever a seller wants to view their products sorted by price, retrieve the prices of their listed products (a maximum of 10).
2. Sorting Mechanism: Use the Selection Sort algorithm to sort these prices in ascending order.
3. Display: Once sorted, display the products on the dashboard in the sorted order.

Code

Output

Products before sorting:
Shirt: ₹1999.00
Hat: ₹1499.00
Socks: ₹999.00
Jacket: ₹2499.00
Jeans: ₹2999.00
Watch: ₹3499.00
Belt: ₹499.00
Shoes: ₹1299.00
Sunglasses: ₹4999.00
Tie: ₹3999.00

Products after sorting by price:
Belt: ₹499.00
Socks: ₹999.00
Shoes: ₹1299.00
Hat: ₹1499.00
Shirt: ₹1999.00
Jacket: ₹2499.00
Jeans: ₹2999.00
Watch: ₹3499.00
Tie: ₹3999.00
Sunglasses: ₹4999.00

This code defines a Product structure with a name and price. It then uses the Selection Sort algorithm to sort an array of these products based on their price. The main function initializes a list of sample products, displays them, sorts them by price, and then displays the sorted list.

Advantages and Disadvantages

Based on the above scenario, we can conclude the following advantages and disadvantages of our algorithm (Selection Sort)

Aspect	Advantage	Disadvantage
Number of Items to Sort	Highly efficient for small datasets like the given maximum of 10 items in the seller dashboard.	Would become inefficient if QuickShop decides to increase the number of items displayed beyond 10.
Simplicity	Given the early stage of the startup and likely limited resources, the simplicity of the algorithm is a boon.	As the platform grows, this simplicity might not cater to more complex sorting needs.
Implementation Time	Can be quickly implemented without a steep learning curve, which is crucial for a startup wanting rapid features.	Might need to be replaced with a more efficient sort if the data grows, requiring redevelopment time.
Memory Usage	Doesn’t require additional memory beyond what’s needed for the list of items, suiting a lightweight application.	No major disadvantages in this context.
User Experience	For small datasets, the sorting will be almost instantaneous, ensuring a good user experience.	If sellers were allowed to display more than 10 items, the lag might become noticeable, affecting UX.
Maintenance and Scalability	Easy to maintain given its simplicity.	As the company grows, they might need a more scalable solution than selection sort.

Thus, Selection Sort is a straightforward and intuitive sorting algorithm that operates by repeatedly selecting the smallest (or largest, depending on the order of sorting) element from an unsorted portion and swapping it with the first unsorted element. Keep Learning, Keep Exploring!