ARRL - Sorting (Lesson)

APCompSci_LessonTopBanner.png

Sorting

Introduction

As we have discovered, to do an efficient search in an array, we need to have the data in sorted order. How do we sort an array? Go to Explore to find out!

There are three sorting methods that we need to know: Selection, Insertion, and Merge. We will explore the Selection and Insertion Sorts now. (We will look at Merge Sort later.)

Selection Sort

To sort an integer array in ascending order using a selection sort, traverse through an array, checking one element at a time looking for the smallest integer. Once you find the smallest, swap this element with the one in the correct position (the current position in the traverse). Continue swapping elements until the array is sorted.

For example, sort the following array in ascending order using a selection sort:

Original Array 1, 4, 5, 3, 2
After First Pass 1, 4, 5, 3, 2
After Second Pass 1, 2, 5, 3, 4
After Third Pass 1, 2, 3, 5, 4
After Fourth (and final) Pass 1, 2, 3, 4, 5

To calculate the total number of comparisons when searching for the smallest value, the sort will make n comparisons and pass over the array n times. n * n = n2 or O(n2). This is Big-O notation which simply represents the number of comparisons being made. No matter what order the data is in, selection sort will make the same number of comparisons each time.

Click below to watch a video demonstrating selection sort.

 

Insertion Sort

Insertion sort is done by comparing the first two elements and inserting the smallest one first. Then compare the next element to every element to its left until the correct position is found and insert it into the correct position. All other elements will move down. Here is what insertion sort looks like using our earlier array after each pass:

Original Array 1, 4, 5, 3, 2
After First Pass 1, 4, 5, 3, 2
After Second Pass 1, 4, 5, 3, 2
After Third Pass 1, 3, 4, 5, 2
After Fourth (and final) Pass 1, 2, 3, 4, 5

An array will be sorted after n-1 passes (n represents the number of elements in the array).

The worst-case scenario for the insertion sort is if the elements are initially sorted in reverse order. The number of comparisons in the first pass is 1, second pass is 2, third pass is 3, etc. Again, this is represented by O(n2). The best-case scenario is if the array is already sorted which allows for only one comparison on each pass to see that the element is in the correct position.

Click below to watch a video about insert sort.

 

Practice Icon Click on "Sorting" below to practice interactive sorts.

You will need to add selection and insertion sort before pressing play.

Sorting Links to an external site.

Sorting Practice

Click below to complete the sorting practice activity.

 

Practice Icon Practice-It! Practice

Go to the PracticeIt website Links to an external site..
Log into account.
Click on Start Practicing!
Go to the most recent edition.
Click on Chapter 13: Searching and Sorting
Complete Self-Check: 13.29 & 13.30

 

ArrayList Quiz Review

  1. Go to AP Classroom Links to an external site..
  2. Complete Unit 7 Progress Check(s).

APCompSci_LessonBottomBanner.pngIMAGES CREATED BY GAVS