Heapsort in Java

Hier eine Implementierung von Heapsort in Java:

package at.ande.sorting.heapsort;

import java.util.ArrayList;

public class HeapSort {
 
 ArrayList list;
 int length;
 
 public ArrayList start(ArrayList arraylist){
  list = arraylist;
  length = list.size();
  createHeap();
  while(length > 1){
   length--;
   change(0, length);
   downheap(0);
  }
  return list;
 }
 
 public void createHeap(){
  for (int i = length / 2 - 1; i >= 0; i--){
   downheap(i);
  }
 }
 
 public void downheap(int i){
  int j = 2 * i + 1;
  while (j < length){
   if(j + 1 < length && list.get(j + 1) > list.get(j)){
    j++;
   }
   if(list.get(i) > list.get(j)){
    break;
   }
   change(i, j);
   i = j;
   j = 2 * i + 1;
  }
 }
 
 public void change(int i, int j){
  int temp = list.get(i);
  list.set(i, list.get(j));
  list.set(j, temp);
 }
}

Im Vergleich zu den auch in diesem Blog implementieren Sortieralgorithmen schneidet Heapsort ganz gut ab:

List Area: 0 - 999
List Numbers: 100000
Unsorted List:
- Iterative Quicksort: 123 ms
- Bubblesort: 45787 ms
- Gnomesort: 75418 ms
- Heapsort: 103 ms
Sorted List:
- Iterative Quicksort: 1518 ms
- Bubblesort: 5 ms
- Gnomesort: 8 ms
- Heapsort: 49 ms

Links:
Wikipediaeintrag über Heapsort
Ausführlicher Artikel der Uni Flensburg über Heapsort

Gnomesort in Java

Hier eine Implementierung von Gnomesort:

package at.ande.sorting.gnomesort;

import java.util.ArrayList;

public class GnomeSort {
 
 ArrayList list;

 public ArrayList start(ArrayList arraylist) {
  list = arraylist;
  sort();
  return list;
 }
 
 public void sort(){
  int right = 1;
  int left = 0;
  while (right != list.size()){
   if (list.get(left) <= list.get(right)){
    right = right + 1;
    left = left + 1;
   } else {
    int temp = list.get(left);
    list.set(left, list.get(right));
    list.set(right, temp);
    if(left != 0){
     left = left -1;
     right = right - 1;
    }
   }
  }
 }
}

Das Laufzeitverhalten ist nicht gerade überzeugend:

List Area: 0 - 999
List Numbers: 100000
Unsorted List:
-Iterative Quicksort: 135 ms
-Bubblesort: 43729 ms
-GnomeSort: 70638 ms
Sorted List:
-Iterative Quicksort: 1767 ms
-Bubblesort: 3 ms
-GnomeSort: 12 ms

Links:
Wikiartikel zu Gnomesort

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

Bubblesort in Java

In nächster Zeit möchte ich als Fingerübung verschiedene Sortieralgorithmen in Java implementieren und dann verschiedene Messungen durchführen, begonnen habe ich mal mit Bubblesort, die ArrayList ist mit Integer befüllt, die Generics mußte ich rausnehmen da die Codedarstellung sonst nicht funzt.

package at.ande.sorting.bubblesort;

import java.util.ArrayList;

public class BubbleSort {

 public ArrayList sort(ArrayList list) {
  int listSize = list.size();
  boolean changed;
  do {
   changed = false;
   for (int i = 0; i < listSize - 1; i++) {
    Integer first = list.get(i);
    Integer second = list.get(i + 1);
    if (first > second) {
     list.set(i, second);
     list.set(i + 1, first);
     changed = true;
    }
   }
   listSize = listSize - 1;
  } while (changed && listSize > 1);
  
  return list;
 }
}

Links: Ausführliche Seite über Bubblesort
Bubblesort von ungarischen Folkloretänzern getanzt