Selection Sort | Algorithms
In our previous articles, we have seen two of the searching algorithms like Binary Search and Fibonacci Search alogorithm. In this article, we will go through Selection Sort algorithm.
Selection sort is one of the simplest sorting algorithm available. Before going into more details we will see first see why sorting is required in programming. Sorting is important in programming for the same reason it is important in everyday life. It is easier and faster to locate items in a sorted list than unsorted.
The selection sort algorithm sorts an array by repeatedly finding the minimum element (considering ascending order) from the unsorted part and putting it at the beginning. The array will have two parts in this process. A subarray which is sorted and other subarrays which is yet to be sorted.
Algorithm
Sudo code for the selection sort will be as below:
sort(A) for i ← 1 to n-1 smallest ← i for j ← i + 1 to n if A[ j ] ≤ A[ smallest ] smallest ← j if smallest ≠ i Exchange A[ j ] ↔ A[ smallest ]
What we are doing in above code:
- First, it finds the smallest element in the array.
- Exchange that smallest element with the element at the first position.
- Then find the second smallest element and exchange that element with the element at the second position.
- This process continues until the complete array is sorted.
Time and Space Complexity
From the code, we can see that the time complexity for selection sort is O(n2) and space complexity is O(
Average Case
Java Program Implementation
Let's implement the selection sort algorithm:
public void sort(int arr[]) { int n=arr.length; int min_ind; for(int i=0;i<n;i++) { min_ind = i; for(int j=i+1;j<n;j++) { if(arr[min_ind] > arr[j]) { min_ind =j; } } if(min_ind!=i) { int temp = arr[i]; arr[i] = arr[min_ind]; arr[min_ind] = temp; } } }
Advantage over Bubble Sort
In Selection sort, a maximum of n swap operations are required, whereas in Bubble Sort, up to n swap operation happens for each element, so up to n2 total swap operation are required. These swap (write) operations are memory-intensive, so selection sort becomes even more efficient than Bubble sort for large lists.
In short, Selection Sort is used normally in cases where memory writes are quite expensive than memory reads.
Bubble Sort
However, both Selection and Bubble Sort take O(n2) time, so it is not recommanded to use them in real-life applications.
You can also check the other articles on sorting and searching such as selection sort, binary search, fibonacci search, merge sort etc. you can also go through our other articles on different algorithms and data structures.
That's all for this topic. If you guys have any suggestions or queries, feel free to drop a comment. We would be happy to add that in our post. You can also contribute your articles by creating contributor account here.
Happy Learning 🙂
If you like the content on CodePumpkin and if you wish to do something for the community and the planet Earth, you can donate to our campaign for planting more trees at CodePumpkin Cauvery Calling Campaign.
We may not get time to plant a tree, but we can definitely donate â‚ą42 per Tree.
About the Author
Tags: Algorithms, Selection Sort, Sorting
Comments and Queries
If you want someone to read your code, please put the code inside <pre><code> and </code></pre> tags. For example:<pre><code class="java"> String foo = "bar"; </code></pre>For more information on supported HTML tags in disqus comment, click here.