Programs

How to Implement Selection Sort in C?

The selection Sort is another algorithm that operates by locating the array’s lowest integer and then assigning it to the top position. The index next to the position of the smallest integer will be used to begin the following array that has to be scanned.

Example of Selection sorting in C

If we take an array with numbers [10,2,8,4,6] in which the smallest number is 2. Thus, we will place the smallest number, which is 2, in the first position, after which the array will look like [2,10,8,4,6]. Next, we will take the next smallest number because 2 is already in its correct position now. The next smallest number is 4, which will be placed in the second position, after which the array will be searched similarly until it is finally sorted.

The selection sort in C sorts numbers in ascending order. By modifying the algorithm, numbers can be arranged in a descending Selection Sort can also be performed in other languages apart from C, like Selection Sort C++ or Selection Sort Python. 

Learn Software Development Courses online from the World’s top Universities. Earn Executive PG Programs, Advanced Certificate Programs or Masters Programs to fast-track your career.

Selection Sort Algorithm

  • First, we set the initial element in the selection sort to be the minimum and search for the smallest element in the array for the correct procedure of the Selection Sort Algorithm.
  • The minimum element is now compared with the second component. If the second element falls below the minimum, we will swap them and then assign the third element a minimum value.
  • Otherwise, we will continue to the third element and compare it to the minimum. If the second element exceeds our first element, we will swap it. Repeat this process up to the last component.
  • After each iteration, we will see that our minimum has arrived at the beginning of the unsorted list.
  • We will begin indexing from the first entry of the unsorted list for each iteration. Until the list is sorted or all the components are suitably positioned, we will repeat Steps 1 through 4 several times.

Popular Courses & Articles on Software Engineering

The following example with each iteration will help in understanding the process of selection sorting in C in detail–

Iteration #1

I [ ] = 8,5,2,6,4

Set a minimum – 8

Compare i0 and i1

As, i0 > i1, set minimum = 5.
  • Compare i1 and i2
As, i1 > i2, set minimum = 2.
  • Compare i2 and i3
As, i2 < i3, set minimum= 2.
  • Compare i2 and i4
As, i2 < i4, set minimum =2.

2 is the smallest number of all the elements, we must swap i0 and i2

­Iteration #2

I [ ]= 2,5,8,6,4

Set minimum 5
  • Compare i1 and i2
As, i1 < i2, set minimum = 5.
  • Compare i1 and i3
As i1 < i3, set minimum = 5
  • Compare i1 and i4
Again, i1 < i4, set minimum = 4.

4 is the smallest element in the array, thus, we must swap i1 and i4.

Iteration #3

I [ ]= 2,4,8,6,5

Set minimum 8
  • Compare i2 and i3
As, i2 > i3, set minimum = 6.
  • Compare i3 and i4
As, i3 > i4, set minimum = 5.

5 is the smallest element in the array, you must swap i2 and i4.

Iteration #4

I [ ] = 2,4,5,6,8

Set minimum 6
  • Compare i3 and i4
As i3 < i4, set minimum = 6.

The minimum is placed in the correct place; thus, no swapping will occur.

Selection Sort Example in C

// Selection sort in C

#include <stdio.h>

// function to swap the position of two elements

void swap(int *a, int *b) {

  int temp = *a;

  *a = *b;

  *b = temp;

}

void selectionSort(int array[], int size) {

  for (int step = 0; step < size - 1; step++) {

int min_idx = step;

for (int i = step + 1; i < size; i++) {

   // To sort in descending order, change > to < in this line.

   // Select the minimum element in each loop.

   if (array[i] < array[min_idx])

     min_idx = i;

}

// put min at the correct position

    swap(&array[min_idx], &array[step]);

  }

}

// function to print an array

void printArray(int array[], int size) {

  for (int i = 0; i < size; ++i) {

    printf("%d  ", array[i]);

  }

  printf("\n");

}

 

// driver code

int main() {

  int data[] = {20, 12, 10, 15, 2};

  int size = sizeof(data) / sizeof(data[0]);

  selectionSort(data, size);

  printf("Sorted array in Acsending Order:\n");

  printArray(data, size);

}

Complexity Analysis of Selection Sort

Input – n input items are given.

Output – The number of steps that are required to sort the list.

Logic – If we are given n items, it will make n-1 comparisons in the first pass, n-2 comparisons in the second pass, n-3 comparisons in the third pass, and so on. Consequently, the total number of comparisons may be calculated using the;

Output –

(n+1) + (n+2) + (n+3) + (n+4) + …. +1

Sum = n(n-1)/2 i.e., O(n²)

Because the selection sort method needs some additional memory space for temporary variables for swapping, it has a time complexity of O(n2) and a space complexity of O(1).

Selection Sort Time Complexity Analysis

Best Case: For the array that has previously been sorted, the selection sort method has a best-case time complexity of O(n²).

Average Case: The selection sort algorithm has an average-case time complexity of O(n²) when the items are jumbled arranged, that is, neither in ascending order nor in descending order.

Worst Case: When we reverse an array’s descending order into its ascending order, the worst-case time complexity is O(n²).

The temporal complexity of the selection sort method is O(n²) in each of the three scenarios. This is due to the fact that we must identify the bare minimum items for each stage in order to arrange them properly. After tracing the whole array, we will have found our minimal element.

Conclusion

This brings the blog post on “Selection Sort In C” to a close. You must understand that it can be performed in other languages as well, like Selection Sort C++ and Selection Sort Python. We hope this article will help you understand how to sort elements in C. 

Selection sorting is not the only segment in the journey of becoming a programmer. If you’re hoping to get a significant boost to your software development career with a professional degree, upGrad is here! upGrad’s frontend development (JavaScript, HTML, CSS), backend (NoSQL-MongoDB), and microservices, then you can pursue UpGrad’s Master of Science in Computer Science course. Delivered by IIIT Bangalore & LJMU Alumni Status, this course helps you land your career as a software engineer/full-stack developer with the tech giants throughout the world.

This course covers the basic knowledge of tools like Java, Spring, and Hibernate, strengthening our full-stack development skills to explore the job market with remarkable opportunities. 

Sign up to learn more!

What does selection sort mean in data structures?

A straightforward sorting algorithm is the selection sort. The list is split into two halves in this in-place comparison-based sorting process, the sorted part at the left end and the unsorted half at the right end. The list as a whole is initially in the unsorted half, and the sorted part is empty.

What is quick sort in C?

The sorting algorithm known as Quicksort is based on the divide and conquer strategy. An array is split into subarrays (an element selected from the array) by choosing a pivot element.

What is 2-way selection in C?

When two sets of statements are present—one set for when the Boolean condition is true and another set for when it is false—this is known as a two-way selection (if/else).

Want to share this article?

Prepare for a Career of the Future

Leave a comment

Your email address will not be published. Required fields are marked *

Our Best Software Development Course

Get Free Consultation

Leave a comment

Your email address will not be published. Required fields are marked *

×
Get Free career counselling from upGrad experts!
Book a session with an industry professional today!
No Thanks
Let's do it
Get Free career counselling from upGrad experts!
Book a Session with an industry professional today!
Let's do it
No Thanks