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.
	}

}