Не рекурсивный QuickSort

Question

Мне любопытно узнать, имеет ли моя реализация нерекурсивного алгоритма QuickSort некоторые недостатки или скрытые камни. Что нужно изменить для его оптимизации? И какие проблемы могут возникнуть при сравнении двух объектов так, как я это делаю?

public class QuickSort <T extends Number> { 

private Integer first, last, boundLo, boundHi, pivot; 
Integer temp[] = {0, 0}; 

public void sort(NewArrayList<T> vect) { 
    Deque<Integer[]> stack = new ArrayDeque<Integer[]>(); 

    first = 0; 
    last = vect.size() - 1; 
    stack.push(new Integer[] {first, last}); 

    while(!stack.isEmpty()) { 
     sortStep(vect, stack); 
    } 
} 

private void sortStep(NewArrayList<T> vect, Deque<Integer[]> stack) { 
    // initialize indices 
    temp = stack.pop(); 
    first = temp[0]; 
    last = temp[1]; 

    boundLo = first; 
    boundHi = last; 
    pivot = last; 

    while(first < last) { 
     if(vect.get(first).doubleValue() >= vect.get(pivot).doubleValue()) { 
      last--; 
      if(first != last) 
       vect.swap(first, last);   
      vect.swap(last, pivot); 
      pivot--; 
     } 
     else first++; 
    } 

    if(boundLo < (pivot - 1)) 
     stack.add(new Integer[] {boundLo, pivot - 1}); 

    if(boundHi > (pivot + 1)) 
     stack.add(new Integer[] {pivot + 1, boundHi}); 

} 

} 

И является ли ArrayList лучшей коллекцией такого рода?

public class NewArrayList<T> extends ArrayList<T> { 

public NewArrayList() { 
    super(); 
} 

public void swap(int index1, int index2) { 
    this.set(index1, this.set(index2, this.get(index1))); 
} 
} 

код после изменения с учетом предложений

public class QuickSort <T extends Number> { 

private int first, last, boundLo, boundHi, pivot; 
int temp[] = {0, 0}; 

public QuickSort() { 
    super(); 
} 

public void sort(List<T> list) { 

    Deque<int[]> stack = new ArrayDeque<int[]>(); 

    first = 0; 
    last = list.size() - 1; 

    stack.push(new int[] {first, last}); 

    while(!stack.isEmpty()) { 
     sortStep(list, stack); 
    } 
} 

private void sortStep(List<T> list, Deque<int[]> stack) { 

    temp = stack.pop(); 
    first = temp[0]; 
    last = temp[1]; 

    boundLo = first; 
    boundHi = last; 
    pivot = last; 

    while(first < last) { 
     if(list.get(first).doubleValue() >= list.get(pivot).doubleValue()) { 
      last--; 
      if(first != last) 
       Collections.swap(list, first, last);    
      Collections.swap(list, last, pivot); 
      pivot--; 
     } 
     else first++; 
    } 

    if(boundLo < (pivot - 1)) 
     stack.add(new int[] {boundLo, pivot - 1}); 

    if(boundHi > (pivot + 1)) 
     stack.add(new int[] {pivot + 1, boundHi}); 
} 

} 

Answer 1

public class Sort { 
    /** Returns a sorted list of attributes. */ 
    protected int[] sortAttributes1(int[] array) { 

     Queue<Range> queue = new ArrayDeque<Range>(); 

     while (!queue.isEmpty()) { 
      Range range = queue.poll(); 
      if (range.isEmpty()) { 
       continue; 
      } 
      int left = range.getLeft(); 
      int right = range.getRight(); 
      // partition the range 
      right = partition(array, left, right); 
      Range lr = new Range(range.getLeft(), right - 1); 
      Range rr = new Range(right + 1, range.getRight()); 

      queue.add(lr); 
      queue.add(rr); 
     } 
     return array; 
    } 


    private int partition(int[] array, int left, int right) { 
     int pivot = right - left >>> 2; 


     while (left <= right) { 
      int pivotVal = array[pivot]; 
      if (array[left] <= pivotVal) { 
       left++; 
       continue; 
      } 
      right--; 
      if (left == right)continue; 
      int temp = array[left]; 
      array[left] = array[right]; 
      array[right] = temp; 
     } 

     int temp = array[pivot]; 
     array[pivot] = array[right]; 
     array[right] = temp; 

     return right; 
    }  
}