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);
}
}
