Page 152
void setup() {
Serial.begin(115200);
int array[] = {8, 4, 9, 3, 7, 2, 6, 1, 10, 76, 0, 21, 4};
bubbleSort(array, 12);
//shellSort(array, 13);
//quickSort(array, 0, 12);
for (int i = 0; i < 13; i++) {
Serial.println(array[i]);
}
}
Page 153
void bubbleSort(int array[], int lastElement) {
bool swap = true;
int hold;
while (swap) {
swap = false;
for (int i = 0; i < lastElement; i++) {
if (array[i] > array[i + 1]) {
swap = true;
hold = array[i];
array[i] = array[i + 1];
array[i + 1] = hold;
}
}
}
}
void shellSort(int array[], int arrayLength) {
int temp;
for (int gap = arrayLength / 2; gap > 0; gap /= 2) {
for (int i = gap; i < arrayLength; i++) {
for (int j = i - gap; j >= 0 && array[j] > array[j + gap]; j -= gap) {
temp = array[j];
array[j] = array[j + gap];
array[j + gap] = temp;
}
}
}
}
Page 154
// quick sort - uses a helper function swap()
// and calls itself recursively
void quickSort(int array[], int left, int right) {
if (left >= right) { return; } //do nothing if < 2 elements
swap(array, left, (left + right) / 2);
int last = left;
for (int i = left + 1; i <= right; i++) {
if (array[i] < array[left]) {
swap(array, ++last, i);
}
}
swap(array, left, last);
quickSort(array, left, last - 1);
quickSort(array, last + 1, right);
}
void swap(int array[], int elem1, int elem2) {
int hold = array[elem1];
array[elem1] = array[elem2];
array[elem2] = hold;
}
Page 156
void setup() {
Serial.begin(115200);
int array[] = {8, 4, 9, 3, 7, 2, 6, 1, 10, 76, 0, 21, 4};
shellSort(array, 13);
reverseArray(array, 12);
for (int i = 0; i < 13; i++) {
Serial.println(array[i]);
}
}
void reverseArray(int array[], int lastElement) {
for(int i = 0, j = lastElement; i < j; i++, j--) {
xorSwap(array, i, j);
}
}
void xorSwap(int array[], int a, int b){
if(a != b) {
array[a] ^= array[b];
array[b] ^= array[a];
array[a] ^= array[b];
}
}
void shellSort(int array[], int arrayLength) {
shellSort(array, arrayLength, ASC);
}
void shellSort(int array[], int arrayLength, Sort_Order so) {
for(int gap = arrayLength / 2; gap > 0; gap /= 2) {
for (int i = gap; i < arrayLength; i++) {
for (int j = i - gap; j >=0 && ((so == ASC) ? array[j] > array[j + gap] : array[j] < array[j + gap]); j -= gap) {
xorSwap(array, j, j + gap);
}
}
}
}
void xorSwap(int array[], int a, int b){
if(a != b) {
array[a] ^= array[b];
array[b] ^= array[a];
array[a] ^= array[b];
}
}
Page 157
void quickSort(int array[], int lastElement) {
quickSort(array, 0, lastElement, ASC);
}
void quickSort(int array[], int lastElement, Sort_Order so) {
quickSort(array, 0, lastElement, so);
}
void quickSort(int array[], int firstElement, int lastElement){
quickSort(array, firstElement, lastElement, ASC);
}
void quickSort(int array[], int firstElement, int lastElement, Sort_Order so){
if(firstElement > lastElement) { return; }
xorSwap(array, firstElement, (firstElement + lastElement) / 2);
int last = firstElement;
for(int i = firstElement + 1; i <= lastElement; i++) {
if((so == ASC) ? array[i] < array[firstElement] : array[i] > array[firstElement]) {
xorSwap(array, ++last, i);
}
}
xorSwap(array, firstElement, last);
quickSort(array, firstElement, last - 1, so);
quickSort(array, last + 1, lastElement, so);
}
enum Sort_Order {ASC, DESC};
void setup() {
Serial.begin(115200);
int array[] = {8, 4, 9, 3, 7, 2, 6, 1, 10, 76, 0, 21, 4};
shellSort(array, 13, DESC);
//shellSort(array, 13);
//quickSort(array, 12);
//quickSort(array, 0, 12, ASC);
//quickSort(array, 12, DESC);
for (int i = 0; i < 13; i++) {
Serial.println(array[i]);
}
}
int compIntAsc(int a, int b) {
if (a == b) {return 0;}
return (a < b) ? -1 : 1;
}
int compIntDsc(int a, int b) {
if(a == b) {return 0;}
return (b < a) ? -1 : 1;
}
Page 158
void shellSort(int array[], int arrayLength, int* cmp(int, int)) {
int temp;
for (int gap = arrayLength / 2; gap > 0; gap /= 2) {
for (int i = gap; i < arrayLength; i++) {
for (int j = i - gap; j >= 0 && cmp(array[j], array[j + gap]) == 1; j -= gap) {
xorSwap(array, j, j + gap);
}
}
}
}
void setup() {
Serial.begin(115200);
int array[] = {8, 4, 9, 3, 7, 2, 6, 1, 10, 76, 0, 21, 4};
//shellSort(array, 13, compIntAsc);
shellSort(array, 13, compIntDsc);
for (int i = 0; i < 13; i++) {
Serial.println(array[i]);
}
}
Pages 160 & 161
const char w1[] = "autocracy";
const char w2[] = "democracy";
const char w3[] = "Democrat";
const char w4[] = "oligarchy";
const char w5[] = "autocrat";
const char w6[] = "aristocrat";
const char w7[] = "bureaucracy";
const char w8[] = "technocrat";
const char w9[] = "oligarch";
const char w10[] = "matriarch";
const char w11[] = "Reservoir";
const char w12[] = "squash";
const char w13[] = "matriarch";
char* wordArray[] = {w1, w2, w3, w4, w5, w6, w7, w8, w9, w10, w11, w12, w13};
void setup() {
Serial.begin(115200);
wQSort(wordArray, 0, 12, true);
for(int i = 0; i < 13; i++){
Serial.println(wordArray[i]);
}
}
// the quick sort function looks like you would expect
// with an added ignoreCase argument
void wQSort( char* array[], int left, int right, bool ignoreCase) {
if(left > right) {return; }
swap(array, left, (left + right) / 2);
int last = left;
for(int i = left + 1; i <= right; i++) {
if(compStr(wordArray[i], wordArray[left], ignoreCase) < 0) {
swap(array, ++last, i);
}
}
swap(array, left, last);
wQSort(array, left, last - 1, ignoreCase);
wQSort(array, last + 1, right, ignoreCase);
}
// the swap simply swaps the pointers – the strings are untouched
void swap( char* array[], int a, int b) {
char * temp = array[a];
array[a] = array[b];
array[b] = temp;
}
// the comparison loops through the two strings until
// there is a difference or one ends
int compStr( char* a, char* b, bool ignoreCase) {
for(; (ignoreCase) ? (tolower(*a) == tolower(*b)) : (*a == *b); a++, b++) {
if(*a == '\0' || *b == '\0') { // end of one of the strings
if(*a == *b) {return 0;} // both words the same
break;
}
}
// return the difference between the char ASCII codes
return (ignoreCase) ? tolower(*a) - tolower(*b) : *a - *b;
}
Page 162
void setup() {
Serial.begin(115200);
long lArray[] = {764, 123, 9854, 3, 999, 97, 6, 78, 123, 0, 5};
qsort(lArray, 11, sizeof(long), lComp);
for (int i = 0; i < 11; i++) {
Serial.println(lArray[i]);
}
}
int lComp(const void *a, const void *b) {
if(*(long*)a < *(long*)b) {return -1;}
if(*(long*)b < *(long*)a) {return 1;}
return 0;
}
Page 163
int binarySearch(int array[], int arrayLength, int target) {
int low = 0;
int high = arrayLength - 1;
while (low <= high) {
int mid = (low + high) >> 1;
int midVal = array[mid];
if (midVal < target) {
low = ++mid;
} else if(midVal > target){
high = --mid;
}
else {
return mid; // found it
}
}
return -1; //not found
}
