	Jupyter at Bryn Mawr College
Public notebooks: /services/public/dblank / CS206 Data Structures / 2016-Spring / Notebooks

[Lab 4, CS206: Data Structures, Bryn Mawr College. In the following cell, give a hash title and by-line. Then you can remove this cell. This lab is due in one week.]

BinaryTrees and Sorting¶

This lab will explore searching binary trees and sorting arrays of integers.

BinaryTree search¶

In the last lab, you wrote a sorted binary tree. For the following, test out your search on the following sized trees:
Put 100 million items in the tree, in order.
Put 1,000 million items in the tree, in order.
Put 100,000 million items in the tree, in order.
Put 1 million items in the tree, in order.
Run your find() method to find items that are, and are not in the tree.
Create a table showing:

Tree Size	Comparisons to Find Item in tree	Comparisons to Find Item not in tree
100
1,000
100,000
1,000,000

Your numbers should be an average.

Put your code here for your Binary tree, find, and None. You may copy your code from last week. If you didn't get last week's answer, ask and a solution will be provided.

You can add cells here to compute your table values. You can use the process below for making random integers for putting into your tree.

Put your table here:

Sorting¶

Shifting gears, we will look at three sorting algorithms, and compare how "good" they are.

Double Trouble¶

Perhaps one of the simplest methods of sorting a list of numbers is the "Double Trouble" algorithm:

For each number $i$ in the array,
compare it to every other number $j$ in the array
- if number[$i$] > number[$j$], then swap them

Let's write that algorithm. First we need an array of numbers.

int[] my_array;

|  Added variable my_array of type int[]

Let's write some functions to create lengths of random numbers:

import java.lang.Math;

int[] makeArray(int size, int low, int high) {
    int[] array = new int[size];
    for (int i=0; i < size; i++) {
        array[i] = (int)((Math.random() * (high - low)) + low);
    }
    return array;
}

void printArray(int[] array) {
    for (int i=0; i < array.length; i++) {
        printf("%s, ", array[i]);
    }
    printf("\n");
}


|  Added method printArray(int[])

printArray(makeArray(10, 0, 100))

47, 56, 19, 1, 73, 75, 85, 96, 89, 18,

Now, let's sort the list using the Double Trouble algorithm.

It should sort the numbers in place
Smallest to largest

Use these functions to count the compares:

int compares = 0; // global

void swap(int[] array, int i, int j) {
    int temp = array[i];
    array[i] = array[j];
    array[j] = temp;
}

boolean compare(int v1, int v2) {
    compares++;
    return v1 > v2;
}

int sort_double_trouble(int[] array) {
    compares = 0;
    /// Write code here!
    return compares;
}

int compares = 0; // global

void swap(int[] array, int i, int j) {
    int temp = array[i];
    array[i] = array[j];
    array[j] = temp;
}

boolean compare(int v1, int v2) {
    compares++;
    return v1 > v2;
}

int sort_double_trouble(int[] array) {
    compares = 0;
    for (int i=0; i < array.length - 1; i++) {
        for (int j=i; j < array.length; j++) {
            if (compare(array[i], array[j])) {
                swap(array, i, j);
            }
        }
    }
    return compares;
}

|  Modified variable compares of type int with initial value 0


|  Modified method swap(int[],int,int)
|    Update overwrote method swap(int[],int,int)

int[] array1 = makeArray(10, 0, 100);
printArray(array1);
printf("Double Trouble took %s comapres\n", sort_double_trouble(array1));
printArray(array1);

|  Modified variable array1 of type int[] with initial value [I@50cbc42f

25, 50, 16, 88, 73, 33, 20, 23, 12, 71, 

Double Trouble took 54 comapres

12, 16, 20, 23, 25, 33, 50, 71, 73, 88,

Bubble Sort¶

Perhaps a "better" algorithm is Bubble sort.

It works as follows:

Let k = 1
For each number $i$ in the array (up to length - k),
compare it to the next number $j$ in the array
- if number[$i$] > number[$j$], then swap them
Increment k
Go back to step 1, until no more swaps were made

It is called Bubble sort, because the biggest number will bubble up to the top on the first loop, then the second largest number on the second loop, etc.

Write the Bubble sort algorithm, and test it.

Quicksort¶

The final algorithm that we will look at is quicksort. quicksort represents a class of algorithms in computer science that capture the motto "divide and conquer".

The quicksort algorithm:

Pick a pivot value
Break set of items into two parts:
    first part is all less than the pivot value
    second part is all greater than the pivot value
Sort the first part
Sort the second part

The quicksort algorithm, with more implementation details:

Quicksort on start and end:
    if start less than end:
        Partition from start to end around p:
        Quicksort on start and p - 1
        Quicksort on p and end

The partition picks a point,

Partition from start to end:
   Pick a pivot position, p, and pivot value
   Partition array into:
       those less than pivot value
       pivot value
       those less than pivot value
   return partition

In Java, the main quicksort function looks like:

void quicksort(int[] array, int lo, int hi) {
    if (lo < hi) {
        int p = partition(array, lo, hi);
        quicksort(array, lo, p - 1);
        quicksort(array, p + 1, hi);
    }
}

int partition(int[] array, int lo, int hi) {
    int pivotIndex = choosePivot(lo, hi);
    int pivotValue = array[pivotIndex];
    // put the chosen pivot at array[hi]
    swap(array, pivotIndex, hi);
    int storeIndex = lo;
    // Compare remaining array elements against pivotValue = array[hi]
    for (int i = lo; i <= hi - 1; i++)  {
        if (compare(pivotValue, array[i])) {
             swap(array, i, storeIndex);
             storeIndex = storeIndex + 1;
        }
    }
    swap(array, storeIndex, hi);  // Move pivot to its final place
    return storeIndex;
}

int choosePivot(int lo, int hi) {
    return (int)Math.ceil((hi + lo) / 2);
}

In the next cell, implement the quicksort algorithm.

void quicksort(int[] array, int lo, int hi) {
    if (lo < hi) {
        int p = partition(array, lo, hi);
        quicksort(array, lo, p - 1);
        quicksort(array, p + 1, hi);
    }
}

int partition(int[] array, int lo, int hi) {
    int pivotIndex = choosePivot(lo, hi);
    int pivotValue = array[pivotIndex];
    // put the chosen pivot at array[hi]
    swap(array, pivotIndex, hi);
    int storeIndex = lo;
    // Compare remaining array elements against pivotValue = array[hi]
    for (int i = lo; i <= hi - 1; i++)  {
        if (compare(pivotValue, array[i])) {
             swap(array, i, storeIndex);
             storeIndex = storeIndex + 1;
        }
    }
    swap(array, storeIndex, hi);  // Move pivot to its final place
    return storeIndex;
}

int choosePivot(int lo, int hi) {
    return (int)Math.ceil((hi + lo) / 2);
}

Finally, in the next cell, compare Double Trouble, Bubble, and Quicksort in the numbers of comparisons that they take to sort lists of 100, 1000, 100000, and 1000000 sized arrays.

Sort name	Size	Compares
Double Trouble
Bubble sort
Quicksort

Reflection¶

[In the following cell, give a thorough reflection of what you found and learned in this lab. Think outside the box, too. Is there any situation where one sort would be better than another? Then you can remove this cell.]

Jupyter at Bryn Mawr College