|
Jupyter at Bryn Mawr College |
|
|
| Public notebooks: /services/public/dblank / CS110 Intro to Computing / 2017-Fall / Notebooks | |||
Algorithms¶
An algorithm is a well-defined, complete, step-by-step description that performs a process in a finite amount of time and space.
In [93]:
void setup() {
int[] heights = new int[100];
for (int i = 0; i < heights.length; i++) {
heights[i] = int(random(500));
}
int b = biggest(heights);
int s = smallest(heights);
printArray(heights);
println("Biggest: " + b + " Smallest: " + s);
}
int biggest(int[] arr) {
// what goes here?
int max = arr[0];
for (int i = 1; i < arr.length; i++) {
if (arr[i] > max) {
max = arr[i];
}
}
return max;
}
int smallest(int[] arr) {
int min = arr[0];
for (int i=1; i < arr.length; i++) {
if (arr[i] < min) {
min = arr[i];
}
}
return min;
}
void printArray(int[] myarray) {
print("[");
for (int i = 0; i < myarray.length; i++) {
print(myarray[i]);
if (i != myarray.length - 1) {
print(", ");
}
}
println("]");
}
Sorting¶
Double Trouble¶
Let's design a very bad (slow) algorithm for sorting numbers.
The Double Trouble sort algorithm, stated very abstractly:
Compare all combinations of values at positions i and j:
Swap where item at i is greater than the item at jThe Squared sort algorithm, stated with more details about an implementation:
Starting at the first element and going to second-to-last item, call this i:
Starting at i + 1, and going to last item, call this j:
if the item at location i is greater than the item at location j:
Swap the items at i and j
end if
end j loop
end i loopAn algorithm is not so specific that it requires that it be written in a computer language. However, it is specific enough that it can be written in a programming language.
Sidebar: swapping¶
The problem with swapping: You can't do this to swap the values of x and y:
x = y;
y = x;Why not?
Solution:
temp = x;
x = y;
y = temp;In [95]:
int[] heights = new int[100];
void setup() {
for (int i = 0; i < 100; i++) {
heights[i] = int(random(50));
}
printArray(heights);
double_trouble_sort(heights);
printArray(heights);
}
void double_trouble_sort(int[] myarray) {
for (int i = 0; i < myarray.length - 1; i++) {
for (int j = i + 1; j < myarray.length; j++) {
if (myarray[i] > myarray[j]) {
// swap
int temp = myarray[i];
myarray[i] = myarray[j];
myarray[j] = temp;
}
}
}
}
void printArray(int[] myarray) {
print("[");
for (int i = 0; i < myarray.length; i++) {
print(myarray[i]);
if (i != myarray.length - 1) {
print(", ");
}
}
println("]");
}
Using Double Trouble to Sort Colors¶
In [96]:
PImage pic;
int p;
PImage big;
void setup() {
size(500, 500);
colorMode(HSB, 255);
pic = createImage(25, 25, RGB);
pic.loadPixels();
for (int i=0; i < pic.pixels.length; i++) {
pic.pixels[i] = color(random(255), 255, 255);
}
pic.updatePixels();
p = 0;
big = createImage(width, height, RGB);
}
void double_trouble_sort(PImage pic) {
// outer loop removed, so we can see the pixels sort!
pic.loadPixels();
for (int j=p + 1; j < pic.pixels.length; j++) {
if (hue(pic.pixels[p]) > hue(pic.pixels[j])) {
color temp = pic.pixels[p];
pic.pixels[p] = pic.pixels[j];
pic.pixels[j] = temp;
}
}
pic.updatePixels();
}
void draw() {
background(0);
double_trouble_sort(pic);
big.copy(pic,0,0,pic.width,pic.height,0,0,width,height);
image(big, 0, 0);
p++;
if (p >= pic.pixels.length - 2) {
noLoop();
println("Done!");
}
}
Bubble Sort¶
Bubble sort is the name given to a simple, and somewhat interesting, sorting algorithm.
The Bubblesort algorithm in abstract terms:
While not done:
Run through all items in a set, i:
if item i is greater than item i + 1:
Swap items i and i + 1
If no swaps were made on last sweep, you are doneThe Bubblesort algorithm, with more implementation details:
Let stop be the length of the array
While stop is not at the beginning:
Starting at the first element and going to stop - 1, call this i:
Let new_stop be the beginning position
if the item at location i is greater than the item at location i + 1:
swap the items at i and i + 1
Save i as new_stop
end if
Let stop be new_stop
end whileAnd written in Java:
void bubble_sort(int[] array) {
int stop = array.length;
int last_swap;
while (stop != 0) {
last_swap = 0;
for (int i = 0; i < stop - 1; i++) {
if (array[i] > array[i + 1]) {
color temp = array[i];
array[i] = array[i + 1];
array[i + 1] = temp;
last_swap = i + 1;
}
}
stop = last_swap;
}
}
Buuble Sort on Colors¶
In [97]:
PImage pic;
PImage big;
int stop;
void setup() {
size(500, 500);
colorMode(HSB, 255);
pic = createImage(25, 25, RGB);
pic.loadPixels();
for (int i=0; i < pic.pixels.length; i++) {
pic.pixels[i] = color(random(255), 255, 255);
}
pic.updatePixels();
big = createImage(width, height, RGB);
stop = pic.pixels.length;
}
void bubble_sort(PImage pic) {
pic.loadPixels();
//int stop = pic.pixels.length;
int last_swap;
if (stop != 0) {
last_swap = 0;
for (int i = 0; i < stop - 1; i++) {
if (hue(pic.pixels[i]) > hue(pic.pixels[i + 1])) {
color temp = pic.pixels[i];
pic.pixels[i] = pic.pixels[i + 1];
pic.pixels[i + 1] = temp;
last_swap = i + 1;
}
}
stop = last_swap;
} else {
noLoop();
println("Done!");
}
pic.updatePixels();
}
void draw() {
background(0);
bubble_sort(pic);
big.copy(pic,0,0,pic.width,pic.height,0,0,width,height);
image(big, 0, 0);
}
Quick Sort¶
The final algorithm that we will look at today is Quicksort. Quicksort represents a class of algorithms in computer science that capture the motto "divide and conquer".
The Quicksort algorithm, at 30,000 feet (abstract view):
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 partThe 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 endThe 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 partitionIn Java, the main quicksort function looks like:
void quicksort(int lo, int hi) {
if (lo < hi) {
int p = partition(lo, hi);
quicksort(lo, p - 1);
quicksort(p + 1, hi);
}
}
Here is the whole algorithm in code:
In [99]:
int [] array;
void quicksort(int lo, int hi) {
if (lo < hi) {
int p = partition(lo, hi);
quicksort(lo, p - 1);
quicksort(p + 1, hi);
}
}
int partition(int lo, int hi) {
int pivotIndex = choosePivot(lo, hi);
int pivotValue = array[pivotIndex];
// put the chosen pivot at array[hi]
int tmp = array[pivotIndex];
array[pivotIndex] = array[hi];
array[hi] = tmp;
int storeIndex = lo;
// Compare remaining array elements against pivotValue = array[hi]
for (int i = lo; i <= hi - 1; i++) {
counter++;
if (array[i] < pivotValue) {
swap++;
tmp = array[i];
array[i] = array[storeIndex];
array[storeIndex] = tmp;
storeIndex = storeIndex + 1;
}
}
tmp = array[hi];
array[hi] = array[storeIndex];
array[storeIndex] = tmp;
return storeIndex;
}
int choosePivot(int lo, int hi) {
return ceil((hi + lo) / 2);
}
void print_array() {
for (int i = 0; i < array.length; i++) {
print("" + array[i] + ", ");
}
println("");
}
void setup() {
println("-----------------------------------------------------------------");
array = new int [1000];
for (int i = 0; i < array.length; i++) {
array[i] = int(random(array.length));
}
println("Before sorting:");
if (array.length < 100)
print_array();
int start = millis();
quicksort(0, array.length - 1);
int stop = millis();
println("Quicksort took: " + (stop - start) + " ms");
if (array.length < 100)
print_array();
}
Quick Sort applied to Colors¶
In [100]:
PImage pic;
PImage big;
void quicksort(int lo, int hi) {
if (lo < hi) {
int p = partition(lo, hi);
quicksort(lo, p - 1);
quicksort(p + 1, hi);
}
}
int partition(int lo, int hi) {
int pivotIndex = choosePivot(lo, hi);
int pivotValue = pic.pixels[pivotIndex];
// put the chosen pivot at pic.pixels[hi]
color tmp = pic.pixels[pivotIndex];
pic.pixels[pivotIndex] = pic.pixels[hi];
pic.pixels[hi] = tmp;
int storeIndex = lo;
// Compare remaining array elements against pivotValue = pic.pixels[hi]
for (int i = lo; i <= hi - 1; i++) {
if (hue(pic.pixels[i]) < hue(pivotValue)) {
tmp = pic.pixels[i];
pic.pixels[i] = pic.pixels[storeIndex];
pic.pixels[storeIndex] = tmp;
storeIndex = storeIndex + 1;
}
}
tmp = pic.pixels[hi];
pic.pixels[hi] = pic.pixels[storeIndex];
pic.pixels[storeIndex] = tmp;
return storeIndex;
}
int choosePivot(int lo, int hi) {
return ceil((hi + lo) / 2);
}
void print_array() {
for (int i = 0; i < pic.pixels.length; i++) {
print("" + pic.pixels[i] + ", ");
}
println("");
}
void draw() {
background(0);
quicksort(0, pic.pixels.length - 1);
big.copy(pic,0,0,pic.width,pic.height,0,0,width,height);
image(big, 0, 0);
}
void setup() {
size(500, 500);
colorMode(HSB, 255);
pic = createImage(25, 25, RGB);
pic.loadPixels();
for (int i=0; i < pic.pixels.length; i++) {
pic.pixels[i] = color(random(255), 255, 255);
}
pic.updatePixels();
big = createImage(width, height, RGB);
}