Advanced Topics: Sorting and Array to ArrayList

There are three common sorting algorithms that can be helpful when trying to sort from lowest to highest or from highest to lowest. We’ll be covering these to a deeper degree in IB Computed science, but for now, you can try to use them to solve the WordSearch Lab

• Selection Sort – Select the smallest item from the current location on to the end of the array and swap it with the value at the current position. Do this from index 0 to the array length – 2. You don’t have to process the last element in the array, it will already be sorted when you compare the prior element to the last element.
• Insertion Sort – Insert the next unsorted element in the already sorted part of the array by moving larger values to the right. Start at index 1 and loop through the entire array.
• Merge sort – Break the elements into two parts and recursively sort each part. An array of one item is sorted (base case). Then merge the two sorted arrays into one.

Selection Sort

The selection sort that you need to know starts at index 0 and looks through the entire array keeping track of the index of the smallest value in the array and then swaps the value at the smallest index with the value at index 0. Then it does the same thing for index 1, then 2, and so on until it reaches the length of the array minus one. At this point, the array is sorted in ascending order.

Code for Selection sort that sorts elements from LOWEST to HIGHEST

Insertion Sort

Insertion sort starts at index 1 and inserts the value at index 1 into its correct place in the already sorted part (the part to the left of the current index). It moves any value larger than the value stored in temp to the right until it either finds the appropriate place to put temp or gets to the front of the array.

Selection and Insertion Sorting Code

You may use this tool for Pseudocode and Visualization:

https://visualgo.net/en/sorting

Array to ArrayList and ArrayList to Array

You can try to make ArrayLists work while sorting, but it’s a bit easier if you convert them to Arrays first and then back to an ArrayList after it has been sorted.