by BehindJava

Data Structures - Selection Sort Algorithm

Home » datastructures » Data Structures - Selection Sort Algorithm

In this tutorial, we are going to learn about selection sort in detail and its algorithmic implementation.

Selection Sort

• In-place algorithm.
• O(n^2) time complexity - Quadratic.
• It will take 100 steps to sort 10 items, 10000 steps to sort 100 items and 1000000 steps to sort 1000 items.
• Doesn’t require much swapping as bubble sort.
• Unstable algorithm.

Selection Sort Algorithm

Selection_Sort (A, n)

1. Set j = 0.
2. Repeat Step 2 to 4 While j < n – 1:
3. Set Min = j and i = j+1.
4. Repeat step 5 while i < n:
5. if(a[i] < a[Min]), then: Min = i. [End of step 4 loop.]
6. if (Min != j), then:
7. swap (a[j], a[Min]). [End of step 2 loop.]
8. End

Selection Sort Programmatic Implementation in Java

``````public class SelectionSort {
public static void main(String[] args) {
int[] intArray = { 20, 35, -15, 7, 55, 1, -22 };
for (int lastUnsortedIndex = intArray.length - 1; lastUnsortedIndex > 0; lastUnsortedIndex--) {
int largest = 0;
for (int i = 1; i <= lastUnsortedIndex; i++) {
if (intArray[i] > intArray[largest]) {
largest = i;
}}
swap(intArray, largest, lastUnsortedIndex);
}
for (int i = 0; i < intArray.length; i++) {
System.out.print(intArray[i]+ " ");
}}
public static void swap(int[] array, int i, int j) {
if (i == j) {
return;
}
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}}``````

Output:

``-22 -15 1 7 20 35 55 ``