Programmierung eines SleepSorter

4 Lösungen

#129

Fortgeschrittener - C# von hollst - 09.06.2016 um 15:33 Uhr

Zum Sortieren irgendwelcher Objekte existieren unzählige Algorithmen, immer mit dem Ziel, das Sortieren möglichst schnell hinzubekommen, denn bei großen Datenmengen kann das Sortieren etliche Zeit beanspruchen. Eine recht originelle Art eines Sortierers stellt der sogenannte SleepSorter dar, allerdings ist er in der Regel kaum praxistauglich. Sein Vorteil besteht jedoch darin, dass man von vornherein fast genau weiß, wie lange der Sortiervorgang dauern wird, egal, wie vielen Objekte zu sortieren sind.

So funktioniert der SleepSorter: Jedem zu sortierenden Element wird ein eigener Thread zugeordnet. Nachdem das geschehen ist, werden alle Threads gleichzeitig gestartet. Die Threads haben keine großartige Rechenleistung zu erbringen, im Gegenteil, sie sind sofort in den Schlaf zu versetzen. Wie lange sie zu schlafen haben, muss ihnen bei der Initialisierung mitgegeben werden, und zwar genau so lange, wie es dem Wert des zu sortierenden Elemets entspricht, d. h. eine Zeitdauer dazu proportional. Das ist alles. Die Threads werden nach dem gemeinsamen Schlafengehen in aufsteigender Folge wieder erwachen und man muss dieses Erwachen lediglich sofort abfangen und den dem Thread jeweils zugeordneten Sortierwert z. B. in einer Liste hinterlegen. In dieser Liste sind die Elemente dann in sortierter Folge gespeichert.

Die Programmieraufgabe lautet so: Gegeben sei ein int-Array mit zufällig belegten Feldern, Wertebereich sei 0 ... 99. Die Länge des Arrays sei N (z. B. N = 1000). Das int-Array ist mit einem SleepSorter zu sortieren. Zusätzlich ist nach der Sortierung zu prüfen, ob auch tatsächlich richtig sortiert worden ist. Die Richtigkeit ist beim SleepSorter nämlich nicht garantiert, bspw. wenn zwei Sortierwerte eng beieinander liegen und der SleepSorter nicht von außen völlig abgeschottet ist.

Bitte melden Sie sich an um zur Aufgabenbeschreibung eine Frage zu stellen.

Frage stellen

Bitte melden Sie sich an um eine Lösung einzureichen.

Lösung einreichen

von Mexx (2370 Punkte) - 31.07.2016 um 23:30 Uhr

C#-Code

using System;
using System.Collections.Generic;
using System.Threading;

namespace SleepSorter
{
    class Program
    {
        static int[] testarray = new int[] { 4, 1, 5, 8, 2, 34, 52, 1, 11, 17, 7 , 13, 1, 22, 31, 21, 1};
        static List<int> sortiert = new List<int>();

        static void Main(string[] args)
        {
            //Zu sortierende Einträge anlegen
            List<Sortieren> objects = new List<Sortieren>(testarray.Length);
            foreach (int entry in testarray)
            {
                objects.Add(new Sortieren(entry));
            }

            //Sortierung für jedes objekt starten
            foreach (Sortieren sort in objects)
            {
                sort.Start();
            }

            //Prüfen ob alle Threads ageschlossen sind
            bool running = true;
            while (running)
            {
                int count = 0;
                foreach (Sortieren sort in objects)
                {
                    if (!sort.thr.IsAlive)
                        count++;
                    if (count == testarray.Length)
                        running = false;
                }
            }

            foreach (int i in sortiert)
                Console.Write(i.ToString() + " ");
            Console.ReadKey();
        }

        public static void SaveValue(int value)
        {
            sortiert.Add(value);
        }
    }

    
    class Sortieren
    {
        public Thread thr { get; }
        delegate void GetValue(int value);
        event GetValue getValue;
        int value;

        public Sortieren(int value)
        {
            this.value = value;
            this.getValue += Program.SaveValue;
            this.thr = new Thread(Warten);
        }

        /// <summary>
        /// Thread starten
        /// </summary>
        public void Start()
        {
            this.thr.Start();
        }

        /// <summary>
        /// Entsprechend des Werts den Thread schlafen legen und beim erwachen den Wert per
        /// Delegat zurückgeben
        /// </summary>
        private void Warten()
        {
            Thread.Sleep(value * 50);
            if (getValue != null)
            {
                getValue(value);
            }
        }
    }
}