Selection Sort in C - Naukri Code 360

Introduction

Selection sort is an easy way to organize elements in a list or array. Imagine sorting playing cards in your hand. You repeatedly pick the smallest or largest card and move it to the right spot until all cards are in order. This method divides the list into two parts: one that's sorted and one that's not. Each time, it finds the smallest (or largest) card left in the unsorted part and moves it over to the sorted part. This continues until every card is sorted, just like arranging your cards from lowest to highest.

In this article, we will discuss the algorithm, implementation, & analysis of selection sort in C programming language. We will cover the step-by-step process, with code examples, & discuss the advantages & disadvantages and various applications also.

What is Selection Sort in C?

Selection Sort is a simple comparison-based sorting algorithm. It works by repeatedly finding the minimum element from an unsorted portion of the list and swapping it with the first unsorted element. This process continues until the entire list is sorted.

Algorithm of Selection Sort in C

The selection sort algorithm follows a simple step-by-step process to sort an array of elements. Let’s see how it works:

1. Start with an unsorted array of elements.

2. Set the first element as the minimum or maximum value (depending on whether you want to sort in ascending or descending order).

3. Traverse the array from the second element to the last element.

4. Compare each element with the current minimum or maximum value.

5. If a smaller or larger element is found (depending on the sorting order), update the minimum or maximum value to that element.

6. After reaching the end of the array, swap the minimum or maximum element with the first element of the unsorted part.

7. Move the boundary of the sorted part one step forward.

8. Repeat steps 2-7 until the entire array is sorted.

The algorithm continuously selects the smallest or largest element from the unsorted part of the array & places it at the appropriate position in the sorted part. This process is repeated until all elements are in their correct sorted positions.

How to Implement Selection Sort in C?

To implement selection sort in C, follow these step-by-step instructions:

Define the Function: Start by defining a function, typically named selectionSort, which will take an array of integers and its size as parameters.
Outer Loop - Track Sorted Section: Create an outer loop that runs from the start of the array to the second last element. This loop marks the end of the sorted section after each pass.
Find Minimum Element: Within the outer loop, initialize a variable to hold the index of the minimum element, starting with the current position of the outer loop.
Inner Loop - Find Minimum Index: Initiate an inner loop starting from the current position + 1 to the end of the array. Compare each element with the current minimum; if a smaller element is found, update the minimum index.
Swap Elements: After determining the minimum index in the unsorted section, swap the element at the minimum index with the element at the current position of the outer loop, if they are not the same.
Repeat Until Array Is Sorted: The outer loop continues until the array is completely sorted.

Let’s see an example of implementation in C

#include <stdio.h>
void selectionSort(int arr[], int n) {
    int i, j, min_idx;
    // One by one move boundary of unsorted subarray
    for (i = 0; i < n-1; i++) {
        // Find the minimum element in unsorted array
        min_idx = i;
        for (j = i+1; j < n; j++)
          if (arr[j] < arr[min_idx])
            min_idx = j;
        // Swap the found minimum element with the first element
        if (min_idx != i) {
            int temp = arr[min_idx];
            arr[min_idx] = arr[i];
            arr[i] = temp;
        }
    }
}
// Function to print an array
void printArray(int arr[], int size) {
    int i;
    for (i=0; i < size; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

int main() {
    int arr[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr)/sizeof(arr[0]);
    selectionSort(arr, n);
    printf("Sorted array: \n");
    printArray(arr, n);
    return 0;
}

You can also try this code with Online C Compiler

Run Code

Output

Sorted array: 
11 12 22 25 64

How does Selection Sort Work in C?

Let’s discuss how selection sort actually works in C :

1. Finding the minimum element: The selection sort algorithm starts by finding the minimum element in the unsorted part of the array. It compares the first element with all the subsequent elements to determine the smallest value. This process is repeated for each iteration of the outer loop, gradually shrinking the unsorted part of the array.

2. Swapping the minimum element: Once the minimum element is found, it is swapped with the first element of the unsorted part. This step ensures that the minimum element is placed in its correct sorted position. After the swap, the boundary between the sorted and unsorted parts of the array is moved one step forward.

3. Repeating the process: The above steps are repeated for the remaining unsorted part of the array. In each iteration, the algorithm finds the minimum element from the unsorted part and swaps it with the first element of that part. This process continues until the entire array is sorted.

4. Sorting in ascending or descending order: Selection sort can be used to sort elements in either ascending or descending order. To sort in ascending order, the algorithm finds the minimum element in each iteration. To sort in descending order, the algorithm finds the maximum element instead.

5. In-place sorting: Selection sort is an in-place sorting algorithm, which means it does not require any additional storage space. The sorting is performed within the same array, and the elements are swapped in place. This makes selection sort memory efficient, as it does not need to allocate extra memory for the sorting process.

Now, let's take a look at an example to understand how selection sort works in C. Consider the following unsorted array:

int arr[] = {64, 25, 12, 22, 11};

1. First iteration: In the first iteration, the algorithm finds the minimum element from the entire array. It compares `64` with `25`, `12`, `22`, and `11`. The minimum element is `11`, so it is swapped with the first element `64`. After the first iteration, the array becomes:

{11, 25, 12, 22, 64}

2. Second iteration: In the second iteration, the algorithm starts from the second element and finds the minimum element from the remaining unsorted part. It compares `25` with `12`, `22`, and `64`. The minimum element is `12`, so it is swapped with the second element `25`. After the second iteration, the array becomes:

{11, 12, 25, 22, 64}

3. Third iteration: In the third iteration, the algorithm starts from the third element and finds the minimum element from the remaining unsorted part. It compares `25` with `22` and `64`. The minimum element is `22`, so it is swapped with the third element `25`. After the third iteration, the array becomes:

{11, 12, 22, 25, 64}

4. Fourth iteration: In the fourth iteration, the algorithm starts from the fourth element and finds the minimum element from the remaining unsorted part. It compares `25` with `64`. The minimum element is `25`, which is already in its correct position, so no swapping is needed. After the fourth iteration, the array remains unchanged:

{11, 12, 22, 25, 64}

After the fourth iteration, the array is fully sorted in ascending order. Selection sort has successfully arranged the elements from the smallest to the largest.

Program to Perform Selection Sort in C

#include <stdio.h>
void selectionSort(int arr[], int n) {
    int i, j, min_idx, temp;
    for (i = 0; i < n - 1; i++) {
        min_idx = i;
        for (j = i + 1; j < n; j++) {
            if (arr[j] < arr[min_idx])
                min_idx = j;
        }
        // Swap the minimum element with the first element
        temp = arr[min_idx];
        arr[min_idx] = arr[i];
        arr[i] = temp;
    }
}
void printArray(int arr[], int size) {
    int i;
    for (i = 0; i < size; i++)
        printf("%d ", arr[i]);
    printf("\n");
}
int main() {
    int arr[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Original array: \n");
    printArray(arr, n);

    selectionSort(arr, n);

    printf("Sorted array: \n");
    printArray(arr, n);

    return 0;
}

You can also try this code with Online C Compiler

Run Code

In this code :

1. The `selectionSort` function takes an integer array `arr` and its size `n` as parameters. It implements the selection sort algorithm using nested loops.

2. The outer loop `i` iterates from 0 to `n-2`, representing the unsorted portion of the array.

3. Inside the outer loop, the variable `min_idx` is initialized to `i`, assuming the first element of the unsorted portion as the minimum.

4. The inner loop `j` iterates from `i+1` to `n-1`, comparing each element with the current minimum element.

5. If an element smaller than the current minimum is found, `min_idx` is updated to the index of that element.

6. After the inner loop ends, the minimum element is swapped with the first element of the unsorted portion using a temporary variable `temp`.

7. The `printArray` function is used to print the elements of the array.

8. In the `main` function, an integer array `arr` is initialized with the values `{64, 25, 12, 22, 11}`.

9. The size of the array is calculated using the `sizeof` operator and stored in the variable `n`.

10. The original array is printed using the `printArray` function.

11. The `selectionSort` function is called with `arr` and `n` as arguments to sort the array.

12. Finally, the sorted array is printed using the `printArray` function.

Output:

Original array:
64 25 12 22 11
Sorted array:
11 12 22 25 64

Program to Perform Selection Sort in C Using For Loop

void selectionSort(int arr[], int n) {
    int i, j, min_idx, temp;
    for (i = 0; i < n - 1; i++) {
        min_idx = i;
        for (j = i + 1; j < n; j++) {
            if (arr[j] < arr[min_idx])
                min_idx = j;
        }
        // Swap the minimum element with the first element
        temp = arr[min_idx];
        arr[min_idx] = arr[i];
        arr[i] = temp;
    }
}

In this code :

1. The outer for loop `i` iterates from 0 to `n-2`, representing the unsorted portion of the array. In each iteration, the first element of the unsorted portion is considered as the minimum element.

2. Inside the outer loop, the variable `min_idx` is initialized to `i`, assuming the first element of the unsorted portion as the minimum.

3. The inner for loop `j` iterates from `i+1` to `n-1`, comparing each element with the current minimum element.

4. If an element smaller than the current minimum is found, `min_idx` is updated to the index of that element.

5. After the inner loop ends, the minimum element is swapped with the first element of the unsorted portion using a temporary variable `temp`.

6. The outer loop continues to the next iteration, considering the next element as the starting point of the unsorted portion.

Note: The for-loop implementation provides a concise and readable way to perform the selection sort algorithm. The outer loop selects the starting element of the unsorted portion in each iteration, while the inner loop finds the minimum element from the remaining unsorted elements.

Program to Perform Selection Sort in C Using While Loop

void selectionSort(int arr[], int n) {
    int i = 0, j, min_idx, temp;
    while (i < n - 1) {
        min_idx = i;
        j = i + 1;
        while (j < n) {
            if (arr[j] < arr[min_idx])
                min_idx = j;
            j++;
        }
        // Swap the minimum element with the first element
        temp = arr[min_idx];
        arr[min_idx] = arr[i];
        arr[i] = temp;
        i++;
    }
}

In this code :

1. We initialize the variable `i` to 0, representing the starting index of the unsorted portion of the array.

2. The outer while loop continues as long as `i` is less than `n-1`, ensuring that we iterate through all the elements except the last one.

3. Inside the outer loop, we initialize `min_idx` to `i`, assuming the first element of the unsorted portion as the minimum.

4. We also initialize the variable `j` to `i+1`, which will be used to traverse the remaining unsorted elements.

5. The inner while loop continues as long as `j` is less than `n`, comparing each element with the current minimum element.

6. If an element smaller than the current minimum is found, `min_idx` is updated to the index of that element.

7. After each comparison, `j` is incremented to move to the next element.

8. Once the inner loop ends, the minimum element is swapped with the first element of the unsorted portion using a temporary variable `temp`.

9. Finally, `i` is incremented to move to the next element, and the outer loop continues to the next iteration.

Program to Perform Selection Sort in C Using Functions

#include <stdio.h>
void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}
void selectionSort(int arr[], int n) {
    int i, j, min_idx;
    for (i = 0; i < n - 1; i++) {
        min_idx = i;
        for (j = i + 1; j < n; j++) {
            if (arr[j] < arr[min_idx])
                min_idx = j;
        }
        swap(&arr[min_idx], &arr[i]);
    }
}
void printArray(int arr[], int size) {
    int i;
    for (i = 0; i < size; i++)
        printf("%d ", arr[i]);
    printf("\n");
}


int main() {
    int arr[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("Original array: \n");
    printArray(arr, n);

    selectionSort(arr, n);

    printf("Sorted array: \n");
    printArray(arr, n);
    return 0;
}

You can also try this code with Online C Compiler

Run Code

Output

Original array: 
64 25 12 22 11 
Sorted array: 
11 12 22 25 64

In this code :

1. We define a `swap` function that takes two integer pointers as parameters. It swaps the values of the two variables pointed to by the pointers using a temporary variable.

2. The `selectionSort` function takes an integer array `arr` and its size `n` as parameters. It implements the selection sort algorithm using nested loops.

3. Inside the `selectionSort` function, we use the same logic as before to find the minimum element in each iteration and swap it with the first element of the unsorted portion.

4. However, instead of directly swapping the elements, we call the `swap` function and pass the addresses of the elements to be swapped using the `&` operator.

5. The `printArray` function remains the same as in the previous examples, which takes an array and its size as parameters and prints the elements of the array.

6. In the `main` function, we create an integer array `arr` and calculate its size using the `sizeof` operator.

7. We print the original array using the `printArray` function.

8. We call the `selectionSort` function, passing the array and its size as arguments, to sort the array.

9. Finally, we print the sorted array using the `printArray` function.

Note: This modular approach makes the code more readable, reusable, and maintainable. Functions can be easily called from different parts of the program, and they can be modified or updated independently without affecting the rest of the code.

Complexity Analysis of Selection Sort

Selection sort is a simple sorting algorithm, but it has a time complexity that makes it less efficient for large datasets. Let's analyze the time and space complexity of selection sort.

1. Time Complexity

Best Case: O(n^2)

In the best-case scenario, where the array is already sorted, selection sort still requires nested loops to compare each element with the minimum element. The outer loop runs for n-1 iterations, and the inner loop compares the current element with the remaining elements. Thus, the time complexity is still O(n^2).

Average Case: O(n^2)

In the average case, where the array is randomly ordered, selection sort performs the same number of comparisons as in the worst case. The outer loop runs for n-1 iterations, and the inner loop compares the current element with the remaining elements. The total number of comparisons is (n-1) + (n-2) + ... + 2 + 1, which results in a time complexity of O(n^2).

Worst Case: O(n^2)

In the worst-case scenario, where the array is sorted in reverse order, selection sort performs the maximum number of comparisons. The outer loop runs for n-1 iterations, and the inner loop compares the current element with all the remaining elements. The total number of comparisons is (n-1) + (n-2) + ... + 2 + 1, resulting in a time complexity of O(n^2).

Selection sort has a quadratic time complexity in all cases, making it inefficient for large datasets. The number of comparisons and swaps increases quadratically with the size of the array.

2. Space Complexity: O(1)

Selection sort is an in-place sorting algorithm, meaning it does not require any additional space proportional to the input size. It sorts the array by swapping elements within the array itself, without using any extra data structures. The space complexity of selection sort is O(1), as it uses only a constant amount of extra space for temporary variables and loop counters.

The in-place nature of selection sort makes it space-efficient, as it does not require allocating additional memory for the sorting process. However, it modifies the original array during the sorting process.

It's important to note that while selection sort has a quadratic time complexity, it has some advantages in certain scenarios:
It is simple to understand and implement, making it a good choice for small datasets or when simplicity is prioritized over efficiency.
It has a low number of swaps compared to other sorting algorithms like bubble sort, making it efficient in terms of memory writes.
It performs well on arrays where the elements are already partially sorted or when the input size is small.

However, for larger datasets or when efficiency is a primary concern, other sorting algorithms with better time complexities, like merge sort or quicksort, are preferred.

Advantages of Selection Sort

1. Simple and easy to understand: Selection sort is one of the simplest sorting algorithms to understand and implement. Its straightforward logic makes it easy to grasp, even for beginners in programming. The algorithm follows a clear step-by-step approach, making it intuitive to follow and reason about.

2. In-place sorting: Selection sort is an in-place sorting algorithm, which means it does not require any additional space proportional to the input size. It sorts the array by swapping elements within the array itself, without using any extra data structures. This makes selection sort space-efficient, as it uses only a constant amount of extra space for temporary variables and loop counters.

3. Fewer swaps compared to other algorithms: Selection sort has a relatively low number of swaps compared to other sorting algorithms like bubble sort. In each iteration, it only swaps the minimum element with the first element of the unsorted portion. This property makes selection sort efficient in terms of memory writes, which can be advantageous in certain scenarios where the cost of swapping elements is high.

4. Performs well on small datasets: Selection sort has a quadratic time complexity, which makes it inefficient for large datasets. However, it performs reasonably well on small arrays or when the input size is limited. For small datasets, the simplicity and low overhead of selection sort can make it a viable choice.

5. Partially sorted arrays: Selection sort performs well on arrays that are already partially sorted. If the array is nearly sorted or has a small number of unsorted elements, selection sort can quickly sort the remaining elements without requiring many iterations. In such cases, selection sort can be more efficient than other sorting algorithms that have higher overheads.

Disadvantages of the Selection Sort

1. Quadratic time complexity: The main disadvantage of selection sort is its quadratic time complexity, which is O(n^2) in all cases (best, average, and worst). This means that the time taken by the algorithm increases quadratically with the size of the input array. As the number of elements grows, the sorting time becomes significantly longer, making selection sort inefficient for large datasets.

2. Not efficient for large datasets: Due to its quadratic time complexity, selection sort becomes impractical and time-consuming when dealing with large arrays. The number of comparisons and swaps required grows rapidly as the input size increases, leading to poor performance. For large datasets, more efficient sorting algorithms like merge sort or quicksort, which have a better time complexity, are preferred.

3. Not adaptive: Selection sort is not an adaptive sorting algorithm, meaning it does not take advantage of partially sorted arrays. Even if the array is nearly sorted, selection sort still performs the same number of comparisons and swaps as in the worst case. It does not have any mechanism to detect and exploit existing order in the array, unlike some other sorting algorithms like insertion sort.

4. Not stable: Selection sort is not a stable sorting algorithm. A sorting algorithm is considered stable if it maintains the relative order of equal elements after sorting. In selection sort, if there are multiple elements with the same value, their relative order may change during the sorting process. This can be a disadvantage in certain applications where the stability of the sorting algorithm is important.

5. Not cache-friendly: Selection sort is not cache-friendly because it requires accessing elements from different parts of the array in each iteration. This leads to poor locality of reference and can result in more cache misses, which can impact the performance of the algorithm, especially on large datasets where cache efficiency is crucial.

Applications of Selection Sort

1. Small datasets: Selection sort is often used when the input size is small. For small arrays or lists, the simplicity and low overhead of selection sort can make it a practical choice. It can be easily implemented and is efficient enough for small-scale sorting tasks.

2. Educational purposes: Selection sort is commonly used as a teaching tool in introductory computer science courses and algorithms classes. Its straightforward logic and step-by-step approach make it a good example to illustrate the basic concepts of sorting algorithms. It helps students understand the fundamental principles of sorting and provides a foundation for learning more advanced sorting techniques.

3. Partially sorted arrays: Selection sort can be useful when dealing with partially sorted arrays. If the array is nearly sorted or has a small number of unsorted elements, selection sort can quickly sort the remaining elements without requiring many iterations. In such cases, selection sort can be more efficient than other sorting algorithms that have higher overheads.

4. Embedded systems: In embedded systems or resource-constrained environments where memory is limited, selection sort can be a viable choice. Its in-place sorting nature and minimal requirement for extra space make it suitable for systems with strict memory constraints. However, the efficiency of the selection sort should be carefully considered based on the input size and the specific requirements of the embedded system.

5. Preprocessing step: Selection sort can be used as a preprocessing step in combination with other sorting algorithms. For example, it can be used to sort small subarrays or to partially order the elements before applying a more efficient sorting algorithm. This hybrid approach can be beneficial in certain scenarios where the initial ordering of elements can significantly impact the performance of the subsequent sorting algorithm.

Note: It's important to note that while selection sort has its applications, it is generally not the most efficient choice for large datasets or performance-critical scenarios. In such cases, more advanced sorting algorithms like merge sort, quicksort, or heap sort, which have better time complexities, are more preferred.

Frequently Asked Questions

Is selection sort a stable sorting algorithm?

No, selection sort is not a stable sorting algorithm. The relative order of equal elements may change during the sorting process.

What is the space complexity of selection sort?

The space complexity of selection sort is O(1) as it is an in-place sorting algorithm & requires only a constant amount of extra space.

Is selection sort efficient for large datasets?

No, selection sort is not efficient for large datasets due to its quadratic time complexity. It becomes impractical & time-consuming for large input sizes.

Conclusion

In this article, we have explained the selection sort algorithm in C. We have discussed its working principle, and implementation using different looping methods, & analyzed its time & space complexity. Selection sort is a simple sorting algorithm that is easy to understand & implement. However, its quadratic time complexity makes it inefficient for large datasets. Despite its limitations, selection sorts have many applications in small-scale sorting tasks, educational purposes, & scenarios where simplicity & low overhead are prioritized.

You can also check out our other blogs on Code360.