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:
- Initialization: Start with the first element as the current “minimum” (initially assuming it’s the smallest).
- 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.”
- 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).
- 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
#include <stdio.h>
void selectionSort(int arr[], int n) { int i, j; // Outer, Inner loop counters int minIndex; // Smallest element index int temp; // Swap variable
// Outer loop: up to second-last element for (i = 0; i < n - 1; i++) { minIndex = i; // Start with current index // Inner loop: find smallest in unsorted part for (j = i + 1; j < n; j++) { if (arr[j] < arr[minIndex]) { minIndex = j; // Update smallest index } } // Swap temp = arr[i]; arr[i] = arr[minIndex]; arr[minIndex] = temp; }}
int main() { int arr[] = {17, 34, 25, 49, 9}; // Initial array int n = sizeof(arr) / sizeof(arr[0]); // Array length
// Display original array printf("Original Array: "); for (int i = 0; i < n; i++) { printf("%d ", arr[i]); } printf("\n");
selectionSort(arr, n); // Sort the array
// Display sorted array printf("Sorted Array: "); for (int i = 0; i < n; i++) { printf("%d ", arr[i]); } printf("\n");}
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})
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^{2}) 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^{2})
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.
- Data Collection: Whenever a seller wants to view their products sorted by price, retrieve the prices of their listed products (a maximum of 10).
- Sorting Mechanism: Use the Selection Sort algorithm to sort these prices in ascending order.
- Display: Once sorted, display the products on the dashboard in the sorted order.
Code
#include <stdio.h>#include <string.h>
#define MAX_PRODUCTS 10
typedef struct { char name[50]; float price;} Product;
// Function to perform Selection Sort based on pricevoid selectionSort(Product products[], int n) { int i, j, minIndex; Product temp;
for (i = 0; i < n-1; i++) { minIndex = i; for (j = i+1; j < n; j++) { if (products[j].price < products[minIndex].price) { minIndex = j; } } // Swap products[i] and products[minIndex] temp = products[i]; products[i] = products[minIndex]; products[minIndex] = temp; }}
int main() { Product sellerProducts[MAX_PRODUCTS] = { {"Shirt", 1999.0}, {"Hat", 1499.0}, {"Socks", 999.0}, {"Jacket", 2499.0}, {"Jeans", 2999.0}, {"Watch", 3499.0}, {"Belt", 499.0}, {"Shoes", 1299.0}, {"Sunglasses", 4999.0}, {"Tie", 3999.0} };
printf("Products before sorting:\n"); for (int i = 0; i < MAX_PRODUCTS; i++) { printf("%s: ₹%.2f\n", sellerProducts[i].name, sellerProducts[i].price); }
// Sorting the products by price using Selection Sort selectionSort(sellerProducts, MAX_PRODUCTS);
printf("\nProducts after sorting by price:\n"); for (int i = 0; i < MAX_PRODUCTS; i++) { printf("%s: ₹%.2f\n", sellerProducts[i].name, sellerProducts[i].price); }
return 0;}
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!
FAQs
What is Selection Sort?
Selection Sort is a simple comparison-based sorting algorithm. It works by repeatedly finding the minimum element (considering ascending order) from the unsorted part of the array and moving it to the beginning. This process is repeated for all elements in the array, thereby sorting the entire list.
How does Selection Sort work in C?
In C, Selection Sort iterates through the array, and for each position, it searches the remaining part of the array to find the minimum (or maximum for descending order) value. It then swaps the found minimum value with the value in the current position. This process continues until the array is fully sorted.
Is Selection Sort efficient for large datasets?
Selection Sort has a time complexity of O(n^2), where n is the number of elements in the array. Due to this quadratic complexity, it is not considered efficient for large datasets, especially when compared to more advanced sorting algorithms like Quick Sort or Merge Sort.
Can Selection Sort be used for sorting strings in C?
Yes, Selection Sort can be adapted to sort arrays of strings in C. Instead of comparing integers or floats, you would compare string values using functions like strcmp() to determine their order. The overall algorithm structure remains the same, with adjustments made for string comparison and swapping.
What are the advantages of using Selection Sort?
Despite its simplicity and not being suitable for large datasets, Selection Sort has some advantages. It is easy to understand and implement, making it a good educational tool for learning about sorting algorithms. Additionally, it performs well on small arrays and has predictable performance, always running in O(n^2) time regardless of the input order.
Hello, world! I'm Esha Gupta, your go-to Technical Content Developer focusing on Java, Data Structures and Algorithms, and Front End Development. Alongside these specialities, I have a zest for immersing myself in v... Read Full Bio