#Visualising 3 sorting algorithms (bubble, insertion, shell) for NXT brick
#Author: Alex Voron
#Details: nnxt.blogspot.com/2012/10/nxt.html

#define WAIT_TIME 20
#define MAX_NUMBERS 50
#define NUM_OFFSET 60

int tArray[MAX_NUMBERS];

// Keep track of our sorting times.
float sortingTimes[3] = {0.0, 0.0, 0.0};

long timer;

// Draw the lines on the screen after each iteration.
void drawLines(int arr[], string functionName)
{
  ClearScreen();
  TextOut(0, LCD_LINE1, functionName);
  NumOut(NUM_OFFSET, LCD_LINE1, (CurrentTick() - timer) / 1000.0)

  for (int i = 0; i < MAX_NUMBERS; i++)
  {
    LineOut(i*2, 0, i*2, arr[i]);
  }
  Wait(WAIT_TIME);
}

// Randomise our array by first filling it up
void randomiseArray(int& arr[])
{
  int temp;
  int randomPos;

  string functionName = "Random";

  timer = CurrentTick();

  for (int i = 0; i < MAX_NUMBERS; i++)
  {
    arr[i] = i;
  }

  // now randomly mix it up, 2 times.
  for (int i = 0; i < 2; i++)
  {
	  for (int j = 0; j < MAX_NUMBERS; j++)
	  {
	    randomPos = Random(MAX_NUMBERS - 1);
	    temp = arr[j];
	    arr[j] = arr[randomPos];
	    arr[randomPos] = temp;
			drawLines(arr, functionName);
	  }
  }
}

// Do a bubble sort on the numbers, returns the number of seconds taken
float bubbleSort(int arr[])
{
  int temp;
  int i, j;

  string functionName = "Bubble";

  timer = CurrentTick();

  for(i = 0; i < MAX_NUMBERS; i++)
	{
	  for(j = 0; j < (MAX_NUMBERS - 1); j++)
	  {
	    if (arr[j] > arr[j+1])
	    {
				temp = arr[j];
				arr[j] = arr[j+1];
				arr[j+1] = temp;
				drawLines(arr, functionName);
			}
		}
	}
	
	return (CurrentTick() - timer) / 1000.0;
}

// Do an insertion sort on the numbers, returns the number of seconds taken
float insertionSort(int arr[])
{
  int temp;
  int i, j, k;

  timer = CurrentTick();

  string functionName = "Insertion";

  for (i = 1 ; i < MAX_NUMBERS ; i++ )
	{
		for (j = 0 ; j < i ; j++ )
		{
			if ( arr[j] > arr[i] )
			{
				temp = arr[j] ;
				arr[j] = arr[i] ;

				for (k = i ; k > j ; k-- )
				{
					arr[k] = arr[k - 1] ;
					drawLines(arr, functionName);
				}
				arr[k + 1] = temp ;
				drawLines(arr, functionName);
			}
		}
	}
	return (CurrentTick() - timer) / 1000.0;
}

// Do a shell sort on the numbers, returns the number of seconds taken
float shellSort(int arr[])
{
	int j, i, m, mid;
  timer = CurrentTick();
	string functionName = "Shell";

	for(m = MAX_NUMBERS/2 ; m > 0; m /= 2)
	{
		for(j = m; j < MAX_NUMBERS; j++)
		{
			for(i = j - m; i >= 0; i -= m)
			{
				if(arr[i + m] >= arr[i])
					break;
				else
				{
					mid = arr[i];
					arr[i] = arr[i + m];
					arr[i + m] = mid;
					drawLines(arr, functionName);
				}
			}
		}
	}
	return (CurrentTick() - timer) / 1000.0;
}

// The main task
task main ()
{
  int arr[MAX_NUMBERS];
  int copy[MAX_NUMBERS];
  ArrayInit(arr, 0, MAX_NUMBERS);

  ClearScreen();

  // Populate the array with random data
  randomiseArray(arr);

  Wait(1000);
  // Iterate through each sorting algorithm
  for (int i = 0; i < 3; i++)
  {
    // Make a copy of the original and sort that.
    memcpy(copy, arr, sizeof(int) * MAX_NUMBERS);
    ClearScreen();
    switch(i)
    {
      case 0: sortingTimes[0] = bubbleSort(copy); break;
      case 1: sortingTimes[1] = shellSort(copy); break;
      case 2: sortingTimes[2] = insertionSort(copy); break;
    }
    Wait(1000);
  }

  // Show the results.
	ClearScreen();

  TextOut(10, LCD_LINE1, "Sorting times:");
  TextOut(0, LCD_LINE2, "Bubble:");
  NumOut(NUM_OFFSET, LCD_LINE2, sortingTimes[0]);
  TextOut(0, LCD_LINE3, "Shell:");
  NumOut(NUM_OFFSET, LCD_LINE3, sortingTimes[1]);
  TextOut(0, LCD_LINE4, "Insertion:");
  NumOut(NUM_OFFSET, LCD_LINE4, sortingTimes[2]);
  TextOut(0, LCD_LINE5, "[Enter] to exit");

  while (!ButtonPressed(BTNCENTER, true));
}