using System.Collections;
using System.Collections.Generic;
using UnityEngine;

public class QS : MonoBehaviour {
    // This function will start the whole code off.
    void Start(){
        // This is to define the array and put in numbers to test the code out.
        int[] Array = new int[] { 13, 10, 27, 101, 4, 25 };
        //This will call the startsort function.
        startsort (Array);

        // this code is for after the array is sorted and it will loop until all of
        //the numbers in the array are displayed in the console.
        for (int j = 0; j < Array.Length; j++) {
            Debug.Log (Array [j]);
        }
    }


    private void startsort(int[] Array){
        //once this function is called in the start function, the quicksort function
        //is called with the array, 0 being the first value in the array and then the last value of the array.
        // the last value of the array is taken by getting the array length and subtracting one because arrays start with 0.
        quicksort (Array, 0, (Array.Length - 1));


    }

    private void quicksort (int[] Array, int start, int end){
        // these three lines are to define the variables for the process.
        //left will be the first value in the array and it is the leftmark for the quicksort.
        int left = start;
        // right will be the last value in the array and it is the rightmark for the quicksort.
        int right = end;
        // This is where the pivot is calculated. You want the pivot to be in the middle of the
        //array which is why left and right are added together and then divided by 2 to get roughly in the middle.
        var pivot = (Array[(left + right) / 2]);
        // This is the loop that starts everything off. it will loop when the left is smaller than or equal to the right.
        // As soon as left is larger than right that means that all of the numbers that are to the
        //right of the pivot are smaller than the pivot and all of the numbers to the right of the pivot are larger.
        while (left <= right) {
            // this will compare the left to the pivot. If it is smaller than the pivot then it
            //will add 1 to left meaning the next number along the array will be compared to the pivot.
            while (Array [left] < pivot) {
                left++;
            }
            // This is the same but for the right.
            // This loop will start when a number that is larger than the pivot is found on the left because
            //now we are trying to find a number on the right side that is smaller than the pivot to swap them numbers.
            while (Array [right] > pivot) {
                right--;
            }
            //This code will swap the numbers around but only if the left is smallar or equal to the right.
            //If left is larger then that means that the right and left have passed each other in the array meaning the numbers shouldnt swap.
            if (left <= right) {
                // temp is used to temporarily store the value that is in the array location of value left.
                // this is so that the two numbers can be swapped.
                var temp = Array [left];
                Array [left] = Array [right];
                Array [right] = temp;
                // the left and right is shifted across to the next space so that the code is looped around once more because of the first while loop.
                left++;
                right--;
            }

        }

        // Once all of the numbers on the left are smaller than the pivot and all of the numbers on the right are
        //larger than the pivot we need to run the code through again for the left and right side.
        //This will use the previous base code to sort the left side using different values for the left and the right.
        // I use recursion here to call the funtion again but with different values for the left and right.
        if (start < right) {
            quicksort (Array, start, right);

        }
        // once all of the left side is sorted, this code will run the base code again but for the right side.
        if (left < end) {
            quicksort (Array, left, end);

        }
        // once all of the numbers are sorted the the for loop in the start function will output all of the numbers.
    }

}