Not so simple QuickSort in Java
package com.julio.quicksort;
import java.math.*;
import java.util.*;
import java.lang.System;
public class QuickSort {
public static void main(String args[]) {
QuickSort sort = new QuickSort();
int[] input = {1,2,5,4,3,2,6,7,8,34,22,-22,22,-22,22-123,1241,-12412,9,-1,-12,2,44};
String s = Arrays.toString(sort.sort(input));
System.out.println(s);
}
public int[] sort(int[] input) {
if (input.length == 1) {
return input;
}
return sortInternal(input, input.length);
}
private int[] sortInternal(int[] integers, int size) {
System.out.println("Input" + Arrays.toString(integers));
if (size <= 1) {
return integers;
}
int pivot = (int) (Math.random() * size);
System.out.println("Pivot " + pivot);
int pivotValue = integers[pivot];
int l[] = new int[size];
int r[] = new int[size];
int ll = 0;
int rl = 0;
int sum = 0;
for (int i = 0; i < size ; ++i) {
sum += integers[i];
if (integers[i] < pivotValue) {
l[ll++] = integers[i];
} else {
r[rl++] = integers[i];
}
}
if (sum/(float)size == integers[0]) {
return integers;
}
System.out.println("left " + Arrays.toString(l));
System.out.println("right " + Arrays.toString(r));
int[] finalArray = new int[size];
System.arraycopy(sortInternal(l, ll), 0, finalArray, 0, ll);
System.arraycopy(sortInternal(r, rl), 0, finalArray, ll, rl);
return finalArray;
}
}
import java.math.*;
import java.util.*;
import java.lang.System;
public class QuickSort {
public static void main(String args[]) {
QuickSort sort = new QuickSort();
int[] input = {1,2,5,4,3,2,6,7,8,34,22,-22,22,-22,22-123,1241,-12412,9,-1,-12,2,44};
String s = Arrays.toString(sort.sort(input));
System.out.println(s);
}
public int[] sort(int[] input) {
if (input.length == 1) {
return input;
}
return sortInternal(input, input.length);
}
private int[] sortInternal(int[] integers, int size) {
System.out.println("Input" + Arrays.toString(integers));
if (size <= 1) {
return integers;
}
int pivot = (int) (Math.random() * size);
System.out.println("Pivot " + pivot);
int pivotValue = integers[pivot];
int l[] = new int[size];
int r[] = new int[size];
int ll = 0;
int rl = 0;
int sum = 0;
for (int i = 0; i < size ; ++i) {
sum += integers[i];
if (integers[i] < pivotValue) {
l[ll++] = integers[i];
} else {
r[rl++] = integers[i];
}
}
if (sum/(float)size == integers[0]) {
return integers;
}
System.out.println("left " + Arrays.toString(l));
System.out.println("right " + Arrays.toString(r));
int[] finalArray = new int[size];
System.arraycopy(sortInternal(l, ll), 0, finalArray, 0, ll);
System.arraycopy(sortInternal(r, rl), 0, finalArray, ll, rl);
return finalArray;
}
}
<< Home