Sortieralgorithmen: Sortierschritte anzeigen (graphisch)

Robert1996

Guten Abend,

ich bin gerade dabei, für den Unterricht ein paar Sortieralgorithmen nachzuvollziehen, und das gelingt auch wunderbar. Ich möchte nun gerne die Schritte anzeigen, zB als Balken, die dann nach und nach in die richtige Reihenfolge gerückt werden. Dazu habe ich eine Funktion, die das Array nach einem Durchgang auf eine Canvas ausgibt

DrawArray(int[] iaArray, Canvas cCanvas)

immer an das eine eines Durchgangs geschrieben, dh sie wird immer aufgerufen, nachdem eine Stufe abgeschlossen ist (zB BubbleSort).

Das Problem ist nun, dass das Array erst ganz am Ende angezeigt wird, also die einzelnen Schritte nicht nachvollziehbar sind. Irgendjemand eine Idee?

Robert

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Windows;
using System.Windows.Controls;
using System.Windows.Data;
using System.Windows.Documents;
using System.Windows.Input;
using System.Windows.Media;
using System.Windows.Media.Imaging;
using System.Windows.Navigation;
using System.Windows.Shapes;

namespace BubbleSortGraphical
{
    /// <summary>
    /// Interaktionslogik für MainWindow.xaml
    /// </summary>
    public partial class MainWindow : Window
    {
        static Random rRandom = new Random();

        int iElements = 10;
        int iMax = 100;

        int[] iaArray;

        public MainWindow()
        {
            InitializeComponent();

            //initialise the varialbles
            iaArray = new int[iElements];
        }

        //bubble sort algorithm 
        void BubbleSort(int[] iaArray, int iLength)
        {
            int temp;

            for (int i = iLength; i >= 0; i--)
            {
                for (int j = 0; j < iLength - 1; j++)
                {
                    if(iaArray[j] > iaArray[j + 1])
                    {
                        temp = iaArray[j];
                        iaArray[j] = iaArray[j + 1];
                        iaArray[j + 1] = temp;
                    }

                    System.Threading.Thread.Sleep(100);
                    DrawArray(iaArray, cCanvas);
                    System.Threading.Thread.Sleep(400);
                }
            }
        }

        public void DrawArray(int[] iaFeld, Canvas myCanvas)
        {
            myCanvas.Children.Clear();

            for (int i = 0; i < iaFeld.Length; i++)
            {
                Rectangle Balken = new Rectangle();
                Balken.Height = ((double)iaFeld[i] / 999) * myCanvas.Height;
                Balken.Width = myCanvas.Width / iaFeld.Length;
                Balken.Fill = Brushes.DarkRed;
                Canvas.SetLeft(Balken, 0 + i * Balken.Width);
                Canvas.SetBottom(Balken, 0);
                myCanvas.Children.Add(Balken);
            }
        }

        private void Window_KeyDown(object sender, KeyEventArgs e)
        {
            if (e.Key == Key.N)
            {
                for (int i = 0; i < iElements; i++)
                {
                    iaArray[i] = rRandom.Next(0, iMax+1);
                }
            }

            if (e.Key == Key.S)
            {
                BubbleSort(iaArray, iElements);
            }

            if (e.Key == Key.X)
            {
                this.Close();
            }
        }
    }
}

Robert1996 schrieb:

Das Problem ist nun, dass das Array erst ganz am Ende angezeigt wird, also die einzelnen Schritte nicht nachvollziehbar sind. Irgendjemand eine Idee?

Die langlaufende BubbleSort-Methode wird im GUI-Thread ausgeführt und blockiert ihn für jedes Neuzeichnen.

3 Vorschläge was Du dagegen tun kannst:
-Neuzeichnen erzwingen nach jedem Schritt, was nichts daran ändert dass das Fenster blockiert wird.
-Die Methode in einem eigenen Thread ausführen und nur das Zeichnen an den GUI-Thread delegieren
-Die Methode so ändern, dass sie nur einen Sortierschritt ausführt. Dann z.b. bei jedem Tastendruck oder per Timer immer wieder aufrufen und das Array sortieren lassen.

volkard

µ schrieb:

3 Vorschläge was Du dagegen tun kannst:
-Neuzeichnen erzwingen nach jedem Schritt, was nichts daran ändert dass das Fenster blockiert wird.
-Die Methode in einem eigenen Thread ausführen und nur das Zeichnen an den GUI-Thread delegieren
-Die Methode so ändern, dass sie nur einen Sortierschritt ausführt. Dann z.b. bei jedem Tastendruck oder per Timer immer wieder aufrufen und das Array sortieren lassen.

Da ist wohl nur der 3. Vorschlag befriedigend, was das Ergebnis angeht. Allerdings ist der Aufwand, Algos so zu zerhacken, bisweilen schlimm. Beliebtes Thema für Bachelor-Arbeiten (vorzugsweise in Java, löl). Ich würde vorher sortieren und in eine Datei(oder System.Collections.Generic.List<MeinIntegerPaar>) mitschreiben und zum Schrittweise-Anzeigen sie wieder auslesen.

Robert1996

Ich finde den 2. Vorschlag eigentlich ganz gut, nur weiß ich nicht so recht, wie ich das umzusetzen habe. Den Algorithmus möchte ich ja wirklich ungern zerteilen, dann lieber mit Sleeps das ganze verlangsamen...

@Robert1996
Schonmal was mit Threading gemacht? Wie man einen Thread startet kannst Du schnell googlen. Wichtig ist nur, dass keine GUI-Elemente außerhalb des GUI-Threads manipuliert werden dürfen. Ein Wechsel von einem anderen Thread in den GUI-Thread kriest Du in WPF so hin:

this.Dispatcher.BeginInvoke(
(Action)delegate()
{
 //Hier die Balken malen
});

volkard schrieb:

Da ist wohl nur der 3. Vorschlag befriedigend, was das Ergebnis angeht. Allerdings ist der Aufwand, Algos so zu zerhacken, bisweilen schlimm. Beliebtes Thema für Bachelor-Arbeiten (vorzugsweise in Java, löl). Ich würde vorher sortieren und in eine Datei(oder System.Collections.Generic.List<MeinIntegerPaar>) mitschreiben und zum Schrittweise-Anzeigen sie wieder auslesen.

Ich würde da mit yield return rangehen und den Enumerator im Timer-Eventhandler einfach jeweils einen Schritt weiter setzen. Der Compiler generiert die ganze komplexe Statemachine hinter yield-return-Konstrukten automatisch

Robert1996

Und das schreibe ich also in die BubbleSort-Schleife? Quasi da, wo noch die DrawArray-Funktion steht?

philipp2100

volkard schrieb:

Allerdings ist der Aufwand, Algos so zu zerhacken, bisweilen schlimm.

Stimmt wohl, aber müsste man in diesem Fall nicht nur die Methode mit einem Rückgbewert versehen, der das dekrementierte i zurückgibt und so oft mit diesem wieder aufrufen, bis -1 zurückgegeben wird?

volkard

philipp2100 schrieb:

volkard schrieb:

Allerdings ist der Aufwand, Algos so zu zerhacken, bisweilen schlimm.

Stimmt wohl, aber müsste man in diesem Fall nicht nur die Methode mit einem Rückgbewert versehen, der das dekrementierte i zurückgibt und so oft mit diesem wieder aufrufen, bis -1 zurückgegeben wird?

Ja, geht. Aber da macht mir die Laufzeit Angst.
yield return klingt prächtig. (Hoffe, das ist nicht so implementiert.)

Robert1996 schrieb:

Und das schreibe ich also in die BubbleSort-Schleife? Quasi da, wo noch die DrawArray-Funktion steht?

Hier eine yield-return Variante mit Timer. Du kannst das aber auch umbauen, dass ein Schritt bei einem Buttonclick durchgeführt wird oder wie Du eben möchtest.
Statt die List in der Console auszugeben malst Du eben Deine Balken.
Vorsicht: Der Hier verwendete Timer läuft in einem eigenen Thread, wollte auf die Schnelle nur ein Konsoleprogramm schreiben. Wenn Du einen WPF-Timer verwendest, musst Du Dich nicht darum kümmern, die Zeichenfunktionen an den GUI-Thread zu delegieren.

using System;
using System.Collections.Generic;
using System.Linq;

namespace Stepsort
{
    class Program
    {
        static void Main(string[] args)
        {
            Sort sort = new Sort();
            Console.ReadKey(true);
        }

        class Sort
        {
            System.Threading.Timer timer;
            IEnumerator<List<int>> enumerator;

            public Sort()
            {
                Random rand = new Random(Environment.TickCount);
                List<int> list = Enumerable.Range(0, 10).Select(i => rand.Next(100)).ToList();
                enumerator = BubbleSort(list).GetEnumerator();
                timer = new System.Threading.Timer(new System.Threading.TimerCallback(tick), null, 0, 1000);
            }

            void tick(object o)
            {
                if (enumerator.MoveNext())
                {
                    var list = enumerator.Current;
                    foreach (var item in list)
                        Console.Write(item + " ");
                    Console.WriteLine();
                }
            }

            IEnumerable<List<int>> BubbleSort(List<int> list)
            {
                for (int i = list.Count; i >= 0; i--)
                {
                    for (int j = 0; j < list.Count - 1; j++)
                    {
                        if (list[j] > list[j + 1])
                        {
                            int temp = list[j];
                            list[j] = list[j + 1];
                            list[j + 1] = temp;

                            yield return list;
                        }
                    }
                }
            }
        }
    }
}

Robert1996

Ich will ganz ehrlich sein, ich verstehe den Code nicht. Aber das mit den Threads nochmal aufgreifend; Ich brauche doch bestimmt 2 Threads, einem lasse ich den BubbleSort ausführen, und während ich den BubbleSort ausführe, lasse ich parallel dazu permanent das Array zeichen..oder geht das dann nicht, wenn beide auf das selbe Array zugreifen?

Edit: Folgendermaßen sieht es jetzt aus, das Resultat ist, dass garnichts mehr angezeigt wird:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Windows;
using System.Windows.Controls;
using System.Windows.Data;
using System.Windows.Documents;
using System.Windows.Input;
using System.Windows.Media;
using System.Windows.Media.Imaging;
using System.Windows.Navigation;
using System.Windows.Shapes;
using System.Threading;

namespace BubbleSortGraphical
{
    /// <summary>
    /// Interaktionslogik für MainWindow.xaml
    /// </summary>
    public partial class MainWindow : Window
    {
        static Random oRandom = new Random();

        int iElements = 10;
        int iMax = 100;

        List<int> ilList;

        public MainWindow()
        {
            InitializeComponent();

            ilList = Enumerable.Range(0, iElements).Select(x => oRandom.Next(0, iMax + 1)).ToList();
        }

        void BubbleSort(List<int> ilList)
        {
            int temp;

            for (int i = ilList.Count; i >= 0; i--)
            {
                for (int j = 0; j < ilList.Count - 1; j++)
                {
                    if (ilList[j] > ilList[j + 1])
                    {
                        temp = ilList[j];
                        ilList[j] = ilList[j + 1];
                        ilList[j] = temp;
                    }

                    this.Dispatcher.BeginInvoke((Action)delegate() { DrawList(ilList, oCanvas); });
                }
            }
        }

        public void DrawList(List<int> ilList, Canvas myCanvas)
        {
            myCanvas.Children.Clear();

            for (int i = 0; i < iElements; i++)
            {
                Rectangle Balken = new Rectangle();
                Balken.Height = ((double)ilList[i] / iMax) * myCanvas.Height;
                Balken.Width = myCanvas.Width / iElements;
                Balken.Fill = Brushes.DarkRed;
                Canvas.SetLeft(Balken, 0 + i * Balken.Width);
                Canvas.SetBottom(Balken, 0);
                myCanvas.Children.Add(Balken);
            }
        }

        private void Window_KeyDown(object sender, KeyEventArgs e)
        {
            if (e.Key == Key.S)
            {
                new Thread(() => BubbleSort(ilList)).Start();
            }

            if (e.Key == Key.X)
            {
                this.Close();
            }
        }
    }
}

Robert1996 schrieb:

Ich will ganz ehrlich sein, ich verstehe den Code nicht.

Woran liegts? Es ist imho die sauberste Variante also würde ich vorschlagen, gehen wir den Code mal durch wenn Du Verständnisprobleme hast.

Robert1996 schrieb:

Aber das mit den Threads nochmal aufgreifend; Ich brauche doch bestimmt 2 Threads, einem lasse ich den BubbleSort ausführen, und während ich den BubbleSort ausführe, lasse ich parallel dazu permanent das Array zeichen..oder geht das dann nicht, wenn beide auf das selbe Array zugreifen?

Zwei Threads ja. Aber einer ist der GUI-Thread, den Du nicht extra erstellen musst. Der andere ist nur für das Sortieren und warten zuständig. Allgemein: Gleichzeitig auf ein Objekt Zugreifen ist Heikel und muss synchronisiert werden.