Pberndt V4

Direkt zum Inhalt springen


Quellcode Matrix-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 in einem zweidimensionalen Koordinatensystem dar.

Sourcecode

/**
* Quicksort
*
* Alternative 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 (Alternative Darstellung)");
        setSize(500, 500);
        setDefaultCloseOperation(EXIT_ON_CLOSE);
        setBackground(Color.white);

        // Zufllige Zahlen speichern
        zahlen = new int[250];
        for(int i=1; i<=250; i++)
        {
            int pos = 0;
            while(zahlen[pos] != 0)
                pos = (int)Math.round(Math.random() * 249);
            zahlen[pos] = i;
        }

        // Zeichnen
        show();

        // Sortieren
        quickSort(zahlen);
    }

    public void paint(Graphics gra)
    {
        // Wei fllen
        gra.setColor(Color.white);
        gra.fillRect(0, 0, getWidth(), getHeight());

        // Punkte zeichnen
        gra.setColor(Color.red);
        for(int i=0; i<250; i++)
            gra.drawRect(zahlen[i] * 2, i * 2, 2, 2);
    }

    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());


        for(int i=0; i<250; i++)
        {
            if(i == pivot)
            {
                gra.fillRect(zahlen[i] * 2, i * 2, 3, 3);
                gra.setColor(Color.green);
            }
            else if(i == swap1 || i == swap2)
            {
                gra.setColor(Color.blue);
                gra.fillRect(zahlen[i] * 2, i * 2, 3, 3);
            }
            else if(i == leftBorder || i == rightBorder)
            {
                gra.setColor(Color.black);
                gra.fillRect(zahlen[i] * 2, i * 2, 3, 3);
            }
            else
            {
                gra.setColor(Color.red);
                gra.drawRect(zahlen[i] * 2, i * 2, 2, 2);
            }
        }

        getGraphics().drawImage(newGraph, 0, 0, this);
    }

    /** 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
Matrix-Quicksort.java
Größe
2.81kb