Pberndt V4

Direkt zum Inhalt springen


Quellcode Quicksort.java

Beschreibung

Um den Quicksortalgorithmus besser verstehen zu können, habe ich (bzw. sollte ich) ein Javaprogramm schreiben, das den Sortiervorgang darstellt. Diese Version stellt den Vorgang dabei als Histogramm dar.

Sourcecode

/**
* Quicksort
*
* Visualisierung des Algorithmus
* Phillip Berndt
*
*/

import javax.swing.*;
import java.awt.*;
import java.awt.image.*;

public class Quicksort extends JFrame
{
    int[] zahlen;
   
    public static void main(String arg[])
    {
        new Quicksort();
    }
   
    public Quicksort()
    {
        // Form initialisieren
        super("Quicksort Demo");
        setSize(400, 300);
        setDefaultCloseOperation(EXIT_ON_CLOSE);
        setBackground(Color.white);
       
        // Zufllige Zahlen speichern
        zahlen = new int[15];
        for(int i=0; i<15; i++)
            zahlen[i] = (int)Math.round(Math.random() * 30);
       
        // Zeichnen
        show();
       
        // Sortieren
        quickSort(zahlen);
    }
   
    public void paint(Graphics gra)
    {
        // Zahlen zeichnen
        gra.setColor(Color.white);
        gra.fillRect(0, 0, getWidth(), getHeight());
        int width  = (int)(getWidth() / 16);
        int left  = 0;
        int top    = getHeight() - 20;
        int height = (int)((getHeight() - 40) / 30);
       
        gra.setColor(Color.red);
        for(int i=0; i<15; i++)
        {
            left += width;
            gra.fill3DRect(left, top - height * zahlen[i], 10, height * zahlen[i], true);
        }
    }
   
    private void swapDraw(int[] Array, int swap1, int swap2, int pivot, int leftBorder, int rightBorder)
    {
        swap(Array, swap1, swap2);
       
        // Animiert zeichnen, dabei Buffer verwenden
        BufferedImage newGraph = ((Graphics2D)getGraphics()).getDeviceConfiguration().createCompatibleImage(
            getWidth(), getHeight(), Transparency.TRANSLUCENT);
        Graphics gra = newGraph.getGraphics();
        gra.setColor(Color.white);
        gra.fillRect(0, 0, getWidth(), getHeight());
       
        int width  = (int)(getWidth() / 16);
        int left  = 0;
        int top    = getHeight() - 20;
        int height = (int)((getHeight() - 40) / 30);
       
       
        for(int i=0; i<15; i++)
        {
            if(i != pivot)
                gra.setColor(Color.red);
            else
                gra.setColor(Color.green);
            if(i == swap1 || i == swap2)
                gra.setColor(gra.getColor().brighter().brighter().brighter());
           
            left += width;
            gra.fill3DRect(left, top - height * zahlen[i], 10, height * zahlen[i], true);
           
            gra.setColor(Color.black);
           
            if(i == leftBorder)
                gra.fillRect(left, top - height * zahlen[i], 3, height * zahlen[i]);
            else if(i == rightBorder)
                gra.fillRect(left + 10 - 3, top - height * zahlen[i], 3, height * zahlen[i]);
        }
       
        getGraphics().drawImage(newGraph, 0, 0, this);
       
        try { Thread.sleep(300); } catch(Exception e) { }
    }
   
    /** Wichtige Funktionen fr Quicksort */
    private void swap(int[] Array, int i, int j)
    {
        int tmp = Array[i];
        Array[i] = Array[j];
        Array[j] = tmp;
    }
   
    /** Ab hier das eigentliche Quicksort */
    public void quickSort(int[] Array)
    {
        _quickSort(Array, 0, Array.length - 1);
    }
   
    private void _quickSort(int[] Array, int left, int right)
    {
        if(right > left)
        {
            int index = left + (int)((right - left) / 2);
            int pivot = Array[index];
           
            // swap(Array, index, right)
            swapDraw(Array, index, right, index, left, right);
            index = left;
            for(int i = index; i < right; ++i)
            {
                if(Array[i] < pivot)
                    // swap(Array, index++, i)
                    swapDraw(Array, index++, i, index, left, right);
            }
            // swap(Array, index, right)
            swapDraw(Array, index, right, index, left, right);
           
            _quickSort(Array, left, index);
            _quickSort(Array, index + 1, right);
        }
    }
}

Download

Dateiname
Quicksort.java
Größe
3.18kb