Saturday, November 23, 2013

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