package src;

public class SortingAlgorithms {
	
	public static double[] bubbleSort(double[] myArray) {
		double[] arr = new double[myArray.length];
		System.arraycopy(myArray, 0, arr, 0, myArray.length);
		for (int i = 0; i < arr.length - 1; i++) {
			for (int j = 0; j < arr.length - i - 1; j++) {
				if (arr[j] > arr[j + 1]) {
					swap(arr, j, j + 1);
				}
			}
		}
		return arr;
	}

	public static double[] selectionSort(double[] myArray) {
		int min;
		double[] arr = new double[myArray.length];
		System.arraycopy(myArray, 0, arr, 0, myArray.length);
		for (int i = 0; i < arr.length - 1; i++) {
			min = i;
			for (int j = i + 1; j < arr.length; j++)
				if (arr[j] < arr[min])
					min = j;
			swap(arr, min, i);
		}
		return arr;
	}

	public static double[] insertionSort(double[] myArray) {
		double[] arr = new double[myArray.length];
		System.arraycopy(myArray, 0, arr, 0, myArray.length);
		for (int i = 1; i < arr.length; i++) {
			int j = i;
			while (j > 0 && arr[j - 1] > arr[j]) {
				swap(arr, j, j - 1);
				j = j - 1;
			}
		}
		return arr;
	}

	// Array A[] has the items to sort; array B[] is a work array.
	public static double[] topDownMergeSort(double[] myArray, double[] B) {
		double[] arr = new double[myArray.length];
		System.arraycopy(myArray, 0, arr, 0, myArray.length);
		CopyArray(arr, 0, arr.length, B); // duplicate array A[] into B[]
		TopDownSplitMerge(B, 0, arr.length, arr); // sort data from B[] into A[]
		// displayArr(A);
		return arr;
	}
	
	public static double[] heapSort(double[] myArray) {
		double[] arr = new double[myArray.length];
		System.arraycopy(myArray, 0, arr, 0, myArray.length);
		buildheap(arr);
		for (int i = arr.length - 1; i >= 1; i--) {
			double temp = arr[0];
			arr[0] = arr[i];
			arr[i] = temp;
			heapify(arr, i, 0);
		}
		// displayArr(a);
		return arr;
	}
	
	public static double[] quickSort(double[] myArray) {
    	double[] arr = new double[myArray.length];
		System.arraycopy(myArray, 0, arr, 0, myArray.length);
        recursiveQuickSort(arr, 0, arr.length - 1);
        return arr;
    }
	
	public static double[] shellSort(double[] myArray) {
		double[] arr = new double[myArray.length];
		System.arraycopy(myArray, 0, arr, 0, myArray.length);
		int inner, outer;
		double temp;

		int h = 1;
		while (h <= arr.length / 3) {
			h = h * 3 + 1;
		}
		while (h > 0) {
			for (outer = h; outer < arr.length; outer++) {
				temp = arr[outer];
				inner = outer;
				while (inner > h - 1 && arr[inner - h] >= temp) {
					arr[inner] = arr[inner - h];
					inner -= h;
				}
				arr[inner] = temp;
			}
			h = (h - 1) / 3;
		}
		return arr;
	}

	public static double[] combSort(double[] myArray) {
		double[] arr = new double[myArray.length];
		System.arraycopy(myArray, 0, arr, 0, myArray.length);
		/*
		 * This function sorts a list in-place using CombSort11. It works
		 * exactly like BubbleSort except that instead of looking at i and i+1
		 * when iterating, it looks at i and i+gap. This helps reposition small
		 * values stuck at the end of the array.
		 */

		int gap = arr.length; // The distance between elements being compared
		boolean swapped = true;
		int i; // Our index

		// keep looping until you make
		// a complete pass without swapping
		while (gap > 1 || swapped) {

			// 1.3 is the shrink factor.
			// I found it to be the fastest.
			// A gap can not be smaller than 1,
			// hence the "if (gap > 1)"
			if (gap > 1) {
				gap = (int) (gap / 1.3);
			}

			// This is why it is CombSort11
			// instead of CombSort. I find
			// doing this increases the speed
			// by a few milliseconds.
			if (gap == 9 || gap == 10) {
				gap = 11;
			}

			i = 0;
			swapped = false;

			// Loop through comparing numbers a gap-length apart.
			// If the first number is bigger than the second, swap them.
			while (i + gap < arr.length) {
				if (arr[i] > arr[i + gap]) {
					swap(arr, i, i + gap);
					swapped = true;
				}
				i++;
			}
		}
		return arr;
	}

	//compare array
	public static boolean compareArray(double[] arr1, double[]arr2){
		if(arr1.length != arr2.length)
			return false;
		else {
			for(int i=0 ; i<arr1.length; i++){
				if(arr1[i] != arr2[i])
					return false;
			}
		}
		return true;
	}
		
		//display array
		public static void displayArr(double[] arr) {
			System.out.println("Array: ");
			for (int i = 0; i < arr.length; i++) {
				System.out.print(arr[i] + " ");
			}
			System.out.println();
		}
		
		public static String toStringArray(double[] arr) {
			String result= "";
			for (int i = 0; i < arr.length; i++) {
				result += arr[i] + " ";
			}
			return result;
		}
	
	
	
	
	// Sort the given run of array A[] using array B[] as a source.
	// iBegin is inclusive; iEnd is exclusive (A[iEnd] is not in the set).
		
		/**
	     * Recursive quicksort logic
	     *
	     * @param array input array
	     * @param startIdx start index of the array
	     * @param endIdx end index of the array
	     */
	    public static void recursiveQuickSort(double[] array, int startIdx, int endIdx) {
	     
	        int idx = partition(array, startIdx, endIdx);

	        // Recursively call quicksort with left part of the partitioned array
	        if (startIdx < idx - 1) {
	            recursiveQuickSort(array, startIdx, idx - 1);
	        }

	        // Recursively call quick sort with right part of the partitioned array
	        if (endIdx > idx) {
	            recursiveQuickSort(array, idx, endIdx);
	        }
	    }

	    /**
	     * Divides array from pivot, left side contains elements less than
	     * Pivot while right side contains elements greater than pivot.
	     *
	     * @param array array to partitioned
	     * @param left lower bound of the array
	     * @param right upper bound of the array
	     * @return the partition index
	     */
	    public static int partition(double[] array, int left, int right) {
	        double pivot = array[left]; // taking first element as pivot

	        while (left <= right) {
	            //searching number which is greater than pivot, bottom up
	            while (array[left] < pivot) {
	                left++;
	            }
	            //searching number which is less than pivot, top down
	            while (array[right] > pivot) {
	                right--;
	            }

	            // swap the values
	            if (left <= right) {
	                double tmp = array[left];
	                array[left] = array[right];
	                array[right] = tmp;

	                //increment left index and decrement right index
	                left++;
	                right--;
	            }
	        }
	        return left;
	    }
		
		
		
	private static void TopDownSplitMerge(double[] B, int iBegin, int iEnd, double[] A) {
		if (iEnd - iBegin < 2) // if run size == 1
			return; // consider it sorted
		// split the run longer than 1 item into halves
		int iMiddle = (iEnd + iBegin) / 2; // iMiddle = mid point
		// recursively sort both runs from array A[] into B[]
		TopDownSplitMerge(A, iBegin, iMiddle, B); // sort the left run
		TopDownSplitMerge(A, iMiddle, iEnd, B); // sort the right run
		// merge the resulting runs from array B[] into A[]
		TopDownMerge(B, iBegin, iMiddle, iEnd, A);
	}

	// Left source half is A[ iBegin:iMiddle-1].
	// Right source half is A[iMiddle:iEnd-1 ].
	// Result is B[ iBegin:iEnd-1 ].
	private static void TopDownMerge(double[] A, int iBegin, int iMiddle, int iEnd, double[] B) {
		int i = iBegin, j = iMiddle;

		// While there are elements in the left or right runs...
		for (int k = iBegin; k < iEnd; k++) {
			// If left run head exists and is <= existing right run head.
			if (i < iMiddle && (j >= iEnd || A[i] <= A[j])) {
				B[k] = A[i];
				i = i + 1;
			} else {
				B[k] = A[j];
				j = j + 1;
			}
		}
	}

	private static void CopyArray(double[] A, int iBegin, int iEnd, double[] B) {
		for (int k = iBegin; k < iEnd; k++)
			B[k] = A[k];
	}

	private static void heapify(double a[], int n, int i) {
		int max, child;
		child = 2 * i + 1;
		max = i;
		if (child < n)
			if (a[child] > a[max])
				max = child;
		if (child + 1 < n)
			if (a[child + 1] > a[max])
				max = child + 1;
		if (max != i) {
			double temp = a[i];
			a[i] = a[max];
			a[max] = temp;
			heapify(a, n, max);
		}
	}

	private static void buildheap(double a[]) {
		for (int i = a.length / 2 - 1; i >= 0; i--)
			heapify(a, a.length, i);
	}


	private static void swap(double[] arr, int index1, int index2) {
		double tempNum = arr[index1];
		arr[index1] = arr[index2];
		arr[index2] = tempNum;
	}

	
}