Shaker Sort

Everyone who has ever programmed a sort has probably done a Bubble sort (and hopefully lived to tell about it). The truth is is that bubble sorts are incredibly simple. But they do have worst cases, such as a reverse ordered list of items. It would take bubble sort order n^2 time to complete any semi-reverse ordered items. Shaker sorts can help resolve this problem.

Generally bubble sorts move from one end of a list of items to the next. Shaker sorts move from one end of the list to the next and then from the other end of the list to the beginning. Pretty straight forward? Well you can write up a C bubble sort in about 6 lines of code. Shaker sorts take a little bit more, and are a little more complicated, but well worth the study.

Here is a C based example of a shaker sort.

#include

#define key(A) (A)

#define less(A, B) (key(A) <>

#define exch(A, B) {int t = A; A = B; B = t;}

#define compexch(A, B) if(less(B, A)) exch(A, B)

void shaker(int *, int, int);

int main(){

int array[10] = {4, 1, 7, 3, 2, 8, 9, 6, 5};

shaker(array, 0, 9);

int i;

for(i = 1; i < 10; i++){

printf("%d ", array[i]);

}

return 0;

}

void shaker(int *array, int l, int r){

int sorted = 1, i, swaps = 0; // Define two integers. Initialize sorted to 1. Sorted will terminate the while loop if nothing has been sorted.

while(sorted){

sorted = 0; // Always set sorted to 0 just to make sure we can continually test to see if it has been sorted

for(i = l; i <>// This loop will be the left-to-right swapping

if(less(array[i], array[i - 1])){ // Check adjacent elements to see if i is less than  i - 1. Swap them if they are.

exch(array[i - 1], array[i]);

sorted = 1; // Sorted will be set to 1 to make sure we either continue looping or don't.

swaps++;

}

if(sorted == 0) break; // An extra text but it will terminate the function if it is already sorted.

}

for(i = r; i > 0; i--){ // This loop will be the right-to-left swapping

if(less(array[i], array[i - 1])){ // Check adjacent elements to see if i is less than  i - 1. Swap them if they are.

exch(array[i - 1], array[i]); 

sorted = 1; // Sorted will be set to 1 to make sure we either continue looping or don't.

swaps++;

}

if(sorted == 0) break;

}

}

printf("\nIt took a total of %d exchanges to sort the list.\n", swaps);

}

Recursive Postfix Expression Evaluator

In a previous post (here). I created a Reverse Polish Notation calculator which would take digits in along with operators in postfix form and return an evaluated expression. The RPN calculator was implemented using my own Stack data structure (based off of an array). The following program is a postfix expression evaluator which uses recursion as a kind of stack implementation. As operands are found in the expression the eval function goes deeper into the recursion (recurses = push operands on stack). When a operator is found the eval function effectively moves up levels in the recursion (popping) values and performing the necessary operations. Enjoy:

/*

 *  

 *

 *  Created by Devin Eldreth on 11/2/07.

 * This program contains a recursive postfix expression evaluator (eval). A global array of characters is set to a postfix expression.

 * eval is called and recursively evaluates the expression to return the integer result. Current the function only works with single digit operands

 * and any of the four mathematical operators +, -, *, /

 */

#include

#include

char *a; // Define a string to hold the expression

int i = 0, y = 0, skip = 0; // Initilize 3 integer values. y will basically the top of the stack (recursively). 

    //Skip will be the test to see if we have already recursed twice and will increment i

int main(){

//a = "5 9 8 + 6 4 * * 7 + *"; //= 2075 (Problem in book)

//a = "2 6 / 8 *"; //= 24

a = "3 5 4 6 * * * 2 / 3 -"; //= 177

printf("\n%s = %d\n", a, eval());

return 0;

}

int eval(){

int x = 0;

for(;;){

while(a[i] == ' ') i++; // Always increment array index if it is just a space

// Return the calculated value y if there is an operator or assume termination when i is the value of the length of the array

// This will actually bring values back from the recursion

if((i == strlen(a)) || (a[i] == '*') || (a[i] == '+') || (a[i] == '-') || (a[i] == '/')) return y;

// Read each array element and recurse after getting the numberical value at index i

while((a[i] >= '0') && (a[i] <= '9')){

x = (a[i++] -'0');

eval();

}

if(a[i] == '*'){ // Handle the multiplicative operator

if(y == 0) y++;

y *= x; 

skip++; // Check to see if the y value is 0 and increment it to handle the initial multiplication. Increment skip.

}

if(a[i] == '+'){ // Handle the addition operator

y = (y == 0) ? x : y + x; 

skip++; // Test to see if y is 0 and set it to x (this isn't quite necessary). Increment skip.

}

if(a[i] == '-'){ // Handle the difference operator

y = (y == 0) ? x : y - x; 

skip++; // Identical to the addition handling test.

}

if(a[i] == '/'){ // Handle the division operator

y = (y == 0) ? x : y / x; 

skip++; // Identical to the addition test.

}

// Check to see if skip is equal to 2. Increment i and set skip equal to 1. This will handle the event that the counter becomes stuck on a single operator.

if(skip == 2) { i++; skip = 1; }

}

}