Over and over again, I've seen/heard references to this not-so-mysterious Bible of Algorithms. Today, I decided to obtain it and dive in face-first. Already, one chapter in, I'm glad I kept my Discrete Mathematics book around! While I can't see myself going through every single exercise (it's at least a semester or two worth of work, and I'm already taking a full course load and bla bla excuses), I'll be selecting specific ones that seem to encompass what the section/chapter is about.

First up is Insertion Sort: Which I've implemented on Runnable. Simple enough!

//direct translation of pseudocode fig.2.2 void insertionSortNonDec(int A[], int size) { int key = -1; int i = -1; for (int j = 1; j < size; j++) { //iterates through array, from second through last element key = A[j]; i = ( j - 1 ); //starts as j-1th element... while ( (i>=0) && A[i] > key ) { // and shifts every element to the left until it reaches the first element, A[i+1] = A[i]; // or until it reaches an element less than itself i--; } A[i+1] = key; //at which point, it assigns the next element to be the key, thus inserting it in ltg order } } //nonincreasing adaptation of translation of pseudocode fig.2.2 void insertionSortNonInc(int A[], int size) { int key = -1; int i = -1; for (int j = 1; j < size; j++) { key = A[j]; i = ( j - 1 ); while ( (i>=0) && A[i] < key ) { //this is the only line that needs to change (A[i] < key, rather than > key) A[i+1] = A[i]; i--; } A[i+1] = key; } }

I trust that my analysis abilities will become more robust and informative than "O(x)???" in short order ;p Onward!