#include <iostream>


void printArray(int array[], int size);
void bubble_sort(int array[], int arraySize);
void bucket_sort(int array[], int size) ;
void merge(int a[], int low, int mid, int high);
void merge_sort(int array[], int low, int high);
void quick_sort(int array[], int low, int high);

int main() 
{
   const int arraySize = 10;
   int a[arraySize] = {2, 6, 4, 8, 10, 12, 89, 68, 45, 37};
   int b[arraySize], c[arraySize], d[arraySize];
   std::copy(a, a + arraySize, b);
   std::copy(a, a + arraySize, c);
   std::copy(a, a + arraySize, d);


   // -------- print the original array ----------
   std::cout << "Original array:";
   printArray(a, arraySize);


   // -------- perform bubble sort and print array -----
   bubble_sort(a, arraySize);
   std::cout << "Sorted array (Bubble sort):";
   printArray(a, arraySize);


   // -------- perform bucket sort and print array -----
   bubble_sort(b, arraySize);
   std::cout << "Sorted array (Bucket sort):";
   printArray(b, arraySize);


   // -------- perform merge sort and print array -----
   merge_sort(c, 0, arraySize-1);
   std::cout << "Sorted array (Merge sort): ";
   printArray(c, arraySize);


   // -------- perform quick sort and print array -----
   quick_sort( d, 0, arraySize-1);
   std::cout << "Sorted array (Quick sort): ";
   printArray(d, arraySize);

}




void printArray(int array[], int size) 
{
   for( int i=0; i< size; i++)  std::cout << "   " << array[i];
   std::cout << std::endl;
}



void bubble_sort(int array[], int size) 
{
   for(int i=0; i < size-1; i++) {
      for(int j=0; j < size-1; j++) {
         if(array[j] > array[j+1]) std::swap( array[j], array[j+1] ); 
      }
   }
}


void merge(int a[], int low, int mid, int high)
{
   int h = low, i = low, j = mid+1, b[high+1];

   while( (h <= mid) && (j <= high) ) {
      if( a[h] <= a[j] )  { b[i] = a[h]; h++; }
      else { b[i] = a[j]; j++; }
      i++;
   }

   int start = h, end = mid;
   if(h > mid) { start = j; end = high; }
   for(int k=start; k <= end; k++) {
      b[i] = a[k];
      i++;
   }
 
   for(int k=low; k <= high; k++) a[k] = b[k];
}



void merge_sort(int array[], int low, int high)
{
   int mid;

   if(low < high) {
      mid = (low + high) / 2;
      merge_sort(array, low, mid);
      merge_sort(array, mid+1, high);
      merge(array, low, mid, high);
   }
}





void quick_sort(int array[], int low, int high) 
{
   if( abs(high - low) < 2) return; //only sort if there is more than 1 element
 
   // Initially find a random pivot
   int pivotIndex = rand() % high;
   int pivot = array[pivotIndex];
 

   // Pointer to begining of array and one to the end
   int* begin = &array[0];
   int* end = &array[high];

   // While begin < end 
   while( begin < end ) {

      // Find the lowest bound number to swap
      while( *begin < pivot ) begin++;
      // Find the highest bound number to swap
      while( *end > pivot ) end--;

      // Do the swap
      std::swap(*begin, *end);
   }

   quick_sort(array, 0, pivotIndex - 1);   //sort elements to the left of pivot
   quick_sort(array, pivotIndex + 1, high); //sort elements to the right of pivot
}





void bucket_sort(int array[], int size) 
{
   // use bucket[x][size] to hold the current count
   int bucket[10][size+1];

   // init bucket counters
   for(int x = 0; x < 10; x++) bucket[x][size] = 0;

   // main loop for each digit position
   for(int digit = 1; digit <= 1000000000; digit *= 10) {

      // array to bucket
      for(int i = 0; i < size; i++) {
         // get the digit 0-9
         int dig = (array[i] / digit) % 10;
         // add to bucket and increment count
         bucket[dig][bucket[dig][size]++] = array[i];
      }

      // bucket to array
      int idx = 0;
      for(int x = 0; x < 10; x++) {
         for(int y = 0; y < bucket[x][size]; y++) {
            array[idx++] = bucket[x][y];
         }
         // reset the internal bucket counters
         bucket[x][size] = 0;
      }

   } // end of main loop

}