1 of 37

Exploring Sorting

2 of 37

Learning Target & Do Now

LT: By the end of class, I will have my own conception of how to use computers to sort information.

​

DN: Refer to the provided handout for today.

3 of 37

Programming a Sorting Algorithm

  • Refer to the provided handout for today
  • It should look similar to how the last topic began
  • Searching and sorting are closely related
    • Founded on identifying properties of a set of items

4 of 37

Homework

  • Complete and submit the classwork
  • Prepare for upcoming test

​

Today’s animal: Giraffe Weevil

5 of 37

Selection Sort

Bubble Sort

6 of 37

Learning Target & Do Now

LT: By the end of today, I will know Selection and Bubble sorts.

​

​

DN: What is the complexity (order of growth) for the following?

​

public static void foo(int[] A){

for(int i=0; i<A.length; i++)

for(int j=0; j<A.length; j++)

System.out.println(“*”);

}

Answer: n2, or quadratic

7 of 37

Selection Sort

  • The most apparent way to sort an array is to pick the smallest item and move it to the front of the array
  • This will be done in-place: we alter the original array, rather than creating another

​

Let’s sort the array [4, 6, 1, 8, 7, 5, 9, 10]

8 of 37

[4, 6, 1, 8, 7, 5, 9, 10]

  1. What is the smallest element?
  2. Swap it into the correct spot. What is the array now?
  3. Repeat steps 1 and 2 for the second smallest, third smallest… nth smallest

9 of 37

Pseudocode

public static void sort(int[] A){

for(int i=0; i<A.length; i++){

// find the smallest value beginning at index i

​

​

​

​

​

// switch the elements at index i and the index of the min value

​

​

​

​

}

}

10 of 37

Time Complexity of Selection Sort

  • How many actions does this take to sort one item into place?
  • Two? Three?
  • It takes n actions to sort the first item
    • n-1 comparisons to other elements, and 1 swap
  • The next item takes n-1 actions, because we can ignore the sorted item
  • Repeat until no items remain
  • Action count: n + (n-1) + (n-2) + … + 2 + 1

11 of 37

Summation Made Simple

n + (n-1) + (n-2) + … + 2 + 1

​

Is the same as

​

​

​

​

Is the same as

​

​

​

Identify the dominating term!

12 of 37

Bubble Sort

  • Sort that only swaps items with their neighbors
  • The desired values will ‘bubble’ up to the end
    • They keep swapping in the same direction
  • How does this differ from selection sort?
  • How would the implementation differ?

​

Pros: partially sorts remaining items in each loop, can complete early on partially sorted data

Cons: variable action count, possibility for higher action count than other n2 sorts

13 of 37

14 of 37

One Iteration

One Iteration, Second Element

for(int i = 0; i < A.length-1; i++){

if(A[i] > A[i + 1]){

swap(A, i, i + 1);

}

}

for(int i = 0; i < A.length-2; i++){

if(A[i] > A[i + 1]){

swap(A, i, i + 1);

}

}

What changed?

15 of 37

Bubble Sort

public static void bubbleSort(int[] A){

for(int i = 1; i < A.length; i++){

for(int j = 0; j < A.length-i; j++){

if(A[j] > A[j+1]){

swap(A, j, j+1);

}

}

}

}

16 of 37

Homework

  • Modified Sorts worksheet (two days)
  • Prepare for upcoming test

​

Today’s animal: Portuguese man o’ war

17 of 37

Modified Bubble Sort;

Insertion Sort

18 of 37

Do Now

LT: By the end of class, I will have a more refined sense of how sorting algorithms work.

​

DN: If bubble sort makes no swaps during an iteration, what does that tell you about the input array?

A: The array is already sorted.

19 of 37

Bubble Sort, cont.

  • The Do Now is indicative of a property of bubble sort at any stage
    • If an iteration occurs with no swaps, then the array must be sorted
  • Bubble sort can ‘bail out’ early if its work is done
  • Implement this!
  • How does this affect complexity?

Case

Conditions

Complexity

Best

​

​

Worst

​

​

Average

N/A

​

20 of 37

Insertion Sort

  • Like bubble and selection sort, elements are put in place one-by-one
  • Unique assumption: at any time, a list is partially sorted
    • Smallest possible number of things that can be sorted?
  • When the sort sees an item outside the sorted portion, it is moved into place
    • Size of the sorted portion increases by 1

21 of 37

Insertion Sort!

22 of 37

Insertion Sort Code

public static void insertionSort(int A[]){

   int j;

for(int i = 1; i < A.length; i++){

       j = i;

while(j > 0 && A[j] < A[j-1]){

           swap(A, j, j-1);

           j--;

      }

   }

}

23 of 37

Analyzing Insertion Sort

Pros:

  • ‘Partial’ runs (goes to next run when an item is in place)
    • Each run can end early
  • Sort can end early
  • Sorting mechanism allows data to be added later with minimal impact

Cons:

  • Swapping one unit left/right is inefficient
  • Can have trouble making use of partially sorted data (same as bubble sort)

24 of 37

Complexity of Insertion Sort

Case

Conditions

Complexity

Best

​

​

Worst

​

​

Average

N/A

​

25 of 37

Homework

  • Modified Sorts worksheet
  • Prepare for upcoming test

Today’s animal: King� Cheetah (has stripes� instead of spots)

26 of 37

Introduction to Recursion

27 of 37

Learning Target & Do Now

LT: By the end of class, I will have an idea of what recursion is.

​

​

​

DN: What are the next six terms in the sequence:

​

1, 1, 2, 3, 5, 8, 13, 21, 34, …

​

What is the name of the sequence?

Answer: 55, 89, 144, 233, 377, 610; Fibonacci Sequence

28 of 37

Arithmetic and Geometric Sequences

  • Arithmetic sequence: add a value to a set pattern
  • Geometric sequence: multiply instead

​

  • Sequences are defined explicitly�or recursively
  • In the table at right, d and r refer�to the functions involved in the process

Fibonacci is a great example of a recursive function that is easier than the explicit

29 of 37

Pros and Cons

  • Explicit:
    • Pros:
      • Great for finding individual values, especially large values in sequence (i.e. n = 1000)
    • Cons:
      • Full action needs to be repeated for every desired value
  • Recursive:
    • Pros:
      • Elegant to read and write
      • Finds all values from initial case (a0) to an
    • Cons:
      • Requires a known base case to function (this is a0)
      • If not handled well, recursion can slow down or damage a computer
        • Computers these days prevent damage with a ‘StackOverflowError’

30 of 37

The Fibonacci Sequence

The explicit Fibonacci sequence, a.k.a Binet’s Formula:

The recursive sequence: Fn = Fn-1 + Fn-2

  • what are the base cases? (There are two)

31 of 37

Programming Geometric Sequences

Explicit:

public static double geometric(double first_term, double r, int term){

return first_term * Math.pow(r, term-1);

}

​

Recursive (Note the base case!):

public static double geometric(double first_term, double r, int term){

if(term == 0)

return first_term;

return r * geometric(first_term, r, term-1);

}

32 of 37

Programming Factorial

  • Let’s do this together!

​

5! = 5*4*3*2*1

4! = 4*3*2*1

5! == 5 * 4!

33 of 37

Coding Fibonacci

  • Spend the rest of today programming up Fibonacci explicitly and recursively
  • The code will be made available after class for review

34 of 37

Homework

  • Prepare for upcoming test

​

Today’s animal: Victoria Crowned Pigeon

35 of 37

Test Day

36 of 37

Learning Target & Do Now

LT: Today I will demonstrate my mastery of concepts relating to searching, sorting, and complexity.

​

DN: Complete any last-minute preparation.

37 of 37

Homework

  • None (get rest!)

​

Today’s animal: Humpback whales