
import java.util.Arrays;
import java.util.Comparator;
import java.util.Random;

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
/**
 *
 * @author Lucas de Lima Rodrigues
 */
public class QuickSort implements SortAlgorithm {

    Random rand = new Random();

    public Object[] _sort(Object v[], Comparator c, int esquerda, int direita) {
        int esq = esquerda, dir = direita;
        Object pivo = v[rand.nextInt(direita - esquerda + 1) + esquerda], aux;

        while (esq <= dir) {
            while (c.compare(v[esq], pivo) < 0) {
                esq++;
            }
            while (c.compare(v[dir], pivo) > 0) {
                dir--;
            }
            if (esq <= dir) {
                aux = v[esq];
                v[esq] = v[dir];
                v[dir] = aux;
                esq++;
                dir--;
            }
        }

        if (dir > esquerda) {
            _sort(v, c, esquerda, dir);
        }
        if (esq < direita) {
            _sort(v, c, esq, direita);
        }

        return v;
    }

    @Override
    public Object[] sort(Object[] collection, Comparator comparator) {
        Object copy[] = new Object[collection.length];
        System.arraycopy(collection, 0, copy, 0, collection.length);
        return _sort(copy, comparator, 0, copy.length - 1);
    }

}

@@ -449,84 +449,163 @@
 int 
-esquerda, int direita) %7B%0A        int esq = esquerda, dir = direita;%0A
+length) %7B%0A        if (length %3E 1) %7B%0A            Object%5B%5D lowers = new Object%5Blength%5D, equals = new Object%5Blength%5D, biggers = new Object%5Blength%5D;%0A  
         
 Obje
@@ -596,24 +596,26 @@
 ;%0A          
+  
 Object pivo 
@@ -635,51 +635,70 @@
 Int(
-direita - esquerda + 1) + esquerda%5D, aux;%0A%0A
+length)%5D;%0A            int k = 0, kl = 0, ke = 0, kb = 0;%0A%0A    
     
@@ -708,26 +708,26 @@
  while (
-esq %3C= dir
+k %3C length
 ) %7B%0A    
@@ -726,37 +726,38 @@
 ) %7B%0A            
+  
-while
+  if
  (c.compare(v%5Bes
@@ -756,23 +756,22 @@
 are(
-v%5Besq%5D, pivo) %3C
+pivo, v%5Bk%5D) ==
  0) 
@@ -792,29 +792,39 @@
     
-esq++;%0A       
+    equals%5Bke++%5D = v%5Bk++%5D;%0A
     
- %7D%0A
     
@@ -831,21 +831,25 @@
         
-while
+%7D else if
  (c.comp
@@ -856,20 +856,18 @@
 are(
-v%5Bdir%5D, pivo
+pivo, v%5Bk%5D
 ) %3E 
@@ -891,58 +891,121 @@
     
-dir--;%0A            %7D%0A            if (esq %3C= dir) %7B
+    lowers%5Bkl++%5D = v%5Bk++%5D;%0A                %7D else %7B%0A                    biggers%5Bkb++%5D = v%5Bk++%5D;%0A                %7D
 %0A   
@@ -1017,57 +1017,161 @@
     
+%7D%0A%0A
     
-aux = v%5Besq%5D;%0A                v%5Besq%5D = v%5Bdir%5D
+        lowers = _sort(lowers, c, kl);%0A            biggers = _sort(biggers, c, kb);%0A%0A            return merge(lowers, kl, equals, ke, biggers, kb)
 ;%0A  
@@ -1176,24 +1176,27 @@
         
+%7D%0A%0A
         
 v%5Bdir%5D =
@@ -1191,81 +1191,245 @@
     
-v%5Bdir%5D = aux;%0A                esq++;%0A                dir--;%0A            %7D
+return v;%0A    %7D%0A%0A    private Object%5B%5D merge(Object%5B%5D l, int ll, Object%5B%5D e, int el, Object%5B%5D b, int bl) %7B%0A        int k = 0;%0A        Object%5B%5D s = new Object%5Bll + el + bl%5D;%0A        for (int i = 0; i %3C ll; i++) %7B%0A            s%5Bk++%5D = l%5Bi%5D;
 %0A   
@@ -1435,25 +1435,24 @@
       %7D%0A
-%0A
         
 if (dir 
@@ -1447,146 +1447,140 @@
     
-if (dir %3E esquerda) %7B%0A            _sort(v, c, esquerda, dir);%0A        %7D%0A        if (esq %3C direita) %7B%0A            _sort(v, c, esq, direita)
+for (int i = 0; i %3C el; i++) %7B%0A            s%5Bk++%5D = e%5Bi%5D;%0A        %7D%0A        for (int i = 0; i %3C bl; i++) %7B%0A            s%5Bk++%5D = b%5Bi%5D
 ;%0A  
@@ -1579,33 +1579,32 @@
 b%5Bi%5D;%0A        %7D%0A
-%0A
         return v
@@ -1594,33 +1594,33 @@
 %0A        return 
-v
+s
 ;%0A    %7D%0A%0A    @Ov
@@ -1859,19 +1859,16 @@
 parator,
- 0,
  copy.le
@@ -1875,12 +1875,8 @@
 ngth
- - 1
 );%0A 

Update QuickSort