#include <iostream>
#include <vector>
#include <list>

/**
 * Profanity is the one language all programmers know best. -- Unknown
 */

using namespace std;

void swap(int& a, int& b)
{
  int t = a;
  a = b;
  b = t;
}

void gnomeSort(vector<int>& nums)
{
  int ind = 0;
  int s = nums.size();

  // Go until we have sorted everything
  // If we just increased ind, then everything
  // at a lesser index is sorted.
  // If we just decreased it, then we have to
  // walk the new value down to where it goes
  // in our sorted list.
  while (ind < s)
    {
      // If we aren't at the beginning, and these are
      // unsorted, swap 'em
      if (ind != 0 and nums[ind] < nums[ind - 1])
	{
	  swap(nums[ind], nums[ind - 1]);
	  // And move back to see if we need to swap further
	  ind --;
	}
      else
	{
	  // Otherwise, move forward
	  ind++;
	}
    }
}

void bubbleSort(vector<int>& nums)
{
  for (unsigned int i = 0; i < nums.size(); i++)
    {
      bool didSomething = false;
      for (unsigned int j = 0; j < nums.size() - i - 1; j++)
	{
	  if (nums[j] > nums[j + 1])
	    {
	      swap(nums[j], nums[j + 1]);
	      didSomething = true;
	    }
	}
      if (not didSomething) break;
    }
}

void merge(vector<int>& nums, int start, int end)
{
  vector<int> temp;
  int low = 0;
  int high = (end - start) - 1;
  int count = 0;
  temp.resize(end - start);
  for (int i = 0; i < end - start; i++)
    {
      if (i < (end - start) / 2)
	{
	  temp[i] = nums[start + i];
	}
      else
	{
	  temp[i] = nums[end - (i - (end - start) / 2) - 1];
	}
    }

  while (low <= high)
    {
      if (temp[low] <= temp[high])
	{
	  nums[start + count] = temp[low];
	  low ++;
	  count ++;
	} 
      else
	{
	  nums[start + count] = temp[high];
	  high --;
	  count ++;
	}
    }
}

void mergeSort(vector<int>& nums, int start, int end)
{
  // If we are only sorting 1 element, we are done
  if (end - start <= 1) return;

  // The median of these two, the midpoint of the list
  int med =  (start + end) / 2;

  mergeSort(nums, start, med);
  mergeSort(nums, med, end);
  merge(nums, start, end);
}

void mergeSort(vector<int>& nums)
{
  mergeSort(nums, 0, nums.size());
}

void insertionSort(vector<int>& nums)
{
  // We need to "pick up" all n cards
  for (unsigned int i = 0; i < nums.size(); i++)
    {
      // Get the next card, that's nums[i]
      // Find where it needs to go
      int index = 0;

      for (; index < i; index++)
	{
	  if (nums[index] > nums[i])
	    break;
	}
      int temp = nums[i];
      for (unsigned int j = i; j > index; j--)
	{
	  nums[j] = nums[j - 1];
	}
      nums[index] = temp;
      
    }
}

void shellSort(vector<int>& nums)
{
  int i, j, increment, temp;
  increment = 7;
  
  while (increment > 0)
    {
      for (i = 0; i < nums.size(); i++)
	{
	  j = i;
	  temp = nums[i];
	  while ((j >= increment) and (nums[j - increment] > temp))
	    {
	      nums[j] = nums[j - increment];
	      j = j - increment;
	    }
	  nums[j] = temp;
	}
      if (increment/2 != 0)
	increment /= 2;
      else if (increment == 1)
	increment = 0;
      else
	increment = 1;
    }
}

void quickSort(vector<int>& nums, int begin, int end)
{
  if (end - begin <= 1) return;

  // We are going to "pivot" around this value
  int pivot = nums[begin];

  // We would like to break our list into 3 sections: 
  // the pivot (currently @ begin), 
  // S1 (everything < pivot, which is currently from begin+1 .. lastS1
  // S2 (everything >= pivot, everything from lastS1+1 .. firstUnknown
  // Everything from firstUnknown to end needs to be classified still
  int lastS1 = begin;
  for (int firstUnknown = begin + 1; firstUnknown < end; firstUnknown++)
    {
      // If this value is < pivot, then we move it into S1
      if (nums[firstUnknown] < pivot)
	{
	  lastS1++;
	  swap(nums[firstUnknown], nums[lastS1]);
	}      
      // The value was >= pivot, so it is already in the right spot
      // if we just update firstUnknown.
    }

  // Now put the pivot in the middle
  swap(nums[begin], nums[lastS1]);

  // LastS1 is the index of the pivot now.
  quickSort(nums, begin, lastS1);
  quickSort(nums, lastS1 + 1, end);
}

void quickSort(vector<int>& nums)
{
  quickSort(nums, 0, nums.size());
}

const int tens[] = {0, 10, 100, 1000, 10000};

// Return the d'th digit of n where d=1 is the 1s digit, d=2 is the 10s digit 
int radix(int n, int d)
{
  return (n / tens[d]) % 10;
}

void radixSort(vector<int>& nums)
{
  vector<list<int> > current;
  vector<list<int> > next;

  int maxDigits = 0;
  current.resize(10);
  next.resize(10);

  for (unsigned int i = 0; i < nums.size(); i++)
    {
      int temp = nums[i];
      current[radix(temp, 1)].push_back(temp);
      maxDigits = max(maxDigits, (int)(log10((double)temp)));
    }

  for (int digit = 2; digit <= maxDigits; digit++)
    {
      for (int i = 0; i < 10; i++)
	{
	  for (list<int>::iterator j = current[i].begin();
	       j != current[i].end(); ++j)
	    {
	      next[radix(*j, digit)].push_back(*j);
	    }
	}
      current = next;
      next.resize(0);
      next.resize(10);
    }
  
  int ind = 0;
  for (int i = 0; i < 10; i++)
    {
      for (list<int>::iterator j = current[i].begin();
	   j != current[i].end(); 
	   ++j)
	{
	  nums[ind] = *j;
	  ind++;
	}
    }
}

void histogramSort(vector<int>& nums)
{
  int minV = nums[0];
  int maxV = nums[0];

  // Find the minimum and the maximum values
  for (unsigned int i = 1; i < nums.size(); i++)
    {
      minV = min(minV, nums[i]);
      maxV = max(maxV, nums[i]);
    }
  
  // Now allocate a vector with 1 bucket for every value between max and
  // min.
  vector<int> counts;
  counts.resize(maxV - minV);
  
  // Now count up how many times each value in nums occurs.  
  for (unsigned int i = 0; i < nums.size(); i++)
    counts[nums[i] - minV] ++;

  // And finally, put the numbers back in sorted order, according to
  // their counts
  int ind = 0;

  // Loop through our histogram
  for (unsigned int i = 0; i < counts.size(); i++)
    {
      // For any value that occurs, lets output it that many times
      for (unsigned int j = 0; j < counts[i]; j++)
	{
	  // This is + minV because we originally subtracted that off
	  // to (hopefully) save space
	  nums[ind] = i + minV;
	  ind++;
	}
    }
}

int main(int argc, char** argv)
{
  vector<int> nums;
  string error = "sortDemo n {gnome|insertion|bubble|merge|shell|quick|radix|hist}";
  if (argc < 3)
    {
      cout << error << endl;
      return 0;
    }

  srand(time(0));

  int numToGen = atoi(argv[1]);
  for (int i = 0; i < numToGen; i++)
    {
      nums.push_back(rand() % 9000 + 1000);
    }

  if (strcmp(argv[2], "gnome") == 0)
    gnomeSort(nums);
  else if (strcmp(argv[2], "insertion") == 0)
    insertionSort(nums);
  else if (strcmp(argv[2], "bubble") == 0)
    bubbleSort(nums);
  else if (strcmp(argv[2], "merge") == 0)
    mergeSort(nums);
  else if (strcmp(argv[2], "shell") == 0)
    shellSort(nums);
  else if (strcmp(argv[2], "quick") == 0)
    quickSort(nums);
  else if (strcmp(argv[2], "radix") == 0)
    radixSort(nums);
  else if (strcmp(argv[2], "hist") == 0)
    histogramSort(nums);
  else
    {
      cout << error << endl;
      return 0;
    }

  return 0;
  
  for (int i = 0; i < numToGen; i++)
    {
      cout << nums[i] << " ";
      if (i % 15 == 14) cout << endl;
    }
  cout << endl;
}