SelectionSort

 Selection sort is yet another simple sorting algorithm:

• Start with an unsorted array
• Find the smallest element in the unsorted part
• Swap it with the first unsorted element
• Keep growing the sorted part of the array (and correspondingly shrinking the unsorted part) until the whole array is sorted

Again, imagine we have as an example the starting state:

3

7

2

4

1

5

6

The smallest unsorted element is 1, and the first is 3. So we swap them.

1

7

2

4

3

5

6

Next, the unsorted part has 6 elements, and the 1 is sorted. The first unsorted element is 7, and the smallest is 2. Swap them.

1

2

7

4

3

5

6

The unsorted part now has 5 elements, the smallest of which is 3, and the first of which is 7. Swap them.

1

2

3

4

7

5

6

                                    

The unsorted part now has 4 elements, the smallest of which is 4, and the first of which is (by coincidence) also 4. Swap them. (It will appear as if nothing changed, but after this step, we can call the 4 officially sorted.)

1

2

3

4

7

5

6

The unsorted part now has 3 elements, the smallest of which is 5, and the first of which is 7. Swap them.

1

2

3

4

5

7

6

The unsorted part now has 2 elements, the first of which is 7 and the smallest of which is 6. Swap them.

1

2

3

4

5

6

7

The unsorted part now has 1 element, the first of which is 7 and the smallest of which is 7. Swap it. (Nothing will change, but now the 7 is considered sorted.)

1

2

3

4

5

6

7

Before you go on, do what I had to do when I first learned this algorithm: make a video or live demo for your family of you selectionSort-ing about that many red Solo cups marked with numbers on their bottoms. If you can correctly sort the cups, move on to the pseudocode.

for i from 0 to n - 2 do

    min_index = i

    for j from i + 1 to n - 1 do

        if array[j] < array[min_index] then

            min_index = j

    if min_index ≠ i then

        swap array[i] and array[min_index]

Spend some time with this pseudocode and understand why it is equivalent to the example, or to what you did for your family with the cups. Once you are confident you understand the pseudocode—and only then—move on to the real Java code, found below:

public class SelectionSort {

    public static void selectionSort(int[] array) {

        int n = array.length;

 

        // Traverse through all array elements

        for (int i = 0; i < n - 1; i++) {

            // Find the minimum element in unsorted array

            int minIndex = i;

            for (int j = i + 1; j < n; j++) {

                if (array[j] < array[minIndex]) {

                    minIndex = j;

                }

            }

 

            // Swap the found minimum element with the first element

            if (minIndex != i) {

                int temp = array[i];

                array[i] = array[minIndex];

                array[minIndex] = temp;

            }

        }

    }

    // Example usage

    public static void main(String[] args) {

        int[] arr = {3, 7, 2, 4, 1, 5, 6};

        selectionSort(arr);

 

        // Print sorted array

        for (int num : arr) {

            System.out.print(num + " ");

        }

        // Output: 1 2 3 4 5 6 7

    }

}