Sorting Algorithms
Introduction: 7.6.0
- There are many algorithms to sort an array
- There are 3 to know for the CS A exam
- Selection sort
- Select the smallest item in the unsorted section of the array; move it to the front
- This value is now “sorted”
- Repeat until you are at the second to last value
- Select the smallest item in the unsorted section of the array; move it to the front
- Insertion sort
- Work left to right; from the second item
- If an item is larger than the item below it, move it down until
arr[i] >= arr[i-1]
- Merge sort
- Break each array down into individual components
- Continually merge components together, sorting along the way
- Groups of 1, 2, 4, 8, 16, etc.
- Uses recursion
Selection sort
To identify selection sort:
- look for a nested loop
- outer loop starts at 0; ends at length - 1
- inner loop starts at the outer loop + 1
- if the value of the inner loop index is less than the smallest index, the smallest index swaps
- swap the value at the outer loop and the smallest value
public static void selectionSort(int[] elements)
{
for (int j = 0; j < elements.length - 1; j++)
{
int minIndex = j;
for (int k = j + 1; k < elements.length; k++)
{
if (elements[k] < elements[minIndex])
{
minIndex = k;
}
}
int temp = elements[j];
elements[j] = elements[minIndex];
elements[minIndex] = temp;
}
}
Insertion sort
- starts at index 1
- inserts the value at index 1 into the correct place on the sorted part of the list
- moves the value left as long as there are larger values below it
To identify an insertion sort:
- look for an outer loop that starts at 1 and loops through the whole array
- storing the element value and possible index
- an inner while loop
- loops while possible index is positive and index value is less than the value below it
- when the inner loop ends, set the possible index to the value
public static void insertionSort(int[] elements)
{
for (int j = 1; j < elements.length; j++)
{
int temp = elements[j];
int possibleIndex = j;
while (possibleIndex > 0 && temp < elements[possibleIndex - 1])
{
elements[possibleIndex] = elements[possibleIndex - 1];
possibleIndex--;
}
elements[possibleIndex] = temp;
}
}
Summary: 7.6.4
- selection sort and insertion sort are iterative sorting algorithms which sort elements in an array or ArrayList
- informal run-time comparisons of code and algorithms can be made using the number of statements executed
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
This was adapted from the CS Awesome curriculum, which was created by
Barbara Ericson, Beryl Hoffman, and many other CS Awesome contributors. All rights reserved.
CS Awesome is licensed under CC BY-NC-SA 4.0.