Example of Huffman Algorithm by using Heap

Example of Huffman algorithm by using heap.

NOTIFICATION: These examples are provided for educational purposes. Using this code is under your own responsibility and risk. The code is given ‘as is’. I do not take responsibilities of how they are used.

huffman.c:

/* 
 * Program: Huffman using heap
 * Author: Alejandro G. Carlstein
 */

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

#define MAX_CODE 1000000
#define MAX_LETTERS 4
#define MAX_HEAP 10
#define LEFT(i) ((i << 1) + 1)
#define RIGHT(i) ((i << 1) + 2)
#define PARENT(i) (((i + 1) >> 1) - 1)
#define DIV_BY_2(i) (i >> 1)
#define DBG_LV0 1
#define DBG_LV1 1
#define DBG_LV2 1
#define DBG_LV3 0
#define LETTER_A 65
#define DIR_LEFT '0'
#define DIR_RIGHT '1'

#define ROOT_INDEX 0

struct Data{
  int letter;
  int frequency;
  int left;
  int right;
  int parent;
}Data;

struct Data data[MAX_LETTERS];
int code[MAX_CODE][MAX_LETTERS];
int heap[MAX_HEAP];

void readInputLetters(void);
void readInputCode(void);
void printCodes(int *codes, int numCodes);
void printStructArray(struct Data array[], int length);
int huffman(void);
void buildMinHeap(int array[], int heapSize);
void minHeapify(int array[], int index, int heapSize);
int heapMin(int array[]);
int heapExtractMin(int array[], int *length);
void insertMinHeap(int array[], int value, int *length);
void exchange(int *a, int *b);
void printArray(int array[], int length);
int isLeft(struct Data array[], int indexLeft, int indexRight);
void test1();
void test2();

int num_letters;
int numCodes = 0;

int main(int argc, char* argv[]){

	readInputLetters();		

	readInputCode();

	if (DBG_LV3) printStructArray(data, num_letters);

	int i;
	for (i = 0; i < num_letters; ++i)
		heap[i] = i;

  printf('ROOT(huffman): %d \n', huffman());

	if (DBG_LV1) printStructArray(data, num_letters);

  //decodeMessage(data, num_letters, &code[0][0], numCodes);

	if (DBG_LV2) printf('\n');

	return 0;

}

void readInputLetters(void){
	if (DBG_LV0) printf('\nreadInputLetters()\n');

  for (num_letters = 0; num_letters < MAX_LETTERS; ++num_letters){       
    scanf('%d', &data[num_letters].frequency);
    data[num_letters].letter = LETTER_A + num_letters;
    data[num_letters].left = -1;
    data[num_letters].right = -1;
		data[num_letters].parent = -1;

    heap[num_letters] = -1;
  }

}

void readInputCode(void){
	if (DBG_LV0) printf('\nreadInputCode()\n');

	int c;
  int indexCode = 0;

  numCodes = 0;

  while ((c = getchar()) != EOF){

    if (c != ' ' && c != '\n'){
      if (DBG_LV3) printf('[%d][%d]%c{%d}\n', numCodes, indexCode, c, c);
      code[numCodes][indexCode] = (int)c;
      ++indexCode;
    }

    if (c == '\n'){
      code[numCodes][indexCode] = -1;
      if (DBG_LV3) printf('{{%d}}\n', code[numCodes][indexCode]);
      ++numCodes;
      indexCode = 0;

    }
  }

	if (DBG_LV3){
	  printf('CODES: \n');
	  printCodes(&code[0][0], numCodes);

  }

}

void printCodes(int *codes, int numCodes){
  if (DBG_LV2) printf('printCodes(numCodes: %d)\n', numCodes);

  int indexCode, index;
	int indexArray;

  for (indexCode = 0; indexCode < numCodes; ++indexCode){

		indexArray = indexCode * sizeof(int);

    for (index = 0; codes[indexArray + index] > -1 ; ++index){

      printf('[%d][%d]: %c(%d) \n', 
             indexArray, index, 
             codes[indexArray + index], codes[indexArray + index]);    

    }

    printf('\n');

  }

}

void printStructArray(struct Data array[], int length){
  if (DBG_LV0) printf('printStructArray()\n');

  int i;
  for (i = 0; i < length; ++i)
	  printf('[%d]%c - %d (L:%d, R:%d, P:%d) \n',
	         i, data[i].letter, data[i].frequency, data[i].left, data[i].right, data[i].parent);
}

int huffman(void){
	if (DBG_LV0) printf('\nHUFFMAN()\n');

	int length = num_letters;
	int i;
	int left;
	int right;
	int parent;
	int n = length;

	length++;

	printf('length: %d\n\n', length);

	if (DBG_LV1) printArray(heap, num_letters);

	for (i = 0; i < n - 1; ++i){

		left = heapExtractMin(heap, &length);

		printf('length: %d\n\n', length);

		right = heapExtractMin(heap, &length);

		parent = left + right;

		data[left].parent = parent;
		data[right].parent = parent;

		printf('length: %d\n\n', length);

		if (DBG_LV2){
			printf('left: %d, ', left);				
			printf('right: %d, ', right);
			printf('parent: %d\n', parent);
			printArray(heap, length);		
		}

		insertMinHeap(heap, parent, &length);

		printf('length: %d\n\n', length);
		//--*length;

	}

	if (DBG_LV1) printArray(heap, num_letters);

	return heapExtractMin(heap, &length);
}

void buildMinHeap(int array[], int heapSize){

	int index;

	for (index = DIV_BY_2(heapSize); index >= ROOT_INDEX; --index){

		minHeapify(array, index, heapSize);

	}

}

void minHeapify(int array[], int index, int heapSize){

	int left, right, smallest;

	smallest = index;
	left = LEFT(index);
	right = RIGHT(index);	

	// Find smallest value
	if (left < heapSize && array[left] < array[index])
		smallest = left;	

	if (right < heapSize && array[right] < array[smallest]) 
		smallest = right;

	if (smallest != index){

		// Exchange 
		exchange(&array[index], &array[smallest]);

		// Rebuild heap region		
		minHeapify(array, smallest, heapSize);	

	}

}

int heapMin(int array[]){
	return array[ROOT_INDEX];
}

int heapExtractMin(int array[], int *length){
	if (DBG_LV0) printf('heapExtractMin()\n');

	if (length < 0){
		printf('[X] Error: heap overflow!\n');
		return -1;
	}

	--*length;

	int heapSize = *length;

	int min = array[ROOT_INDEX];

	--heapSize;

	printf('exchange: array[%d]: %d, array[%d]:%d \n',
				 ROOT_INDEX, array[ROOT_INDEX],
				 heapSize, array[heapSize]);

	exchange(&array[ROOT_INDEX], &array[heapSize]);

	--heapSize;

	minHeapify(array, ROOT_INDEX, heapSize);

	return min;
}

void insertMinHeap(int array[], int value, int *length){

	if (DBG_LV0) printf('insertMinHeap(value: %d, length: %d)\n',
											value, *length);

	int heapSize = *length;

	++*length;

	array[heapSize] = INT_MAX;

	if (value > array[heapSize]){
		printf('[X] Error: new value is bigger than biggest element!\n');
	}else{

		array[heapSize] = value;

		if (DBG_LV2) printArray(array, *length);

		while (heapSize > ROOT_INDEX && 
					 array[PARENT(heapSize)] > array[heapSize]){

			exchange(&array[heapSize], &array[PARENT(heapSize)]);

			heapSize = PARENT(heapSize);

		}

	}

}

void exchange(int *a, int *b){
		if (DBG_LV3) printf('exchange()\n');

		int temp;
		temp = *a;
		*a = *b;
		*b = temp;
}

void printArray(int array[], int length){
	if (DBG_LV0) printf('printArray()\n');

	int i;

	for (i = 0; i < length; ++i)
		printf('[%d]', i);

	printf('\n');

	for (i = 0; i < length; ++i)
		printf(' %d ', array[i]);

	if (DBG_LV1) printf('\n\n');
}

int isLeft(struct Data array[], int indexLeft, int indexRight){
	if (DBG_LV0) printf('isLeft()\n');

	if (array[indexLeft].frequency == array[indexRight].frequency){

		 	if (array[indexLeft].letter < array[indexRight].letter){
		 		return DIR_LEFT;
		 	}else{
		 		return DIR_RIGHT;
		 	}

	}else if (array[indexLeft].frequency < array[indexRight].frequency){
		return DIR_LEFT;	 	
	}else{
		return DIR_RIGHT;
	} 

}

void test1(){
	if (DBG_LV1) printf('test1()\n');

	int i, length = 5;

	if(DBG_LV1)	printf('BUILD HEAP ARRAY:\n');
	for(i = 0; i < length; ++i){
		heap[i] = i * 2;
		printf('heap[%d]: %d \n', i, heap[i]);
	}
	heap[4] = 1;

	buildMinHeap(heap, length);

	printArray(heap, length);

	insertMinHeap(heap, 3, &length);

	printArray(heap, length);
}

void test2(){

	int heapLen = num_letters;

	printf('heapLen: %d\n', heapLen);

	printArray(heap, heapLen);

	int result1, result2;

	printf('TEST HEAPEXTRACTMIN:\n');
	result1 = heapExtractMin(heap, &heapLen);
  printf('result1: %d\n', result1);
	printArray(heap, heapLen);

	printf('heapLen: %d\n', heapLen);

	result2 = heapExtractMin(heap, &heapLen);
  printf('result2: %d\n', result2);
	printArray(heap, heapLen);

	printf('heapLen: %d\n', heapLen);

}

input.txt:

1 
2 
3 
4 
1 0 0 
1 0 1 
1 1 
0

If you encounter any problems or errors, please let me know by providing an example of the code, input, output, and an explanation. Thanks.

Share
Leave a comment

Example of Ferry Loading Algorithm

Example of Ferry Loading algorithm.

NOTIFICATION: These examples are provided for educational purposes. Using this code is under your own responsibility and risk. The code is given ‘as is’. I do not take responsibilities of how they are used.

ferry_loading.c:

/**
 * Ferry Loading Algorithm
 * @author: Alejandro G. Carlstein R. M. 
 */
#include <stdio.h>

/* Macros Functions */
#define max(a,b) \
           ({ typeof (a) _a = (a); \
              typeof (b) _b = (b); \
            _a > _b ? _a : _b; })

/* Debugging flags */
#define DBG_LV1 0
#define DBG_LV2 1
#define DBG_LV3 0

/* Constants */
#define MAX_NUM_CAR 100
#define MAX_FERRY_LEN 100

enum{ UNKNOWN = -1, LEFT = 0, RIGHT = 1,
};

/* Our dynamic programming table element.  We have the value
 * that we can store, and also a way to remember what we selected.
 */
typedef struct{
  int length;
  int prev_row;
  int prev_col;
} Table;

int cars[MAX_NUM_CAR];
int side[MAX_NUM_CAR];
int i, j;
int ferry_len;
int total_cars;

// [ROW] [COLUMN]
Table ferry[MAX_FERRY_LEN][MAX_FERRY_LEN];

/*
 *
 */
int main(int argc, char *argv[]){

  /* Read the length of the ferry */
  scanf('%d', &ferry_len);

  // Read length of each car and set side to UNKNOWN since
  // we haven't decided yet where they will go
  cars[0] = 0;
  side[0] = UNKNOWN;
  for (i = 1; scanf('%d', &cars[i]) == 1; ++i){
    side[i] = UNKNOWN;
  };
  total_cars = i;

  // Initialize the first row and the first column
  for (i = 0; i <= ferry_len; ++i)
    ferry[0][i].length = ferry[i][0].length = 0;
    ferry[0][i].prev_row = ferry[i][0].prev_col = 0;

  // Print info
  if (DBG_LV2){
    printf('\nLength of Ferry: %d \n', ferry_len);
    printf('Number of Cars: %d \n\n', total_cars);

    for (i = 0; i < total_cars; ++i)
      printf('Car[%d]: %d length\n',
             i, cars[i]);
    printf('************************************\n');
  }//end if

  // Fill table
  int result = recursive_ferry(0,0,0, ferry_len);

  if (DBG_LV2){
    printf('Result: %d length value\n',  result);
  }

  if (DBG_LV2)
    print_tables();

  // Track back foot steps
  if (DBG_LV2)  printf('tracking(%d, %d, %d)\n\n', ferry_len, ferry_len, total_cars);
  tracking(ferry_len, ferry_len, total_cars);

  // Print results
  if (DBG_LV2) printf('\n SIDE: \n');

  for (i = 1; i < total_cars; ++i)
    switch(side[i]){
      case UNKNOWN:
        if (DBG_LV2) printf('UNKNOWN side[%d]: %d\n', i, side[i]);
        break;

      case RIGHT:
        if (DBG_LV2) printf('RIGHT side[%d]: %d\n', i, side[i]);
        printf('right\n');
        break;

      case LEFT:
        if (DBG_LV2) printf('LEFT side[%d]: %d\n', i, side[i]);
        printf('left\n');
        break;

    };

  return 0;
}

/*
 *
 */
int tracking(int left, int right, int idx_car){

  if (1) printf('\ntracking(%d,%d,%d)\n', left, right, idx_car);

  if (idx_car < 0)
    return;

  if (DBG_LV2) printf('.1 ');

  if (ferry[left][right].length == 0)
    return;

  if (DBG_LV2) printf('.2 ');

  --idx_car;

  int prev_len = (left + right) - cars[idx_car];
  int prev_left = left - cars[idx_car];
  int prev_right = right - cars[idx_car];

  if (DBG_LV2) printf('prev_len: %d = (%d + %d) - %d (car[%d])\n', prev_len, left, right, cars[idx_car], idx_car);

  if (ferry[prev_left][right].length == prev_len && prev_left >= 0){

    if (DBG_LV2) printf('ferry[prev_LEFT: %d][right: %d] MATCH [from RIGHT]\n', prev_left, right);

    side[idx_car] = RIGHT;

    tracking (prev_left, right, idx_car);

  }else  if (ferry[left][prev_right].length == prev_len && prev_right >= 0){

    if (DBG_LV2) printf('ferry[left: %d][prev_RIGHT: %d] MATCH [from LEFT]\n', left, prev_right);

    side[idx_car] = LEFT;    

    tracking (left, prev_right, idx_car);

  }else{

    if (DBG_LV2) printf('ferry[prev_left][right] and ferry[left][prev_right] DO NOT MATCH\n');
    tracking (left, right, idx_car);  

  }//end if

  return;
}

/*
 *
 */
int recursive_ferry(int left, int right, int idx_car, int ferry_len){

  if (DBG_LV1) printf('r_f(left: %d, right: %d, idx_car: %d (car_len: %d) \n',
                      left, right, idx_car, cars[idx_car]);

  if (left > ferry_len || right > ferry_len || idx_car > total_cars)
    return 0;

  if (ferry[left][right].length > 0){
    if (DBG_LV3) printf('++Return length: %d \n', ferry[left][right].length);
    return ferry[left][right].length;
  }// end if

  // Store value in ferry
  ferry[left][right].length += (left + right);

  // Record foot steps
  int nxt_row = ferry[left][right].prev_row = left;
  int nxt_col = ferry[left][right].prev_col = right;

  //
  int rtn_left = recursive_ferry(left + cars[idx_car], right, idx_car + 1, ferry_len);
  int rtn_right = recursive_ferry(left, right + cars[idx_car], idx_car + 1, ferry_len);

  if (DBG_LV1 && (rtn_left == 0))
    printf('L>');

  if (DBG_LV1)
    printf('[%d,%d](%d | %d)', nxt_row, nxt_col, rtn_left, rtn_right);

  if (DBG_LV1 && (rtn_right == 0))
    printf('<R');

  if (DBG_LV2) printf('\n');
  // Obtain the result of the best route
  return max(rtn_left, rtn_right);
}                    

/*
 *
 */
int print_tables(void){

    printf('\n\nTABLE\n ');
    for (i = 0; i <= ferry_len; ++i)
      printf(' %d ',i);
    printf('\n');

    for (i = 0; i <= ferry_len; ++i){
      for (j = 0; j <= ferry_len; ++j){
        if (j == 0) printf('%d', i);
        printf (' %d ', ferry[i][j].length);
      }// end for
      printf('\n');
    }//end for
    printf('\n');

    printf('\n TABLE XY\n ');
    for (i = 0; i <= ferry_len; ++i)
      printf(' [ %d ]',i);
    printf('\n');

    for (i = 0; i <= ferry_len; ++i){
      for (j = 0; j <= ferry_len; ++j){
        if (j == 0) printf('%d ', i);
        printf('[%d,%d] ', ferry[i][j].prev_row, ferry[i][j].prev_col);
      }//end for
      printf('\n');
   }//end for
   printf('\n');

  return 0;
}

If you encounter any problems or errors, please let me know by providing an example of the code, input, output, and an explanation. Thanks.

Share
Leave a comment

Example of Knapsack Algorithm

Example of Knapsack algorithm.

NOTIFICATION: These examples are provided for educational purposes. Using this code is under your own responsibility and risk. The code is given ‘as is’. I do not take responsibilities of how they are used.

knapsack.c:

/**
 * Knapsack Algorithm
 * @author: Alejandro G. Carlstein R. M.
 * @description: Simple Knapsack algorithm
 */
#include <stdio.h>

/* Macros Functions */
#define max(a,b) \
           ({ typeof (a) _a = (a); \
              typeof (b) _b = (b); \
            _a > _b ? _a : _b; })

/* Debugging flags */
#define DBG_LV1 0
#define DBG_LV2 0

/* Constants */
#define MAX_STRING_LEN 80
#define MAX_ITEMS 100
#define MAX_WEIGHT 1000

/* This is an item we can put into the knapsack. */
typedef struct{
  char name[MAX_STRING_LEN];
  int weight;
  int value;
} item;

/* Our dynamic programming table element.  We have the value
 * that we can store, and also a way to remember what we selected.
 */
typedef struct{
  int value;
  int prev_row;
  int prev_column;
} prog;

void print_table(int num_items, int max_weight);
void print_table_prev_xy(int num_items, int max_weight);

/* The actual DP table, and the items.  Note that we have an extra
 * row and column in the table for the 'zero elements' and 'no weight'
 * situation.
 */
prog table[MAX_ITEMS + 1][MAX_WEIGHT + 1];

item items[MAX_ITEMS];

int main(int argc, char *argv[]){

  int num_items; // Number of items
  int w; // Weight
  int max_weight;
  int n; // Item number;
  int i, j;
  int diff_weight;

  /* Read in the maximum weight and number of items. */
  scanf('%d %d', &max_weight, &num_items);

  if (DBG_LV2){
    printf('\nMax Weight: %d, Number of Items: %d \n\n', max_weight, num_items);
    printf('READ ITEMS\nw v name\n');
  }//end if

  /* Read in the items */
  for (n = 0; n < num_items; ++n){
      scanf('%d %d %s',
            &items[n].weight,
            &items[n].value,
            items[n].name);

     if (DBG_LV1)
        printf('%d %d %s\n',
               items[n].weight,
               items[n].value,
               items[n].name);
  }//end for

  if(DBG_LV2)
    printf('\n');

  /* Initialize the first row of the table. */
  for (w = 0; w <= max_weight; ++w){
      table[0][w].value = 0;
      table[0][w].prev_row = table[0][w].prev_column = -1;
  }//end for

  // Fill in the table
  // Your code goes here.
  // Should be a for loop for the items, a for loop for the weight,
  // and inside all of that, a few if statements to determine if you
  // can take an item -- and if so, do you want to?
  //
  // I strongly recommend printing out EVERY DECISION your program
  // makes while debugging things -- and feed your program very small
  // problems until it's running.
  //
  // Debugging code is an important skill.  If you can work through a
  // problem by hand, you should be able to get your code to solve the
  // same thing.

  /* Initialize the first column of the table */
  for (i= 0; i <= num_items; ++i){
    table[i][0].value = 0;
  }

  if (DBG_LV2){
    printf('TABLE VALUES\n');
    print_table(num_items, max_weight);
  }//end if

  if (DBG_LV2){
    printf('TABLE PREVIOUS COORDINATES\n');
    print_table_prev_xy(num_items, max_weight);
  }//end if

  // Perform knapsack and find maximun value
  for (i = 1; i <= num_items; ++i){

    for (w = 0; w <= max_weight; ++w){

  		table[i][w].prev_row = i - 1;
		  table[i][w].prev_column = w;			

			// Check if item fit inside the knapsack

			if(items[i - 1].weight <= w) {

        int diff_weight = w - items[i - 1].weight;

        // Check which value is higher
				table[i][w].value = max((items[i - 1].value +
                    				    table[i - 1][diff_weight].value),
                    				    table[i - 1][w].value);

        // Keep track of the previous column
				if(table[i][w].value > table[i - 1][w].value)

					table[i][w].prev_column = diff_weight;

			}else{

				table[i][w].value = table[i - 1][w].value;

			}//end if

    }//end for

  }//end for

  if (DBG_LV2){
    printf('************\n\n');
  }//end if

  if (DBG_LV2){
    printf('TABLE VALUES\n');
    print_table(num_items, max_weight);
  }//end if

  if (DBG_LV2){
    printf('TABLE PREVIOUS COORDINATES\n');
    print_table_prev_xy(num_items, max_weight);
  }//end if

  // In my code, the maximum value is here.
  // I can use the prev_row and prev_column to trace back the solution.
  if (DBG_LV1)
    printf('Maximum value is %d\n', table[num_items][max_weight].value);

  if (DBG_LV2){
    printf('************\n\n');
  }//end if

  // Print results:

  w = max_weight;

  int count = -1;

	int t;

	int total_weight = 0;

  item *p_items[MAX_ITEMS];

	for(i = num_items;
	    i > 0;
	    t = w,
	    w = table[i][w].prev_column,
	    i = table[i][t].prev_row){

		if(table[i][w].value != table[i - 1][w].value){

			total_weight += items[i - 1].weight;

			p_items[++count] = &items[i - 1];

	  }//end if

	}//end for

	printf('%d\n', table[num_items][max_weight].value);

	printf('%d\n', total_weight);

  for (i = 0; i <= count; ++i){

    printf('%d %d %s \n',
           p_items[i]->weight,
           p_items[i]->value,
           p_items[i]->name);

  }//end for

}

/*
 *
 */
void print_table(int num_items, int max_weight){

  int w,i;

   for (i = 0; i <= num_items; ++i){
     for (w = 0; w <= max_weight; ++w){
       printf('%d ', table[i][w].value);
    }//end for
    printf('\n');
   }//end for
   printf('\n');

}

/*
 *
 */
void print_table_prev_xy(int num_items, int max_weight){

  int w,i;

   for (i = 0; i <= num_items; ++i){
     for (w = 0; w <= max_weight; ++w){
       printf('[%d,%d] ', table[i][w].prev_row, table[i][w].prev_column);
    }//end for
    printf('\n');
   }//end for
   printf('\n');

}

input.txt:

5
4
2 3 item_A
3 4 item_B
4 5 item_C
5 6 item_D

If you encounter any problems or errors, please let me know by providing an example of the code, input, output, and an explanation. Thanks.

Share
Leave a comment

Example of Quicksort using Hoarse Partition and Random Partition Algorithms

Example of Quicksort using Hoarse partition and random partition algorithms.

NOTIFICATION: These examples are provided for educational purposes. Using this code is under your own responsibility and risk. The code is given ‘as is’. I do not take responsibilities of how they are used.

quicksort.c:

/* Framework for the sorting programs.
 * Program: 04
 * Author: Alejandro G. Carlstein
 * Description: This program will implement quicksort 
 * (using the pseudocode from the book), applying 
 * the Hoare partition function, and randomization. 
 * This program should run with data where all the values 
 * are equal, and also when the data is in sorted 
 * (or reverse sorted) order. 
 */

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define MAX_SIZE 1000000

#define DBG_LV1 0
#define DBG_LV2 0

void Quicksort(int array[], int p, int r);
int Hoare_partition(int array[], int p, int r);
int Randomized_partition(int array[], int p, int r);
void Exchange(int *a, int *b);
int Get_random(int min, int max);

int data[MAX_SIZE];

int n;

int main(int argc, char* argv[]){

	int i;

	int n;

	int m = 0;

	int begin = 1;

	int ia_keys[MAX_SIZE];

	srand (time (NULL));

	/* Read in the data */
	n = 0;
    while (scanf('%d', &data[n]) == 1)
	    ++n;

	/* Print ou t the data */
	if (DBG_LV2)
		for (i = 0; i < n; ++i)
		    printf('[%d] %d\n', i, data[i]);

	Quicksort(data, 0, n);

	/* Print out the data */
	for (i = 0; i < n; ++i)
	    if (DBG_LV2){
	    	printf('[%d] %d\n', i, data[i]);
	    }else{
	    	printf('%d\n', data[i]);
	    }//end if

	if (DBG_LV2) 
		printf('+[10]: %d \n', data[10]);    

	return 0;
}

/*
 * Quicksort
 */
void Quicksort(int array[], int p, int r){

	if (DBG_LV1)
		printf('Quicksort(p: %d, r: %d)\n', p, r);

	int q;

	if (p < r){

		q = Randomized_partition(array, p, r);

		Quicksort(array, p, q);

		Quicksort(array, q + 1, r);		

	}// end if

}

/*
 * Hoare partition Book
 */
int Hoare_partition(int array[], int p, int r){

	if (DBG_LV1)printf('Hoare_partition_book(p: %d, r:%d)\n', p, r);

	int b_done = 1;

	// pivot value
	int x = array[p];

	int i = p - 1;

	int j = r + 1;

	if (DBG_LV2)
		printf('i: %d, j: %d\n', i, j);

	while (b_done){

		do{
			--j;
		}while (array[j] < x);

		do{
			++i;
		}while (array[i] > x);

		if (DBG_LV2)
			printf('+i: %d, j: %d\n', i, j);

		if (i < j){

			Exchange(&array[i], &array[j]);

		}else{

			b_done = 0;

		}//end if

	}// end while

	return j;
}

/*
 * Randomized partition
 */
int Randomized_partition(int array[], int p, int r){

	if (DBG_LV1)
		printf('Randomized_partition(p: %d, r: %d)\n', p, r);

	int i = Get_random(p, r);

	Exchange(&array[i], &array[r]);

	return Hoare_partition(array, p, r);

}

/*
 * Exchange swap the values holded by two variables
 */
void Exchange(int *a, int *b){

	if (DBG_LV1)
		printf('Exchange(value a: %d, value b: %d)\n', *a, *b);		

		int temp;

		temp = *a;
		*a = *b;
		*b = temp;
}

/*
 * get random number
 */
int Get_random(int min, int max){

	if (DBG_LV1)
		printf('Get_random(min: %d, max: %d)\n', min, max);		

	int rtn = 0;

	if (max > min){

		rtn = (rand() % (max - min)) + min;

	}else{

		fprintf(stderr, '[X] ERROR: minimum value cannot exceed maximun value\n');	

		exit(1);

	}//end if

	return rtn;
}

If you encounter any problems or errors, please let me know by providing an example of the code, input, output, and an explanation. Thanks.

Share
Leave a comment

Example of Heapsort Algorithm

Example of Heapsort algorithm.

NOTIFICATION: These examples are provided for educational purposes. Using this code is under your own responsibility and risk. The code is given ‘as is’. I do not take responsibilities of how they are used.

heapsort.c:

/* Framework for the sorting programs.
 * Program: 02
 * Author: Alejandro G. Carlstein
 * Description: This program will read a set of integers from standard 
 * input and sort them by implement a heap sort using the pseudocode 
 * from the book Introduction to Algorithms' by Thomas H. Cormen. 
 * Then print them out in sorted order (smallest to largest).
 */

#include <stdio.h>

#define MAX_SIZE 1000000
#define LEFT(i) ((i << 1) + 1)
#define RIGHT(i) ((i << 1) + 2)
#define DIV_BY_2(i) (i >> 1)

void Max_heapify(int array[], int i, int heap_size);
void Build_max_heap(int array[], int heap_size);
void Exchange(int *a, int *b);
void Heapsort(int array[], int length);

int data[MAX_SIZE];
int n;

int main(int argc, char* argv[]){

	int i;
	int heap_size;

	/* Read in the data */
	n = 0;
    while (scanf('%d', &data[n]) == 1)
	    ++n;

	/* Sort the numbers low to high */
	Heapsort(data, n);

	/* Print out the data */
	for (i = 0; i < n; ++i)
	    printf('%d\n', data[i]);

	return 0;
}

/*
 * Max_heapify helps to rebuild the heap region
 */
void Max_heapify(int array[], int i, int heap_size){

	int l, r, temp, largest;

	l = LEFT(i);

	r = RIGHT(i);	

	// Find Largest value
	largest = (l < heap_size && array[l] > array[i]) ? l : i;

	if (r < heap_size && array[r] > array[largest]) largest = r;

	if (largest != i){

		// Exchange 
		Exchange(&array[i], &array[largest]);

		// Rebuild heap region		
		Max_heapify(array, largest, heap_size);	

	}// end if	

}

/*
 * Build_max_heap helps to build the initial heap
 */
void Build_max_heap(int array[], int heap_size){

	int i = DIV_BY_2(heap_size);

	for (; i > -1; i--){

		Max_heapify(array, i, heap_size);

	}//end for

}

/*
 * Exchange swap the values holded by two variables
 */
void Exchange(int *a, int *b){

		int temp;

		temp = *a;
		*a = *b;
		*b = temp;
}

/*
 * Heapsort sort an array from the smallest element to the largest
 */
void Heapsort(int array[], int length){

	int i;
	int	heap_size = length ;

	Build_max_heap(data, length);

	for (i = (length - 1) ; i > 0; --i){

		// Exchange the largest item in the heap region
		// to the beginning of the sorted region
		Exchange(&data[0], &data[i]);

		// Reduce the heap region, increase the sorted region
		heap_size--;

		// Rebuild the heap region
		Max_heapify(data, 0, heap_size);

	}//end for

}

If you encounter any problems or errors, please let me know by providing an example of the code, input, output, and an explanation. Thanks.

Share
One Comment