langc_algo_quicksort.c

/*
    Quick sort example 3 
*/

#include <stdio.h>

//SETTING QUICK SORT, PIVOT POSITION 

#define PIVOT_LEFT
//#define PIVOT_RIGHT

#define PIVOT_LEFT_SWAP
//#define PIVOT_RIGHT_SWAP

#define SORT_ORDERING_ASCEND   //   , DESCENDING 4,3,2,1 


int partition(int data[], int left, int right)
{
	
#if defined(PIVOT_LEFT)
	
	int pivot = data[left]; 
	int start = left+1;
	int end   = right;

#elif defined(PIVOT_RIGHT)

	int pivot = data[right]; 
	int start = left;
	int end   = right-1;

#endif

	int tmp;

	
	while(start <= end) //first to right-1 
	{

#if defined(SORT_ORDERING_ASCEND)	// ASCENDING ,1,2,3,4	
		while(data[start] <= pivot && start <= end) start++;
		while(data[end]   >  pivot && start <= end) end--;

#else   // DESCENDING 4,3,2,1 
		while(data[start] > pivot && start < end) start++;
		while(data[end] <= pivot && start <= end) end--;	 
#endif
	
		if(start < end ){
			tmp         = data[start]; 
			data[start] = data[end];
			data[end]   = tmp;
		}else
			break;
		
	}

#if defined(PIVOT_LEFT_SWAP) // last swap 
	
	tmp = data[left];
	data[left] = data[end];
	data[end] = tmp;	
	
	return end;
	
#elif defined(PIVOT_RIGHT_SWAP)	
	
	tmp = data[start];
	data[start] = data[right];
	data[right] = tmp;	
	
	return start;
	
#endif

}
/*
int partition2(int arr[], int left, int right)
{
	int first=left;
	int pivot=arr[first];
	int tmp;
	
	left++; // next. 
	
	while(left <= right)
	{
		
//ASCENDING ,1,2,3,4		
	   while(arr[left] <= pivot && left < right) left++;
	   while(arr[right] > pivot && left <= right) right--;

//DESCENDING 4,3,2,1 	   
//   while(arr[left] > pivot && left < right) left++;
//   while(arr[right] <= pivot && left <= right) right--;	   
	   
	   if(left < right){ // can't find value
          
          tmp = arr[left];
          arr[left] = arr[right];
          arr[right] = tmp;
	   	
	   }else
	      break;
	   
	}
	
	tmp = arr[first];
	arr[first] = arr[right];
	arr[right] = tmp;
	
  return right; //index;	
}
*/


int quicksort(int data[], int left, int right)
{
	int index=0;
	
    if (left < right)
    {	
		index = partition(data,left,right);
		quicksort(data,left,index-1);
		quicksort(data,index+1,right);
    }
		
}

void sort_print(int arr[], int Lens)
{
  int i=0;

    for (i = 0; i < Lens; i++)
        printf("%d ", arr[i]);
    printf("\n");
}


// Second Quick sort 
void quickSort2(int arr[], int left, int right) {
      int i = left, j = right;
      int tmp;
      int pivot = arr[(left + right) / 2];

       /* partition */
      while (i <= j) {
            while (arr[i] < pivot)
                  i++;
            while (arr[j] > pivot)
                  j--;

            if (i <= j) {
                  tmp = arr[i];
                  arr[i] = arr[j];
                  arr[j] = tmp;
                  i++;
                  j--;
            }
      };

      /* recursion */
      if (left < j)
            quickSort2(arr, left, j);

      if (i < right)
            quickSort2(arr, i, right);
}


int main(void) {
	// your code goes here
 	int arr1[] = {5, 2, 1, 8, 3, 6, 4, 7 , 9 , 12, 11, 10 };
 	int arr2[] = {5, 2, 1, 8, 3, 6, 4, 7 , 9 , 12, 11, 10 };
 	
 	int Lens1 = sizeof(arr1) / sizeof(int);
 	int Lens2 = sizeof(arr2) / sizeof(int); 	
 	
       
 	printf("Quick Lenght=%d\n",Lens1);
    
    printf("------1st TEST \n");
 	sort_print(arr1, Lens1);
	quicksort(arr1, 0, Lens1 - 1);   
	sort_print(arr1, Lens1);

    printf("------2nd TEST \n"); 	
 	
	sort_print(arr2, Lens2);
	quickSort2(arr2, 0, Lens2 - 1);   
	sort_print(arr2, Lens2);
	
	return 0;
}