using System;
using System.Collections.Generic;
using System.Text;

namespace SearchAlgorithms
{
    class Search
    {

        const int ARRAYLENGTH = 5000;	
        public static int[] randomArray = new int[ARRAYLENGTH];
        public static int[] qsArrayClone = new int[ARRAYLENGTH];
        public static int[] isArrayClone = new int[ARRAYLENGTH];
        public static int[] msArrayClone = new int[ARRAYLENGTH];
        public static int[] hsArrayClone = new int[ARRAYLENGTH];
        public static int[] temp = new int[ARRAYLENGTH];
        
        public static int msACSize = randomArray.Length - 1;
       
        public static int isKeyComparisons;
        public static int qsKeyComparisons;
        public static int msKeyComparisons;
        public static int hsKeyComparisons;

        static void Main(string[] args)
        {
            arraySetUp();

            linearSearch(isArrayClone); 
            quickSort(qsArrayClone, 0, msACSize);
            mSort(msArrayClone, 0, msACSize + 1);
            heapSort(hsArrayClone);

            Console.WriteLine("First 100 of the linear search ");
            printArray(isArrayClone);

            Console.WriteLine("First 100 of the quick sort");
            printBackwards(qsArrayClone);

            Console.WriteLine("First 100 of the merge sort ");
            printBackwards(msArrayClone);

            Console.WriteLine("First 100 of the heap sort ");
            printBackwards(hsArrayClone);

            Console.WriteLine("Insertion sort key " + isKeyComparisons);
            Console.WriteLine("Quick sort key " + qsKeyComparisons);
            Console.WriteLine("Merge sort key " + msKeyComparisons);
            Console.WriteLine("Heap sort key " + hsKeyComparisons);
        }

        private static void arraySetUp()
        {
            Random newRandom = new Random();
            for (int x = 0; x < 5000; x++)
            {
                randomArray[x] = newRandom.Next();
            }
            randomArray.CopyTo(qsArrayClone, 0);
            randomArray.CopyTo(isArrayClone, 0);
            randomArray.CopyTo(msArrayClone, 0);
            randomArray.CopyTo(hsArrayClone, 0);
        }

        private static void printArray(int[] sortedArray)
        {
            for (int x = 0; x < 100; x++)
            {
                Console.WriteLine(sortedArray[x]);
            }
            Console.Write("\n");
        }

        // print out the first 100 sorted items
        private static void printBackwards(int[] sortedArray)
        {

            for (int x = sortedArray.Length - 1; x > 4899; x--)
            {
                Console.WriteLine(sortedArray[x]);
            }
            Console.Write("\n");
        }

        private static void linearSearch(int[] isArrayClone)
        {
            // copy the random array into the array we will be dealing with in this function
            //randomArray.CopyTo(qsArrayClone, 0);

            int maxValue = 0;                   // set a highest value to compare to
            int maxValuePosition = 0;           // position of current highest
            int replacePosition = 0;            // position we are checking against all values

            while (replacePosition < 100)
            {
                maxValue = isArrayClone[replacePosition];
                maxValuePosition = replacePosition;

                // iterate through array, comparing maxValue to each value in the array
                for (int checkPosition = replacePosition; checkPosition < isArrayClone.Length; checkPosition++)
                {
                    isKeyComparisons++;
                    if (isArrayClone[checkPosition] > maxValue)
                    {
                        //copy the value into max 
                        maxValue = isArrayClone[checkPosition];
                        maxValuePosition = checkPosition;
                    }
                }
                int temp = isArrayClone[replacePosition]; // temp to hold swappable int
                isArrayClone.SetValue(maxValue, replacePosition); // move max value to correct position
                isArrayClone.SetValue(temp, maxValuePosition); // move temp to old max position
                replacePosition++; // increase n by 1 to move the swapper
            }
        }

        private static void quickSort(int[] qsArrayClone, int pivot, int right)
        {
            if (pivot < right)
            {
                //qsMainCount++;
                int left = qsortPartition(qsArrayClone, pivot, right);
                quickSort(qsArrayClone, pivot, left);
                quickSort(qsArrayClone, left + 1, right);
            }
        }

        private static int qsortPartition(int[] qsArrayClone, int pivot, int right)
        {
            int leftNew = pivot - 1;
            int rightNew = right + 1;
            int pivotNew = qsArrayClone[pivot];
            
                // in between n log base 2 n and n^2

                while (true)
                {
                    do
                    {
                        qsKeyComparisons++;
                        rightNew--;
                    }
                    while (qsArrayClone[rightNew] > pivotNew);

                    do
                    {
                        qsKeyComparisons++;
                        leftNew++;
                    }
                    while (qsArrayClone[leftNew] < pivotNew);

                    if (leftNew < rightNew)
                    {
                        qsKeyComparisons++;
                        qsortSwap(qsArrayClone, leftNew, rightNew);
                    }
                    else
                        return rightNew;
                }
        }

        private static void qsortSwap(int[] qsArrayClone, int leftNew, int rightNew)
        {
            int tempHold = qsArrayClone[leftNew];
            qsArrayClone[leftNew] = qsArrayClone[rightNew];
            qsArrayClone[rightNew] = tempHold;
        }

        public static void mSort(int[] msArrayClone, int first, int msACSize)
        {
            int leftSize; // Size of the first half of the array
            int rightSize; // Size of the second half of the array

            if (msACSize > 1)
            {
               // msKeyComparisons++;
                // Compute sizes of the two halves
                leftSize = msACSize / 2;
                rightSize = msACSize - leftSize;

                mSort(msArrayClone, first, leftSize);      // Sort randomArrayClone[first] through randomArrayClone[first+leftSize-1]
                mSort(msArrayClone, first + leftSize, rightSize); // Sort randomArrayClone[first+leftSize] to the end

                // Merge the two sorted halves.
                merge(msArrayClone, first, leftSize, rightSize);
            }
        }

        private static void merge(int[] msArrayClone, int first, int leftSize, int rightSize)
        {
            // int[] temp = new int[leftSize + rightSize]; // Allocate the temporary array
            int copied = 0; // Number of elements copied from randomArrayClone to temp
            int copied1 = 0; // Number copied from the first half of randomArrayClone
            int copied2 = 0; // Number copied from the second half of randomArrayClone
            int i;           // Array index to copy from temp back into randomArrayClone

            // Merge elements, copying from two halves of randomArrayClone to the temporary array.
            while ((copied1 < leftSize) && (copied2 < rightSize))
            {
                msKeyComparisons++;
                if (msArrayClone[first + copied1] < msArrayClone[first + leftSize + copied2])
                {
                    temp[copied++] = msArrayClone[first + (copied1++)];
                }
                else
                {     
                    temp[copied++] = msArrayClone[first + leftSize + (copied2++)];
                }
            }

            // Copy any remaining entries in the left and right subarrays.
            while (copied1 < leftSize)
            {
                temp[copied++] = msArrayClone[first + (copied1++)];
                msKeyComparisons++;    
            }
            while (copied2 < rightSize)
            {
                msKeyComparisons++;
                temp[copied++] = msArrayClone[first + leftSize + (copied2++)];
            }
            // Copy from temp back to the randomArrayClone array.
            for (i = 0; i < leftSize + rightSize; i++)
            {
                msKeyComparisons++;
                msArrayClone[first + i] = temp[i];
            }
        }

        private static void heapSort(int[] hsArrayClone)
        {
            hSort(hsArrayClone.Length - 1);
        }

        private static void hSort(int end)
        {
            // Establish the heap property.
            for (int x = end / 2; x >= 0; x--)
            rebuildHeap(x, end, hsArrayClone[x]);

            // Now place the largest element last,
            for (int x = end; x > 0; x--)
            {
                // a[0] is the next-biggest element.
                swapElements(0, x);
                hsKeyComparisons++;
                
                // Heap shrinks by 1 element.
                rebuildHeap(0, x - 1, hsArrayClone[0]);
            }
        }

        private static void rebuildHeap(int root, int end, int key)
        {
            int child = 2 * root; // left child

            // Find the larger child.
            if (child < end && hsArrayClone[child] < hsArrayClone[child + 1])
            {
                hsKeyComparisons++;
                child++;  // right child is larger
            }

            // If the larger child is larger than the element at the root, move the larger child
            // to the root and filter the former root element down into the "larger" subtree.
            
            if (child <= end && key < hsArrayClone[child])
            {
                hsArrayClone[root] = hsArrayClone[child];
                rebuildHeap(child, end, key);
             }
            else
                hsArrayClone[root] = key;
        }

        private static void swapElements(int a, int b)
        {
            int temp = hsArrayClone[a];
            hsArrayClone[a] = hsArrayClone[b];
            hsArrayClone[b] = temp;
        }
    }
}