ArrayLists

Selection sort sorts arrays by repeatedly finding the minimum value in an array, and moving it to the front. Consider the following, unorganized array:

Using selection sort to sort this array, the first index in the array is picked to start.

Then, the list is traversed to find the minimum value in the rest of the list, which in this case is 1. The value 1 is then swapped from its current position to the position where 5 was:

Now the value 1 at index 0 is considered sorted, and the next unsorted element at index 1 will be chosen. The value at index 1 will be compared with the rest of the unsorted items until a minimum value is found. In this case, the value 2 at index 5 is the minimum value, and it is swapped with the value at index 1.

This process continues until the entire list is sorted from least - greatest.

Here is what this process looks like in pseudocode:

traverse each index up to the second to last element
find the minimum in the rest of the list
swap the index and minIndex
// now everything up to curIndex is sorted

This can then be used to create a working algorithm for selection sort:

public static void selectionSort(int[] array)
{
    for(int index = 0; index < array.length - 1; index++)
    {
        int minIndex = index;
        for(int i = index; i < array.length; i ++)
        {
            if(array[i] < array[minIndex])
            {
                minIndex = i;
            }
        }
        int tempValue = array[index];
        array[index] = array[minIndex];
        array[minIndex] = tempValue;
    }
}

The initial traversal goes from the first element to the second to last element (array.length - 1) because the final element in the array is considered sorted if every other element in the array has been sorted correctly. The second traversal looks for the minimum value in the array from the current element until the end of the list. It does not search the list for already sorted elements. Once the minimum element is found, it swaps positions with the current element.

Selection sort is a particularly useful sorting algorithm when the elements in a list are in reverse order:

In this case, the algorithm only needs to swap values a few times, as each swap successfully puts each element in its correct position.

Insertion sort sorts an array by sorting each element compared to the elements already sorted to their left.

Given the same list as the previous example, insertion sort marks the first element in the list as sorted:

The next element, 3, is then selected as the next element to sort:

Rather than find the minimum value in the unsorted segment like selection sort, insertion sort compares unsorted elements to the sorted ones, placing the element in the correct position within the sorted list:

The element 3 is now considered sorted, and the sort continues on to the next element, 4, and sorts it within the already sorted list:

This continues until all elements in the list are sorted from least to greatest.

Here is a pseudocode implementation of insertion sort:

traverse each element starting from index 1
traverse sorted elements to find current element position
shift sorted elements to place current element

This can be used to create a working algorithm for insertion sort:

public static void insertionSort(int[] array)
{
    for(int index = 1; index < array.length; index++)
    {
        int currentIndexValue = array[index];
        int sortedIndex = index - 1;

        while(sortedIndex > -1 && array[sortedIndex] > currentIndexValue)
        {
            array[sortedIndex + 1] = array[sortedIndex];
            sortedIndex--;
        }

        array[sortedIndex + 1] = currentIndexValue;
    }
}

Insertion sort traverses all elements from index 1 until the end of the array. Each element then traverses the sorted segment of the array, looking for the correct place in the sorted list to go. This is done using a while loop, as the number of iterations depends largely on the content of the sorted list. As the element moves through the sorted list, each element it searches through is shifted one index higher. This ensures that the element can be placed in the correct index without removing any of the pre-sorted elements from the list.

Insertion sort is most useful when a list is mostly sorted:

When lists are almost sorted, the number of times that insertion sort needs to iterate through the list items is limited. In this case, the while loop will not execute for the first 5 index values in this array, limiting the execution count, and reducing the amount of time the algorithm spends sorting items.

When choosing which sorting algorithm to use, it’s important to pay attention to the composition of the existing list, and determine which method will be most efficient, especially as the datasets grow.

Starting the insertion sort algorithm from the example, switch the order for the sort from ascending order to sort in descending order. (for example, 10, 8, 6, 4, 2).

Hint: Where are items compared? Try writing out the steps in the algorithm on paper to help.