Sorting

import java.util.Arrays;

class Main {
    
    
    public static void bubbleSort(int[] list){
        for (int firstIndex= 0 ; firstIndex < list.length; firstIndex++ ){
            for (int secondIndex= 0 ; secondIndex < list.length-1; secondIndex++){
                if (list[secondIndex] > list [secondIndex+1]){
                    //System.out.println("first:"+firstIndex+" second:"+secondIndex);
                    //System.out.println(""+list[firstIndex]+" >"+list[secondIndex]);
                    int temporalHolder= list[secondIndex];
                    list[secondIndex]= list[secondIndex+1];
                    list[secondIndex+1] = temporalHolder;
                    //printAll(list);
                }
            }
        }
    }
    
    /**
     *  Simple implementation of selection sort
     *  List is a list of integers
     * Returns exception if the list is null or empty
     **/
    public static void selectionSort(int[] list){
        if ( list == null || list.length==0){
            throw new RuntimeException("The list is null or empty.");
        }
        int length = list.length;
        
        for (int placementIndex = 0; placementIndex <  length; placementIndex++){
            int selected= placementIndex;
            for (int searchingIndex = placementIndex; searchingIndex < length; searchingIndex++){
                if (list[selected] > list[searchingIndex]){
                    selected= searchingIndex;
                }
            }
            swap(list, selected, placementIndex);
        }
    }
    
    /*public static void insertionSort(int[] list){
        
        for (int index =0 ; index < list.length; index++){
            int selected=index;
            if (list[reverseIndex-1] > list[reverseIndex]){
                for (int reverseIndex = index; reverseIndex > 0 ; reverseIndex--){
                    swap(list, reverseIndex-1, reverseIndex);
                }
            }
            
            printAll(list);
        }
        
    }*/
    
    public static int[] mergeSort(int [] array){
        if (array.length == 1){
            return array;
        }
        //Split Array in into rigth and left
        int[] left = Arrays.copyOfRange(array, 0, (array.length/2));
        int[] right = Arrays.copyOfRange(array, (array.length/2), array.length);
        //printAll(left);
        //printAll(right);
        
        return merge(mergeSort(left), mergeSort(right));
    }
    
    public static int[] merge(int[] array1, int [] array2){
        
        int[] newArray = new int[array1.length+array2.length];
        int newIndex=0, leftIndex=0, rightIndex=0;
        
      //  printAll(array1);
    //    printAll(array2);
        while (newIndex< array1.length+array2.length){
            if (leftIndex < array1.length && rightIndex < array2.length){
                if (array1[leftIndex] <= array2[rightIndex]){
                    newArray[newIndex++]= array1[leftIndex++];
                } else {
                    newArray[newIndex++]= array2[rightIndex++];
                }
            } else if (leftIndex < array1.length){
                newArray[newIndex++]= array1[leftIndex];
                leftIndex++;
            }  else if (rightIndex < array2.length){
                newArray[newIndex++]= array2[rightIndex];
                rightIndex++;
            }
        }
        //printAll(newArray);
        /*for (int i =0; i < array1.length; i++){
            for (int j =0 ; j < array2.length;j++){
                System.out.println("Comparing "+array1[i]+" "+array2[j]);
                if (array1[i] >= array2[j]){
                    newArray[index] = array2[j];    
                } else {
                    newArray[index] = array1[j];
                }
                index++;
                
            }
        }*/
        //System.out.println("New Array");
        //printAll(newArray);
        
        return newArray;
    }
    
    /*public int[] mergeSort(int [] array, int left, int right){
        if (right-left == 1){
            return array;
        }
        
        return merge(mergeSort(array, left, middle), mergeSort(array, middle+1, right));
    }*/

// 4 5 6 7 1 2 3 
// 1 4 5 6 7 2 3
// 1 2 4 5 6 7 3
// 1 2 3 4 5 6 7
//
//
//





    
    
    public static void swap(int[] list, int selected, int placementIndex){
        int temporalHolder= list[selected];
        list[selected] = list[placementIndex];
        list[placementIndex] = temporalHolder;
    }
    public static void printAll(int[] list){
        System.out.println(" ");
        for (int index = 0; index < list.length; index++){
            System.out.print(list[index]+" ");
        }
    }
    
    /*
        const numbers = [99, 44, 6, 2, 1, 5, 63, 87, 283, 4, 0];

function quickSort(array, left, right) {
 
}

function partition(array, pivot, left, right) {
  
}

function swap(array, firstIndex, secondIndex) {
  
}

//Select first and last index as 2nd and 3rd parameters
quickSort(numbers, 0, numbers.length - 1);
console.log(numbers);
    */
    public static void quicksort(int[] array, int left, int right){
        if (array.length == 1){
            return;
        }
        partition(array, (right-left)/2, left, right);    
    }
    public static void partition(int[] array, int pivot, int left, int right){
        System.out.println("left:"+left+" Pivot: "+pivot+" right:"+right);
        if (pivot - left <= 0  ||  right - pivot <= 0 ){
            System.out.println("Returning...");
            return;
        }
        
        int pointer = left;
        while (pointer < pivot ){
            if (array[pointer]> array[pivot]){
                swap(array, pointer, pivot-1);
                swap(array,pivot-1, pivot--);
            } else {
                pointer++;
            }
        }
        
        partition(array, (pivot - left)/2, left, pivot);
        partition(array, (right - pivot)/2, pivot, right);
    }
    
    
    
    public static void main(String[] args) {
        int [] list = new int[]{10,9,8,7,6,5,4,3,2,1};
        printAll(list);
        //int[] sortedArray=mergeSort(list);
        quicksort(list, 0, list.length-1);
        printAll(list);
    }
}