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 daniel59 (4260 Punkte) - 17.06.2016 um 07:40 Uhr

C#-Code

using System;
using System.Collections.Generic;
using System.Linq;
using System.Threading;
using System.Diagnostics;

namespace ConsoleSleepSorter
{
    class Program
    {
        static List<int> sleepSortedList;
        static Random rnd = new Random();
        static List<Thread> threads;
        static int accuracy;
        static void Main(string[] args)
        {
            Console.Write("Größe der Liste: ");
            int length = Convert.ToInt32(Console.ReadLine());
            Console.Write("Wertebereich untere Grenze: ");
            int from = Convert.ToInt32(Console.ReadLine());
            Console.Write("Wertebereich obere Grenze: ");
            int to = Convert.ToInt32(Console.ReadLine());
            Console.Write("Genauigkeit: ");
            accuracy = Convert.ToInt32(Console.ReadLine());

            List<int> randomList = new List<int>();
            for (int i = 0; i < length; i++)
            {
                randomList.Add(rnd.Next(from, to));
            }

            List<int> sortedList = randomList.OrderBy(x => x).ToList();

            int expectedTime = sortedList.Max() * accuracy;//in ms
            Console.WriteLine("Geschätzte Zeit: " + expectedTime + " ms\n");

            Stopwatch sw = new Stopwatch();
            sw.Start();
            Sort(randomList);
            while (!threads.TrueForAll(a => !a.IsAlive))//Warte solange bis alle Threads abgeschlossen sind
            { }
            int count = 0;
            for (int i = 0; i < sortedList.Count; i++)
            {
                if (sortedList[i] == sleepSortedList[i])
                {
                    Console.ForegroundColor = ConsoleColor.DarkGreen;
                    count++;
                }
                else
                {
                    Console.ForegroundColor = ConsoleColor.DarkRed;
                }
                Console.WriteLine("{0}\t\t---\t\t{1}", sortedList[i], sleepSortedList[i]);
            }
            sw.Stop();
            Console.ForegroundColor = ConsoleColor.White;
            Console.WriteLine("\nGeschätzte Zeit: " + expectedTime + " ms");
            Console.WriteLine("Benötigte Zeit: " + sw.ElapsedMilliseconds + " ms");
            Console.WriteLine("Übereinstimmungen: {0}/{1}", count, sortedList.Count);

            Console.ReadLine();
        }

        static void Sort(IEnumerable<int> source)
        {
            sleepSortedList = new List<int>();
            threads = new List<Thread>();
            foreach (int i in source)
            {
                Thread sortingThread = new Thread(() => Sleep(i * accuracy));
                sortingThread.Start();
                threads.Add(sortingThread);
            }
        }

        static void Sleep(int duration)
        {
            Thread.Sleep(duration);
            lock (sleepSortedList)
            { sleepSortedList.Add(duration / accuracy); }
        }
    }
}