Iteratives Quicksort in Java

Nachdem man bei der rekursiven Quicksort sehr schnell an Speichergrenzen stößt habe ich es mal iterativ implementiert.
Der Vergleich zu meiner Implementierung von Bobblesort zeigt bei einer Liste von 100000 Einträgen mit 1000 verschiedenen Werten einen beträchlichen Geschwindigkeitsvorsprung:
- Bubblesort ca. 40000 ms.
- Quicksort ca. 120 ms.
Übergibt man jedoch beiden eine schon sortierte Liste derselben Größe kehrt sich das um:
- Bubblesort ca. 12 ms.
- Quicksort ca. 2000 ms.

package at.ande.sorting.quicksort;

import java.util.ArrayList;
import java.util.Stack;

import at.ande.sorting.utils.SortingUtils;

public class QuickSort2 {

 ArrayList list;

 public ArrayList quickSort2(ArrayList arraylist) {
  list = arraylist;
  sort(0, arraylist.size() - 1);
  return list;
 }

 public void sort(int left, int right) {
  Stack stack = new Stack();
  while (true) {
   if (left < right) {
    int pivot = list.get(SortingUtils.randomOfTwo(left, right));
    int i = left - 1;
    int j = right + 1;

    while (true) {
     do {
      i = i + 1;
     } while (list.get(i) < pivot);

     do {
      j = j - 1;
     } while (list.get(j) > pivot);

     if (i >= j) {
      break;
     }
     int temp = list.get(i);
     list.set(i, list.get(j));
     list.set(j, temp);
    }
    stack.push(right);
    right = left > (i - 1) ? left : (i - 1);
   } else {
    if (stack.size() == 0) {
     break;
    }
    left = right + 1;
    right = stack.pop();
   }
  }
 }
}

Links:
Wikipediaeintrag Quicksort
Ausführliche Seite über Quicksort

Quicksort in Java

Hier eine erste Implementierung von Quicksort, allerdings hat diese den Nachteil das ein StackOverflowError rasch erreicht wird:

package at.ande.sorting.quicksort;

import java.util.ArrayList;

public class QuickSort {
 
 ArrayList list;
 
 public ArrayList quickSort(ArrayList arraylist){
  list = arraylist;
  sort(0, arraylist.size() - 1);
  return list;
 }
 
 public void sort(int left, int right){
  if (left < right){
   int divisor = divide(left, right);
   sort (left, divisor - 1);
   sort (divisor + 1, right);
  }
  
 }
 
 public int divide(int left, int right){
  int i = left;
  int j = right -1;
  int pivot = list.get(right);
  
  do{
   while (list.get(i) <= pivot && i < right){
    i = i + 1;
   }
   while (list.get(j) >= pivot && j > left){
    j = j - 1;
   }
   if( i < j){
    int temp = list.get(i);
    list.set(i, list.get(j));
    list.set(j, temp);
   }
   
  } while (i < j );
  
  if(list.get(i) > pivot){
   int temp = list.get(i);
   list.set(i, list.get(right));
   list.set(right, temp);
  }
  return i;
 }
}

Ein Screenshot der Console des bei größeren Listen schnell auftretenden Fehlers:

Implementiert man Quicksort iterativ anstatt rekursiv funkt es auch mit großen Mengen: Iterative Implementierung von Quicksort
Quicksort von ungarischen Folkloretänzern getanzt

Links:
Ausführliche Seite über Quicksort