import java.applet.*;
import java.awt.*;
import java.awt.event.*;

public class sort extends Applet
{
    int sx=600; int sy=400;
    int x=0;int y=0;
    Graphics g;
    TextField tf;
	Choice tempo;
    Color hgrund,fuell;
    int a[] = new int[100];
    int a2[] = new int[100];
    int zaehler=0;

    public void init() {
        g=this.getGraphics();


        Button b_bubble = new Button ("Bubblesort");
        add(b_bubble);
        b_bubble.addMouseListener(
            new MouseAdapter(){
                public void mouseClicked(MouseEvent e){
                    bubble(g);
                }
            }
        );

        Button b_select = new Button ("Selection Sort");
        add(b_select);
        b_select.addMouseListener(
            new MouseAdapter(){
                public void mouseClicked(MouseEvent e){
                    selection(g);
                }
            }
        );

        Button b_insert = new Button ("Insertion Sort");
        add(b_insert);
        b_insert.addMouseListener(
            new MouseAdapter(){
                public void mouseClicked(MouseEvent e){
                    insertion(g);
                }
            }
        );

        Button b_quick = new Button ("QuickSort");
        add(b_quick);
        b_quick.addMouseListener(
            new MouseAdapter(){
                public void mouseClicked(MouseEvent e){
                    quick(g);
                }
            }
        );
    
        Button b_heap = new Button ("HeapSort");
        add(b_heap);
        b_heap.addMouseListener(
            new MouseAdapter(){
                public void mouseClicked(MouseEvent e){
                    heap(g);
                }
            }
        );

        Button b_shell = new Button ("ShellSort");
        add(b_shell);
        b_shell.addMouseListener(
            new MouseAdapter(){
                public void mouseClicked(MouseEvent e){
                    shell(g);
                }
            }
        );

        Button b_merge = new Button ("MergeSort");
        add(b_merge);
        b_merge.addMouseListener(
            new MouseAdapter(){
                public void mouseClicked(MouseEvent e){
                    merge(g);
                }
            }
        );

        Button b_buheap = new Button ("BottomUpHeapSort");
        add(b_buheap);
        b_buheap.addMouseListener(
            new MouseAdapter(){
                public void mouseClicked(MouseEvent e){
                    buheap(g);
                }
            }
        );

        tf = new TextField();
        tf.setColumns(20);
        tf.setText("Anzahl Vergleiche");
        add(tf);

        Label l1=new Label("Anzeige");
        add(l1);

        tempo = new Choice();
        tempo.addItem("langsam");
        tempo.addItem("normal");
		tempo.addItem("schnell");
		tempo.addItem("sehr schnell");
        add(tempo);

    }

    public void bubble(Graphics g){
        int anz;
        hgrund = new Color (255,255,255);
        fuell = new Color (0,255,0);
        int j; int h; int zaehler=0;
        tf.setText(zaehler+" Vergleiche");
        int oben=a.length;
        starten(g);
        for (j=oben-1;j>0;j--) {
            for (int k=0;k<j;k++) {
                zaehler=++zaehler;
                if (a[k]>a[k+1]) {
                    h=a[k];
                    a[k]=a[k+1];
                    a[k+1]=h;
                }
                anzeige(g,k);
                anzeige(g,k+1);
            }
        }
        tf.setText(zaehler+" Vergleiche");
    }


    public void selection(Graphics g){
        int anz;
        hgrund = new Color (255,255,255);
        fuell = new Color (0,255,0);
        int h; int zaehler=0;
        tf.setText(zaehler+" Vergleiche");
        int oben=a.length;
        starten(g);
        for (int j=0;j<oben-1;j++) {
            for (int k=j;k<=oben-1;k++) {
                zaehler=++zaehler;
                if (a[j]>a[k]) {
                    h=a[j];
                    a[j]=a[k];
                    a[k]=h;
                }
                anzeige(g,k);
                anzeige(g,j);
            }
        }
        tf.setText(zaehler+" Vergleiche");
    }

    public void insertion(Graphics g){
        int anz; int k;
        hgrund = new Color (255,255,255);
        fuell = new Color (0,255,0);
        int h; int zaehler=0;
        tf.setText(zaehler+" Vergleiche");
        int oben=a.length;
        starten(g);
        for (int j=1;j<=oben-1;j++) {
            k=j;
            while (j>0 && a[j-1]>a[j]) {
                zaehler=++zaehler;
                h=a[j];
                a[j]=a[j-1];
                a[j-1]=h;
                anzeige(g,j-1);
                anzeige(g,j);
                j=--j;
            }
        }
        tf.setText(zaehler+" Vergleiche");
    }

    public void quick(Graphics g){
        int anz; int k;
        hgrund = new Color (255,255,255);
        fuell = new Color (0,255,0);
        int h; zaehler=0;
        tf.setText(zaehler+" Vergleiche");
        int oben=a.length;
        starten(g);
        quicksort(g,0,oben-1);
        tf.setText(zaehler+" Vergleiche");
    }

    public void quicksort(Graphics g, int l, int r) {
        int m;
        int u=l;
        int o=r; int wert;
        int h;
        if ((r-l)>=1) {
            m= (int) ((r+l)/2); 
            wert=a[m];
            while (u<o) {
                while (a[u]<wert) {
                    anzeige(g,u);
                    zaehler=++zaehler;
                    u=++u;
                }
                while (a[o]>wert){
                    anzeige(g,o);zaehler=++zaehler;
                    o=--o;
                }
                if (a[u] > a[o]) {
                    h=a[u]; a[u]=a[o]; a[o]=h;
                    anzeige(g,u);anzeige(g,o);zaehler=++zaehler;
                    if (u==m) m=o;
                    else {
                        if (o==m) m=u;
                    };
                    wert=a[m];
                }
                if (u!=m) u=++u;
                if (o!=m) o=--o;
            }
            quicksort(g,l,m-1);
            quicksort(g,m+1,r);
        }
    }

    public void heap(Graphics g) {
        int anz; int k;
        hgrund = new Color (255,255,255);
        fuell = new Color (0,255,0);
        int h; zaehler=0;
        tf.setText(zaehler+" Vergleiche");
        int oben=a.length;
        starten(g);
        aufbauen(g,oben-1);
        heapsort(g,oben-1);
        tf.setText(zaehler+" Vergleiche");
    }

    public void aufbauen(Graphics g,int r) {
        int i;
        int j1,j2,h;
        for (i=1;i<=r;++i) {
            j1=i;
            j2 = (int) (i / 2);
            while (a[j1]>a[j2]) {
                zaehler=++zaehler;
                h=a[j1]; a[j1]=a[j2]; a[j2]=h;
                anzeige(g,j1);
                anzeige(g,j2);
                if (j2==0) break;
                j1 = j2;
                j2 =(int) (j2 / 2);
            }
        }
    }

    public void heapsort(Graphics g,int r) {
        int i,j;
        int k1,k2;
        int maxim, stelle,h;
        for (i=r;i>0;--i) {
            h=a[0]; a[0]=a[i]; a[i]=h; j=0;
            anzeige(g,0);anzeige(g,i);
            while (true) {
                k1 = 2 * j;
                k2 = k1 + 1;
                if (k1 < i) {
                    maxim = a[k1];
                    stelle = k1;}
                else break;
                zaehler=++zaehler;
                if (k2 < i) {
                    if (a[k2] > maxim) {
                        maxim = a[k2];
                        stelle = k2;
                    }
                }    
                zaehler=++zaehler;
                if (a[j] < maxim) {
                    h = a[j]; a[j] = a[stelle]; a[stelle] = h;
                    anzeige(g,j);anzeige(g,stelle);
                    j = stelle;}
                else break;
            }
        }
    }

    public void shell(Graphics g) {
        int anz; int k;
        int i,j,incr; int h; int zaehler=0;
        hgrund = new Color (255,255,255);
        fuell = new Color (0,255,0);
        tf.setText(zaehler+" Vergleiche");
        int oben=a.length;
        starten(g);
        incr = (int) (100 / 2);
        while (incr > 0) {
            for (i = incr;i<100;i++) {
                j = i - incr;
                while (j > -1) {
                    zaehler=++zaehler;
                    if (a[j] > a[j + incr]) {
                        h = a[j + incr];
                        a[j + incr] = a[j];
                        a[j] = h;
                        anzeige(g,j);
                        anzeige(g,j+incr);
                        j = j - incr;}
                    else j = -1;
                }
            }
            incr = (int) (incr / 2);
        }
        tf.setText(zaehler+" Vergleiche");
    }

    public void merge(Graphics g) {
        int anz; int k;
        int i,j,incr; int h;
        hgrund = new Color (255,255,255);
        fuell = new Color (0,255,0);
        tf.setText(zaehler+" Vergleiche");
        int oben=a.length;
        zaehler=0;
        starten(g);
        m(g,1,oben);
        tf.setText(zaehler+" Vergleiche");
    }

    public void m(Graphics g,int anz,int oben) {
        int i,j,k,l,j1,j2;
        for (i = 0; i<=oben-1; i++) {
            a2[i] = a[i];
        }    
        k = 0;
        for (i = 0; i<oben-1; i=i+anz*2) {
            j1 = i; j2 = i + anz;
            for (l = 1; l<=anz * 2; l++) {
                if (k > oben-1) break;
                else {
                    if ((j1 == i + anz) || (j1 > oben-1)) {
                        a[k] = a2[j2];anzeige(g,k);k = k + 1;j2 = j2 + 1;}
                    else {
                        if ((j2 == i + 2 * anz) || (j2 > oben-1)) {
                            a[k] = a2[j1];anzeige(g,k);k = k + 1;j1 = j1 + 1;}
                        else {
                            zaehler=++zaehler;
                            if (a2[j1] < a2[j2]) {
                                a[k] = a2[j1];anzeige(g,k);j1 = j1 + 1;k = k + 1;}
                            else {
                                a[k] = a2[j2];anzeige(g,k);j2 = j2 + 1;k = k + 1;
                            }
                        }
                    }
                }
            }
        }
        if (anz*2 < oben-1) m(g,anz*2,oben);
    }

    public void buheap(Graphics g) {
        hgrund = new Color (255,255,255);
        fuell = new Color (0,255,0);
        zaehler=0;
        tf.setText(zaehler+" Vergleiche");
        int j; int h;
        int oben=a.length;
        starten(g);
        buheapstart(g,oben-1);
        tf.setText(zaehler+" Vergleiche");
    }

    public void buheapstart(Graphics g, int r) {
        buaufbauen(g,r);
        buheapsort(g,r);
    }

    public void buaufbauen(Graphics g, int r) {
        int i;
        int j1,j2,h;
        for (i=1;i<=r;++i) {
            j1=i;
            j2 = (int) ((i-1) / 2);
            while (a[j1]>a[j2]) {
                zaehler=++zaehler;
                h=a[j1]; a[j1]=a[j2]; a[j2]=h;
                anzeige(g,j1);anzeige(g,j2);
                if (j2==0) break;
                j1 = j2;
                j2 =(int) ((j2-1) / 2);
            }
        }
    }

    public void buheapsort(Graphics g, int r) {
        int i,j;
        int k1,k2,h1,h2;
        int maxim, stelle,h;
        for (i=r;i>0;--i) {
            h=a[0]; a[0]=a[i]; a[i]=h; j=0; 
            anzeige(g,0);anzeige(g,i);stelle=j;
            while (true) {
                k1 = 2 * stelle+1; k2 = k1 + 1;
                if (k1 < i) {
                    maxim = a[k1]; stelle = k1;}
                else break;
                if (k2 < i) {
                    zaehler=++zaehler;
                    if (a[k2] > maxim) {
                        maxim = a[k2]; stelle = k2;
                    }
                }
            }
            while (true) {
                zaehler=++zaehler;
                if ((a[0] > a[stelle]) && (stelle > 0)) 
                    stelle = (int) ((stelle-1) / 2);
                else break;
            }
            if (stelle > 0) {
                h1 = a[stelle]; a[stelle] = a[0];
                anzeige(g,stelle);
                while (true) {
                    stelle = (int) ((stelle-1) / 2);
                    h2 = a[stelle]; a[stelle] = h1; 
                    anzeige(g,stelle);h1 = h2;
                    if (stelle == 0) break;
                }   
            };
        }
    }
                        
    public void anzeige(Graphics g,int k){
		String anzeige=tempo.getSelectedItem();
		long temp=0;
		if (anzeige.equals("langsam")) temp=7;
		if (anzeige.equals("normal")) temp=5;
		if (anzeige.equals("schnell")) temp=3;
		if (anzeige.equals("sehr schnell")) temp=0;
        temp=(long) Math.pow(10,temp);
        for (int i=0;i<temp ;i++ ){}
        g.setColor(hgrund);
        g.fillRect(k*sx/100,0,sx/100,sy);
        fuell = new Color 
            (Math.max((100-a[k]-50)*2,0)*255/100,
            Math.max(100-Math.abs(2*a[k]-100),0)*255/100,
            Math.max((a[k]-50)*2,0)*255/100);
        g.setColor(fuell);
        g.fillRect(k*sx/100,sy-a[k]*sy/100,sx/100,a[k]*sy/100);
    }

    public void starten(Graphics g){
        int oben=a.length;
        for (int j=0;j<=oben-1;j++) { 
            a[j]=(int) (Math.random()*100);
        }
        for (int k=0;k<=oben-1 ;k++ ){
            anzeige(g,k);
        }
        
    }

}