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

    }

}

InsertionSort

 Insertion sort is another simple sorting algorithm that is even easier to explain than quicksort

•  Find the nth smallest element not yet sorted
  
• Swap it into the nth position

Suppose again we have our unsorted array:

3

7

2

4

1

5

6

We scan the array and find the smallest number is 1.

So 1 swaps with whatever is in the 1^st position (array[0]).

1

7

2

4

3

5

6

Now the 1 is sorted and won’t move again. The rest remains unsorted.
The smallest element in “the rest” is 2, so we swap 2 and arr[1].

1

2

7

4

3

5

6

Now [1,2] is sorted, and “the rest” still isn’t.

1

2

3

4

7

5

6

At this point, [1,2,3] is sorted. (The 4 happens to be in the right place, but that’s by luck.) Let’s swap the 4 with the 4^th element.

We still have

1

2

3

4

7

5

6

Because we got lucky.

Now, we can say for sure that [1,2,3,4] is sorted, and “the rest” is not.

So let’s swap 5.

1

2

3

4

5

7

6

Now, [1,2,3,4,5] is sorted and “the rest” is not. To sort the 6, we find the 6 and swap it with position arr[5].

1

2

3

4

5

6

7

 

Now, [1,2,3,4,5,6] is sorted. Let’s take the final (trivial) step and sort the 7 by swapping 7 with whatever happens to be in arr[6] (itself, so nothing will change).

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 insertionSort-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.

In pseudocode, this is:

InsertionSort(A)

    for i ← 1 to length(A) - 1 do

        key ← A[i]

        j ← i - 1

        while j ≥ 0 and A[j] > key do

            A[j + 1] ← A[j]

            j ← j - 1

        end while

        A[j + 1] ← key

    end for

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 InsertionSort {

    public static void main(String[] args) {

        int[] array = {10, 20, 25, 63, 96, 57};

        int size = array.length;

 

        for (int i = 1; i < size; i++) {

            int val = array[i];

            int pos = i;

            while (pos > 0 && array[pos - 1] > val) {

                array[pos] = array[pos - 1];

                pos = pos - 1;

            }

            array[pos] = val;

        }

 

        for (int i = 0; i < size; i++) {

            System.out.print(" " + array[i]);

        }

    }

}

QuickSort

 This is the first in a series of recursive sorting algorithms. Sorting algorithms, as their name implies, intend to take an unsorted collection of things—numbers, for now, but they could be anything—and put them in order.

Quicksort does this recursively with a “pivot” element. This pivot element works like a fulcrum on a lever: you have the left side of the lever (which is entirely left of the fulcrum), the fulcrum, and the right side of the lever (which is entirely right of the fulcrum).

Quicksort works like this:

1. Pick a pivot
2. Move everything less than the pivot to its left
3. Move everything greater than the pivot to its right
4. Quicksort the left
5. Quicksort the right

When we’re looking at only 0 or 1 elements, those are trivially already sorted—our base cases/stopping conditions for the recursion.

Suppose we have

3

7

2

4

1

5

6

There are many ways to pick pivots—the first, the last, the middle, the median (but this involves already sorting them, then picking the middle element), a random element. Here, for simplicity, we’ll pick the middle, 4 (3 things on its left, it, 3 things on its right).

Now, everything less than 4 goes on 4’s left, and everything greater goes on 4’s right.

3

2

1

4

7

5

6

Now, let’s just look at “the left”:

3

2

1

The pivot is 2; there is only one element less than it, so it is “the left” of “the left”; and there is only one element greater than 2, so it is “the right” of “the left.”

1

2

3

Now, let’s apply the same procedure to “the right” (and include the first pivot):

4

7

5

6

Let’s pick 6 as the pivot—so everything less than 6 is on the left of 6, then we have 6, then we have everything greater than it on the right.

4

5

6

7

We quickSorted the left half and the right half (where our pivot was), so we have successfully sorted both halves of the array—the left half (everything less than the pivot) and the right half (the pivot and everything greater). Since we have sorted both halves of the array, we have sorted the whole array:

3

7

2

4

1

5

6

sorted with quicksort becomes

1

2

3

4

5

6

7

Before you go on, try a few more examples of about this size—no fewer than 5, no more than 10. Pick a pivot, sort the left half (by picking a pivot), sort the right half (by picking a pivot).

In pseudocode, this is:
quicksort(arr, left, right)

    if left >= right

        return

    // Choose the middle element as pivot

    mid = left + (right - left) / 2

    pivot = arr[mid]

    // Partition the array

    i = left

    j = right

    while i <= j

        while arr[i] < pivot

            i = i + 1

        while arr[j] > pivot

            j = j - 1

        if i <= j

            swap arr[i] and arr[j]

            i = i + 1

            j = j - 1

    // Recursively sort the two partitions

    quicksort(arr, left, j)

    quicksort(arr, i, right)

and in real Java, this is:

public class QuickSort {

 

    public static void quicksort(int[] arr, int left, int right) {

        if (left >= right) {

            return;

        }

 

        // Choose the middle element as pivot

        int mid = left + (right - left) / 2;

        int pivot = arr[mid];

 

        int i = left;

        int j = right;

 

        while (i <= j) {

            while (arr[i] < pivot) {

                i++;

            }

            while (arr[j] > pivot) {

                j--;

            }

            if (i <= j) {

                // Swap arr[i] and arr[j]

                int temp = arr[i];

                arr[i] = arr[j];

                arr[j] = temp;

                i++;

                j--;

            }

        }

 

        // Recursively sort the two partitions

        if (left < j) {

            quicksort(arr, left, j);

        }

        if (i < right) {

            quicksort(arr, i, right);

        }

    }

 

    // Example usage

    public static void main(String[] args) {

        int[] array = { 9, 3, 7, 1, 8, 2, 5, 4, 6 };

        quicksort(array, 0, array.length - 1);

 

        // Print sorted array

        for (int num : array) {

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

        }

    }

}

BubbleSort

 Because it’s so simple, BubbleSort is one of the first sorting algorithms anyone learns. However, it does have its drawbacks, most notably its slow speed.

Imagine we have an array as shown here, assumed not to be sorted:

3

7

1

6

5

2

4

And we want the array sorted in ascending order, ending up as

1

2

3

4

5

6

7

We can, in a sense, “bubble” each item up or down into position, making a pass through potentially the whole array to get the number in the right position:

Let’s do that process to get 1 in place:

3

7

1

6

5

2

4

Is 1 in the right spot? No, it’s too far to the right.

3

1

7

6

5

2

4

Is 1 in the right spot? No, it’s too far to the right.

1

3

7

6

5

2

4

Is 1 in the right spot? Yes. It has bubbled up.

Now we need 2:

1	3	7	6	5	2	4
1	3	7	6	2	5	4
1	3	7	2	6	5	4
1	3	2	7	6	5	4
1	2	3	7	6	5	4

3 happens to be in the right place

Now we bubble up 4:

1	2	3	7	6	5	4
1	2	3	7	6	4	5
1	2	3	7	4	6	5
1	2	3	4	7	6	5

 

And the process continues, until, with all these pairwise comparisons and swaps, the list is in the proper order, the numbers having gradually risen into position like bubbles in a soda.

The worst possible outcome for this sort occurs when the list is already sorted, but in the opposite order. What happens if we want 123…7 but have 765…1?:

7	6	5	4	3	2	1
7	6	5	4	3	1	2
7	6	5	4	1	3	2
7	6	5	1	4	3	2
7	6	1	5	4	3	2
7	1	6	5	4	3	2
1	7	6	5	4	3	2

And all this work was just to bubble up the 1—we now have to do all this over again to bubble up the 2, 3, 4, 5, 6, and 7.