c prog quick sort

/*
 * gcc.c4.2.1-p4a.x86_64 -g3 quick_sort.c  -o quick_sort
 *
 * Quick sort is devide and conquer algorithm. It first divides a large array into smaller sub-arrays: The low elements and the high
 * elements. Quick sort can then recursively sort the sub-arrays.
 *
 * 1. Pick element, called pivot, from the array.
 * 2. Partitioning: reorder the array so that all elements with the values less than the pivot come before the pivot,
 *    while all elements with values greater than the pivot come after it . After partitioning, the pivot is in its final poisiton.
 * 3. recursively apply the above steps to the sub sub-array of elements. whtih smaller values.
 *
 *  algorithm quicksort(A, lo, hi) is
 *      if lo < hi then
 *          p := partition(A, lo, hi)
 *          quicksort(A, lo, p – 1)
 *          quicksort(A, p + 1, hi)
 *  algorithm partition(A, lo, hi) is
 *      pivot := A[hi]
 *      i := lo        // place for swapping
 *      for j := lo to hi – 1 do
 *          if A[j] ≤ pivot then
 *              swap A[i] with A[j]
 *              i := i + 1
 *      swap A[i] with A[hi]
 *      return i
 */
#include
#include "sort_common.h"

#define DATASIZE 25
int data1[25] = {25,22,23,21,19,24,18,20,17,14,16,13,15,12,10,11,9,7,8,6,4,5,3,1,2};

/*
 * Loumuto partition scheme
 * Algorithm maintains the index to put the pivot in variable i and each time it finds an element
 * less than or equal to pivot, this index is incremented and that element would be placed before
 * the pivot. This schem is more compact and easy to understand, it is frequently used.
 */
int lomuto_partition(int *array, int lo, int hi)
{
    int pivot = 0;
    int i = 0, j = 0;
    pivot = array[hi];
   int i = 0, j = 0;                                                                                                                                                                                                                                                       [63/24342]
    pivot = array[hi];
    i = lo;
    for( j = lo; j <= hi-1; j++) {
        if(array[j] <= pivot) {
            swap(&array[j], &array[i]);
            printf("Inside swap array[%d]=%d array[%d]=%d\n", j, array[j], i, array[i]);
            i= i + 1;
        }
    }
    swap(&array[i], &array[hi]);
    printf("Outside swap array[%d]=%d array[%d]=%d\n", j, array[j], i, array[i]);
    return i;
}


void quick_sort(int *array, int lo, int hi)
{
    int pi = 0;
    if(lo < hi) {
        pi = lomuto_partition(array, lo, hi);
        printf("pi=%d\n", pi);
        quick_sort(array, lo, pi - 1);
        quick_sort(array, pi + 1, hi);
    }
}
/*
 * Hoare partition scheme:
 *  Two indices that start at the ends of the array being partitioned,
 *  then move toward each other, until they detect an inversion: pair of
 *  elements, one greater than the pivot, one smaller, that are in the wrong order
 *  relative to each other. The inverted elements are then swapped. When indices
 *  meet algorithm stops and returns ihe final index.
 *  algorithm quicksort(A, lo, hi) is
 *
 *  if lo < hi then
 *      p := partition(A, lo, hi)
 *      quicksort(A, lo, p)
 *      quicksort(A, p + 1, hi)
 *  algorithm partition(A, lo, hi) is
 *      pivot := A[lo]
 *      i := lo – 1
 *      j := hi + 1
 *      loop forever
 *          do
 *              i := i + 1
 *          while A[i] < pivot
 *
 *          do
 *              j := j – 1
 *          while A[j] > pivot
 *
 *          if i >= j then
 *              return j
 *
 *          swap A[i] with A[j]
 *
 */

int hoare_partition(int *array, int lo, int hi)
{
    int pivot = 0;
    int i=0,j=0;
    j = hi + 1;
    i = lo - 1;
  j = hi + 1;                                                                                                                                                                                                                                                              [0/24342]
    i = lo - 1;
    pivot = array[lo];
    while(1) {
        do{
            i = i + 1;
            //printf("i inc i=%d j=%d array[i]=%d pivot= %d \n", i, j, array[i], pivot);
        } while (array[i] < pivot);
        do{
            j = j - 1;
            //printf("i inc i=%d j=%d array[j]=%d pivot= %d \n", i, j, array[j], pivot);
        } while (array[j] > pivot);

        if( i >= j) {
            printf("return i=%d j=%d\n", i, j);
            return j;
        }
        swap(&array[i], &array[j]);
        //printf("outside swap array[%d]=%d array[%d]=%d\n", j, array[j], i, array[i]);
    }
}
void quick_sort1(int *array, int lo, int hi)
{
    int pi = 0;
        printf("outside pi=%d lo=%d hi=%d \n", pi, lo, hi);
    if(lo < hi) {
        pi = hoare_partition(array, lo, hi);
        printf("inside pi=%d lo=%d hi=%d \n", pi, lo, hi);
        show_data_flat(sizeof(data1)/(sizeof(int)), array);
        quick_sort1(array, lo, pi);
        quick_sort1(array, pi + 1, hi);
    }
}

int main(void)
{
    show_data(sizeof(data1)/(sizeof(int)), data1);
    //quick_sort(data1, 0, sizeof(data1)/(sizeof(int)) - 1);
    quick_sort1(data1, 0, sizeof(data1)/(sizeof(int)) - 1);
    show_data(sizeof(data1)/(sizeof(int)), data1);
}