#version 3.8;
global_settings {
	assumed_gamma 1.0
}


#include "strings.inc"

//signed random number, range [-1, 1]
#macro SRand(RS) (rand(RS)*2 - 1) #end

//random number in specified range [Min, Max]
#macro RRand(Min, Max, RS) (rand(RS)*(Max-Min) + Min) #end

#declare Sec = 24*60*60;
#declare ms = 1000*Sec;

//------------------------------------------------------------------------------

#macro TimeUnits (Elapsed)
	#local NewTime = Elapsed;
	#local Units = " ms"
	#if (Elapsed > 1000) 
	#local NewTime = Elapsed/1000;
		#local Units = " sec";
	#end
	#if (Elapsed > 60000) 
	#local NewTime = Elapsed/60000;
		#local Units = " min";
	#end
	
	#local Result = concat (str (NewTime, 0, 2), Units);
	
	Result
	
#end

//------------------------------------------------------------------------------

#macro TimeElapsed (Macro)
	#local Start = now*ms;
	Parse_String (Macro)
	#local End = now*ms;
	#local Elapsed = End-Start;
	
	Elapsed
	
#end

//------------------------------------------------------------------------------

#macro MakeRandomArray (TotalElements, MinValue, MaxValue)
	#local Seed = seed (19375);
	#local Array = array [TotalElements];
	#for (i, 0, TotalElements-1)
		#local Array [i] = RRand (MinValue, MaxValue, Seed);
	#end
	
	Array
	
#end

//------------------------------------------------------------------------------

#macro PrintArray (Name, Array, Dec)
	#debug concat (Name, " \n")
	#local Elements = dimension_size (Array, 1)-1;
	#local Leading = floor(log(Elements))+1;
	#for (i, 0, Elements-1)
		#debug concat (str(Array[i], Leading, Dec), ", ")
	#end
	#debug concat (str(Array[Elements], Leading, Dec))
	#debug "\n"
#end

//------------------------------------------------------------------------------

#macro Newlines (N)
	#for (NL, 0, N)
		#debug "\n"
	#end
#end

//------------------------------------------------------------------------------

#macro BubbleSort (Array)
	#local Elements = dimension_size (Array, 1)-1;
	#local SortedArray = Array;
	#for (i, 0, Elements)
		#for (j, i+1, Elements)
			#if (SortedArray[j] < SortedArray[i])
				#local temp = SortedArray[i];
				#local SortedArray[i] = SortedArray[j];
				#local SortedArray[j] = temp;
			#end // end if
		#end // end for j
	#end // end for i
	
	SortedArray
	
#end // end macro BubbleSort

//------------------------------------------------------------------------------

#macro FindSmallest (Array, i)	// Utility macro for Selection Sort
	#local Elements = dimension_size (Array, 1)-1;
	#local ele_small = Array[i];
	#local position = i;
	#for (j, i+1, Elements)
		#if (Array[j] < ele_small)
			#local ele_small = Array[j];
			#local position = j;
		#end // end if
	#end // end for
	
	position

#end // end macro FindSmallest

#macro SelectionSort (Array)
	#local Elements = dimension_size (Array, 1)-1;
	#local SortedArray = Array;
	#for (i, 0, Elements)
		#local pos = FindSmallest (SortedArray,i);
		#local temp = SortedArray[i];
		#local SortedArray[i] = SortedArray[pos];
		#local SortedArray[pos] = temp;
	#end // end for
	
	SortedArray
	
#end

//------------------------------------------------------------------------------

#macro InsertionSort (Array)
	#local Elements = dimension_size (Array, 1)-1;
	#local SortedArray = Array;
	#for (k, 1, Elements)
		#local temp = SortedArray[k];
		#local j = k-1;
		#while(j >=0 & temp <= SortedArray[j])
			#local SortedArray[j+1] = SortedArray[j];
			#local j = j-1;
			#if (j < 0) #break #end
		#end // end while
		
		#local SortedArray[j+1] = temp;
	#end // end for k
	
	SortedArray
	
#end


//------------------------------------------------------------------------------

#macro Swap (A, B)	// Utility macro for Quick Sort
	#local T = A;
	#local A = B;
   	#local B = T;
#end


#macro Partition (Array, Low, High)
	#local pivot = Array[High];
	#local i = (Low - 1);
	#for (j, Low, High-1)
		//if current element is smaller than pivot, increment the low element
		//swap elements at i and j
		#if (Array[j] <= pivot)
			#local i = i + 1; // increment index of smaller element
			Swap (Array[i], Array[j])
		#end // end if
	#end // end for
	Swap (Array[i + 1], Array[High])
	
	(i + 1)
	
#end // end macro Partition


#macro QuickSort (Array, optional Low, optional High)
	#local Elements = dimension_size (Array, 1)-1;
	#ifndef (Low)
		#local Low = 0;
	#end
	#ifndef (High)
		#local High = Elements;
	#end
	#if (Low < High)
		#local pivot = Partition (Array, Low, High);
		//sort the sub arrays independently
   		QuickSort (Array, Low, pivot - 1)
   		QuickSort (Array, pivot + 1, High)
	#end

	//SortedArray
	
#end

//------------------------------------------------------------------------------


/*
//------------------------------------------------------------------------------
#macro Merge (Array, Low, High, Mid)

	#local c = array;
	#local i = Low;
	#local k = Low;
	#local j = Mid + 1;
	#while (i <= Mid & j <= High)
		#if (Array[i] < Array[j])
			#local c[k] = Array[i];
			#local k = k + 1;
			#local i = i + 1;
		#else {
			#local c[k] = Array[j];
			#local k = k + 1;
			#local j = j + 1
		#end;
	#end
	
	#while (i <= Mid)
		#local c[k] = Array[i];
		#local k = k + 1;
		#local i = i + 1;
	#end
	
	#while (j <= High)
		#local c[k] = Array[j];
		#local k = k + 1;
		#local j = j + 1;
	#end
	
	#for (i, Low; k)
		#local Array[i] = c[i];
	#end
#end // end macro


#macro MergeSort (Array, optional Low, optional High)
	#local Elements = dimension_size (Array, 1)-1;
	#ifndef (Low)
		#local Low = 0;
	#end
	#ifndef (High)
		#local High = Elements;
	#end
	#if (Low < High)
		// divide the array at mid and sort independently using merge sort
		#local Mid = (Low + High)/2;
		MergeSort (Array, Low, Mid);
		MergeSort (Array, Mid+1, High);
		//merge or conquer sorted arrays
		Merge (Array, Low, High, Mid);
	#end
#end
 // TOO MANY NESTED SYMBOL TABLES
//------------------------------------------------------------------------------
*/


#macro ShellSort (Array)
	#local Elements = dimension_size (Array, 1)-1;
	#local SortedArray = Array;
	
	#local gap = Elements/2;
	#while (gap > 0)
		 #for (i, gap, Elements)
			//sort sub lists created by applying gap
			#local temp = SortedArray[i];
			#local j = i;
			//#for (j = i; j >= gap && arr[j - gap] > temp; j -= gap)
			#while (j >= gap & SortedArray[j - gap] > temp)
				#local SortedArray[j] = SortedArray[j - gap];
				#local j = j - gap;
				#if (j-gap < 0) #break #end
			#end
			#local SortedArray[j] = temp;
      	#end // end for
		#local gap = floor (gap/2);
	#end // end while
	
	SortedArray

#end

//------------------------------------------------------------------------------

// function to heapify the tree
#macro Heapify (Array, N, root)
	#local largest = root; // root is the largest element
	#local l = 2*root + 1; // left = 2*root + 1
	#local r = 2*root + 2; // right = 2*root + 2
	// If left child is larger than root
	#if (l < N)
		#if (Array[l] > Array[largest])
			#local largest = l;
		#end
	#end
  
	// If right child is larger than largest so far
	#if (r < N)
		#if (Array[r] > Array[largest])
			#local largest = r;
		#end
	#end
  
	// If largest is not root
	#if (largest != root)
		//swap root and largest
		Swap (Array[root], Array[largest])
		// Recursively heapify the sub-tree
		Heapify (Array, N, largest)
	#end // end if
#end // end macro
 
 
 
#macro HeapSort (Array)
	#local Elements = dimension_size (Array, 1)-1;
	#local SortedArray = Array;
	// build heap
	#for (i, floor(Elements/2) - 1, 0, -1)
		Heapify (SortedArray, Elements, i)
	#end // end for
		// extracting elements from heap one by one
	#for (i, Elements, 0, -1)
 		// Move current root to end
		Swap (SortedArray[0], SortedArray[i])
		// again call max heapify on the reduced heap
		Heapify (SortedArray, i, 0)
	#end // end for
	
	SortedArray
	
#end // end macro


//------------------------------------------------------------------------------

// Iterative HeapSort

// CountingSort

// RadixSort

// BucketSort



// Execute all sorting macros and compared the time for completion

#declare Items = 1000;


#declare UnsortedArray = MakeRandomArray (Items, 0, 100);
//PrintArray ("Unsorted Array", UnsortedArray, 3)
//Newlines (2)

#declare Speed = TimeElapsed ("#declare BubbleSorted = BubbleSort (UnsortedArray)");
//PrintArray ("Bubble Sorted Array", BubbleSorted, 3)
#debug concat("\n   Bubble sorting ", str (Items, 0, 0), " items took ", TimeUnits (Speed), " \n")

//Newlines (2)
#declare Speed = TimeElapsed ("#declare SelectionSorted = SelectionSort (UnsortedArray)");
//PrintArray ("Selection Sorted Array", SelectionSorted, 3)
#debug concat("\nSelection sorting ", str (Items, 0, 0), " items took ", TimeUnits (Speed), " \n")

//Newlines (2)
#declare Speed = TimeElapsed ("#declare InsertionSorted = InsertionSort (UnsortedArray)");
//PrintArray ("Insertion Sorted Array", InsertionSorted, 3)
#debug concat("\nInsertion sorting ", str (Items, 0, 0), " items took ", TimeUnits (Speed), " \n")

//Newlines (2)
#declare QuickSorted = UnsortedArray;
#declare Speed = TimeElapsed ("QuickSort (QuickSorted,,)");
//PrintArray ("Quick Sorted Array", QuickSorted, 3)
#debug concat("\n    Quick sorting ", str (Items, 0, 0), " items took ", TimeUnits (Speed), " \n")
/*
Newlines (2)
#declare MergeSorted = UnsortedArray;
#declare Speed = TimeElapsed ("MergeSort (MergeSorted,,)");
PrintArray ("Merge Sorted Array", MergeSorted, 3)
#debug concat("\nMerge sorting ", str (Items, 0, 0), " items took ", str (Speed, 0, 2), " ms. \n")
*/
//Newlines (2)
#declare ShellSorted = UnsortedArray;
#declare Speed = TimeElapsed ("#declare ShellSorted = ShellSort (ShellSorted)");
//PrintArray ("Shell Sorted Array", ShellSorted, 3)
#debug concat("\n    Shell sorting ", str (Items, 0, 0), " items took ", TimeUnits (Speed), " \n")

//Newlines (2)
#declare HeapSorted = UnsortedArray;
#declare Speed = TimeElapsed ("#declare HeapSorted = HeapSort (HeapSorted)");
//PrintArray ("Heap Sorted Array", HeapSorted, 3)
#debug concat("\n     Heap sorting ", str (Items, 0, 0), " items took ", TimeUnits (Speed), " \n")

Newlines (2)

#declare SortedArray = BubbleSorted;

#declare Speed = TimeElapsed ("#declare BubbleSorted = BubbleSort (SortedArray)");
#debug concat("\n   Bubble sorting ", str (Items, 0, 0), " items took ", TimeUnits (Speed), " \n")

#declare Speed = TimeElapsed ("#declare SelectionSorted = SelectionSort (SortedArray)");
#debug concat("\nSelection sorting ", str (Items, 0, 0), " items took ", TimeUnits (Speed), " \n")

#declare Speed = TimeElapsed ("#declare InsertionSorted = InsertionSort (SortedArray)");
#debug concat("\nInsertion sorting ", str (Items, 0, 0), " items took ", TimeUnits (Speed), " \n")
/*
#declare QuickSorted = SortedArray;
#declare Speed = TimeElapsed ("QuickSort (QuickSorted,,)");
#debug concat("\n    Quick sorting ", str (Items, 0, 0), " items took ", TimeUnits (Speed), " \n")
*/

#declare ShellSorted = SortedArray;
#declare Speed = TimeElapsed ("#declare ShellSorted = ShellSort (ShellSorted)");
#debug concat("\n    Shell sorting ", str (Items, 0, 0), " items took ", TimeUnits (Speed), " \n")

#declare HeapSorted = SortedArray;
#declare Speed = TimeElapsed ("#declare HeapSorted = HeapSort (HeapSorted)");
#debug concat("\n     Heap sorting ", str (Items, 0, 0), " items took ", TimeUnits (Speed), " \n")

#error "Stopping render: No elements in scene."