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!
![Most Asked AWS Interview Questions & Answers [For Freshers & Experienced]](/__khugblog-next/image/?url=https%3A%2F%2Fd14b9ctw0m6fid.cloudfront.net%2Fugblog%2Fwp-content%2Fuploads%2F2019%2F07%2FBlog_FI_July_upGrads-Interview-tips.png&w=3840&q=75)
