Selection Sort in C
In this article, we will discuss the Selection sort Algorithm. The working procedure of selection sort is also simple and efficient sorting algortihm that works by swapping the minimum element of list.
This article will be very helpful and interesting to students as they might face selection sort as a question in their examinations. So, it is important to discuss the topic.
Selection Sort is a simple and efficient sorting algortihm that works by swapping the minimum element of list from the first element.It is used to sort a list of elements in either ascending or descending order.
Working of Selection Sort Algorithm
Now let' see the working of Selection Sort Algorithm.
To understand the working let us take an unsorted array(unsorted array means the data present in the array is in jumbled order that is neither in ascending order nor descending)and start sorting it using Selection Sort Algorithm.
Lets start by taking the array elements.
Indexing of array starts from 0th position.
Set the first element of the array as minimum. Minimum = 10 and Compare the minimum value with the rest of the array, if a smaller element is found than the minimum element, swap with the minimum element.
Here in figure 2 smallest element except the first index, 7 is present at index [3], so we will swap the minimum with the smallest value.Therefore our array after swapping will look like the figure given below.
In second step we will now assign the second element (15) as minimum and scan the rest of array looking for the smallest element present.If we look carefully the smallest value is present at index at 3. So we will swap it with the minimum element.
Therefore our array after swapping will look like the figure given below.
If your are getting the idea how selection sort works then Let's proceed towards sorting the rest of the array.
Just like the previous ones now its time to assign the third element (25) as minimum and scan the rest of array looking for the smalest value present and this time smallest value is just next to it, So swapping will take place.
Lets swap it
After swapping array will look like the figure given below.
Slowly our array is sorting lets fully sort our array.
Now we will fix the forth position element and scan the rest of the elements, smallest value is 20 at array index 5.
so we will swap it.
After swapping array will look like the figure given below.
Again we will select the fifth element (32) as minimum element and swap with the smallest value present in the rest of array. smallest value is 25.
so we will swap it.
Now if you look carefully in the array you will find that all elements are sorted and the last element doesn't need to swap as it is already presnet in the right position.
Hence our array is sorted. So full process of sorting using selection sort is represented in the below figure.
Just have a look
As we have learned the working of binary search Lets proced towards the Pseudo Code.
Pesudo Code Of Selection Sort
We are moving towards the Algorithm of Selection Sort.
Algorithm of Binary Search
Selection Sort Program in C
Time Complexity
Now let's see the Time complexity of Selection Sort in Best case, worst case, Average case. We will also be learning about space complexity.
Best Case: In Selection Sort best case occur when the array is already sorted.
Worst Case: Worst Case occurs when we sort the descending order of array into ascending order..
Average Case: Average Case of Selection Sort occurs when the element are in jumbled order i,e. neither in ascending nor in descending order.
Space Complexity
Advantage of Selection Sort
Selection sort is simple and easy to understand.
Selection Sort works well with small datasets.
It is easy to modify to sort in ascending or descending order.
Disadvantage of Selection Sort
Selection Sort does not work well with large datasets.
It has poor cache performance
It does not handle data with many duplicates since it can make unecessary swaps.
When to use Selection Sort
Selection Sort can be used whwn we are dealing with small datasets.
It can be used in more efficient algorithm
It can be used where there is limited memory environment
Conclusion
So far our Selection Sort article comes to an end but before ending we just conclude what are the things that we have learned today.
To conclude, it can be said that
Selection Sort is simple and easy to undestand as it works by repeatedly swapping the minimum element in the array.
Its a stable sorting algorithm
It is useful with small datasets
Main Banner Image Credit: veryfi.com