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

Facebook Plugin für Blogger

Auf dieser Seite kann man sich html generieren lassen, das dann einfach in den in die Vorlage einfügt:

Links:
Blogeintrag Facebook Plugin

Nachtrag 24.5.2011: Wie sich nun herausstellt spioniert Facebook mit dem Likebutton die User aus, ist also auf eine Seite ein "Like It" Button und man gleichzeitig in Facebook eingeloggt schneidet Facebook das mit, sprich Facebook weiß über deinen Account welche Seiten du besuchst. Dafür brauchst du den Button nicht benutzen, technisch kriegt es Facebook auch mit wenn der Button nur vorhanden ist. Aus diesem Grund hab ich den Button wieder aus dem Blog entfernt, man will ja seine Leser nicht an Facebook ausliefern.

Links:
Chipartikel zu diesem Thema

Sozialversicherungsnummer überprüfen

Eine österreichische Sozialversicherungsnummer auf Gültigkeit zu überprüfen ist einfach, man multipliziert jede der 10 Stellen mit einer Ziffer, nimmt das ganze Modulo 11 und vergleicht die vierte Zahl der Nummer damit, hier mal ein Javacodeschnipsel:

 public static boolean checkSozialversicherungsnummer(String nr) {
  int checksum = 0;

  if (nr.length() != 10)
   return false;

  try {
   checksum += Character.getNumericValue(nr.charAt(0)) * 3;
   checksum += Character.getNumericValue(nr.charAt(1)) * 7;
   checksum += Character.getNumericValue(nr.charAt(2)) * 9;
   checksum += Character.getNumericValue(nr.charAt(4)) * 5;
   checksum += Character.getNumericValue(nr.charAt(5)) * 8;
   checksum += Character.getNumericValue(nr.charAt(6)) * 4;
   checksum += Character.getNumericValue(nr.charAt(7)) * 2;
   checksum += Character.getNumericValue(nr.charAt(8)) * 1;
   checksum += Character.getNumericValue(nr.charAt(9)) * 6;

   checksum = checksum % 11;

   return (Character.getNumericValue(nr.charAt(3)) == checksum);

  } catch (NumberFormatException ex) {
   return false;
  }
 }