AL.5: SORTING

OBJECTIVES

I can:

apply selection sort and insertion sort algorithms to sort the elements of array or ArrayList objects
compute statement execution counts and informal run-time comparison of sorting algorithms

There are many sorting algorithms to put an array or ArrayList in alphabetic or numerical order.

Two of the sorting algorithms that you need to know for the exam are:

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.

SELECTION SORT

The selection sort that you need to know for the exam 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.

Check out this folk dance video which shows the selection sort process:

Here is a short video that shows how selection sort works:

To identify a selection sort look for the following:

a nested for loop with the outer loop starting at 0 and ending when the index reaches length - 1 (see line 7 below)
the index of the smallest value should start at the outer loop index (see line 9 below)
the inner loop should start at the outer loop index + 1 and loop through the whole array (see line 10 below)
if the value in the array at the index of the inner loop is less than the value of the smallest index then set the smallest index to the index of the inner loop (see lines 12 - 15)
swap the value at the outer loop index and the smallest value (the one at the smallest value index) (see lines 17 - 19)

INSERTION SORT

The insertion sort that you need to know for the exam 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.

Here is a folk dance video that shows the insertion sort process:

And a short video that describes how insertion sort works:

To identify an insertion sort look for the following:

an outer for loop that starts at 1 and loops through the entire array (see line 7)
storing the element value at the outer loop index in temp (see line 9)
setting the possible index to the outer loop index (see line 10)
an inner while loop that loops while the possible index is greater than 0 and the value in temp is less than the value at the possible index minus one (see line 11)
set the value at the possible index to the one to the left of it (the one at possible index minus one) (see line 13)
decrement the possible index (subtract one from it) (see line 14)
when the while loop ends set the value at the possible index to temp (see line 16)

SUMMARY

Selection sort and insertion sort are iterative sorting algorithms that can be used to sort elements in an array or ArrayList.
Informal run-time comparisons of program code segments can be made using statement execution counts.

EVIDENCE

1) Complete the following Google Form. This form must be 100% correct and includes released AP practice questions. To stop working and return later, hit submit! You can "edit your response" and continue where you left off.

AL.5 Evidence

2) MC Exam Practice: This lesson has additional practice problems which can be found on the MC Exam Practice page with an answer key! Use ctrl + f to search for different objectives throughout the year. You could look at these questions now, or, save these practice questions for later and use them to review! The choice is yours.

Report abuse

AL.5: SORTING

OBJECTIVES

There are many sorting algorithms to put an array or ArrayList in alphabetic or numerical order.

Two of the sorting algorithms that you need to know for the exam are:

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.

SELECTION SORT

The selection sort that you need to know for the exam 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.

Check out this folk dance video which shows the selection sort process:

Here is a short video that shows how selection sort works:

To identify a selection sort look for the following:

a nested for loop with the outer loop starting at 0 and ending when the index reaches length - 1 (see line 7 below)

the index of the smallest value should start at the outer loop index (see line 9 below)

the inner loop should start at the outer loop index + 1 and loop through the whole array (see line 10 below)

if the value in the array at the index of the inner loop is less than the value of the smallest index then set the smallest index to the index of the inner loop (see lines 12 - 15)

swap the value at the outer loop index and the smallest value (the one at the smallest value index) (see lines 17 - 19)

INSERTION SORT

The insertion sort that you need to know for the exam 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.

Here is a folk dance video that shows the insertion sort process:

And a short video that describes how insertion sort works:

To identify an insertion sort look for the following:

an outer for loop that starts at 1 and loops through the entire array (see line 7)

storing the element value at the outer loop index in temp (see line 9)

setting the possible index to the outer loop index (see line 10)

an inner while loop that loops while the possible index is greater than 0 and the value in temp is less than the value at the possible index minus one (see line 11)

set the value at the possible index to the one to the left of it (the one at possible index minus one) (see line 13)

decrement the possible index (subtract one from it) (see line 14)

when the while loop ends set the value at the possible index to temp (see line 16)

SUMMARY

Selection sort and insertion sort are iterative sorting algorithms that can be used to sort elements in an array or ArrayList.

Informal run-time comparisons of program code segments can be made using statement execution counts.

EVIDENCE

1) Complete the following Google Form. This form must be 100% correct and includes released AP practice questions. To stop working and return later, hit submit! You can "edit your response" and continue where you left off.

AL.5 Evidence