Selection Sort Algorithm in C

Selection Sort Algorithm in C

12 mins read1.6K Views Comment
clickHere
Esha
Esha Gupta
Associate Senior Executive
Updated on Mar 27, 2024 18:56 IST

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!

2022_01_Copy-of-Blue-Abstract-Modern-Productive-Project-Analytics-Presentation-1.jpg

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

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

2023_10_Selection-Sort.jpg

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.

Sorting Algorithms in Java
Sorting Algorithms in Java
Sorting is the process of putting a list, a sequence of provided items, or data collection into a specific order. In this article, we will discuss different sorting algorithms in...read more
Bucket Sort Algorithm: Use and Comparison
Bucket Sort Algorithm: Use and Comparison
Bucket sort refers to a sorting algorithm that works by distributing elements of an array into several buckets. Every bucket is sorted individually, either using a different sorting algorithm or...read more
Bubble Sort Algorithm (With Code)
Bubble Sort Algorithm (With Code)
In today’s world of continuous data generation, it is of utmost importance for all businesses to sort data linearly and attain relationships on the same. With different types...read more

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");
}
Copy 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(n2)

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(n2) 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(n2)

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


 
#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 price
void 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;
}
Copy 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!

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.

About the Author
author-image
Esha Gupta
Associate Senior Executive

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