Algorithmus zum sortieren arbeitet fehlerhaft



  • Guten Abend,
    ich programmiere zurzeit einen Sortieralgorithmus für Arrays.

    Stopwatch sw = new Stopwatch(); //Zeit messen
    
                string[] array = File.ReadAllLines("test.txt"); //Zahlen zum sortieren
                string buffer; //Für Swap
    
                int min; //Kleinster Wert
    
                bool sorted = true; //Angabe ob das Array sortiert ist
                bool result = true; //Angabe ob das Array fehlerfrei sortiert wurde
    
                sw.Start();
    
                //Gesamtes Array durchlaufen
                for (int counter = 0; counter < array.Length; counter++)
                {
                    //min ist der kleinste Wert
                    min = counter;
    
                    //Kleineren Wert finden
                    Parallel.For(counter + 1, array.Length, index =>
                    {
                        //Wenn ein kleinerer Wert gefunden wurde
                        if (Convert.ToInt32(array[index]) < Convert.ToInt32(array[min]))
                        {
                            //Index des neuen kleinsten Wertes speichern
                            min = index;
                        }
                    });
    
                    //Falls der kleinste Wert nicht an der Stelle des aktuellen Indexes liegt
                    if (min != counter)
                    {
                        //Swap
                        buffer = array[counter];
                        array[counter] = array[min];
                        array[min] = buffer;
                    }
                }
    
                //Bubble Sort um Fehler auszubügeln
                do
                {
                    sorted = true;
    
                    //Gesamtes Array durchlaufen
                    for (int index = 0; index < array.Length - 1; index++)
                    {
                        //Wenn ein Fehler gefunden wurde
                        if (Convert.ToInt32(array[index]) > Convert.ToInt32(array[index + 1]))
                        {
                            //Swap
                            buffer = array[index];
                            array[index] = array[index + 1];
                            array[index + 1] = buffer;
    
                            sorted = false;
                        }
                    };
    
                } while (sorted == false);
    
                sw.Stop();
    
                //Ausgabe der Zeit
                Console.WriteLine("Dauer: {0}", sw.Elapsed);
    
                //Verifizieren
                for (int index = 0; index < array.Length - 1; index++)
                {
                    //Falls ein Fehler gefunden wurde
                    if (Convert.ToInt32(array[index]) > Convert.ToInt32(array[index + 1]))
                    {
                        result = false;
    
                        Console.WriteLine("Fehler an Stelle {0}: {1} > {2}", index, array[index], array[index + 1]);
                    }
                }
    
                Console.WriteLine((result) ? "Fehlerfrei sortiert" : "Fehlerhaft sortiert");
    
                Console.ReadKey();
            }
    

    Mein Algorithmus arbeitet ohne Parallel-Schleife fehlerfrei und mit teilweise fehlerhaft (daher nochmal ein Bubble-Sort um Fehler zu korrigieren). Die Korrektur kostet bei meiner Testdatei, die aus 32767 zufällig generierten Zahlen besteht, ca. 10 Sekunden. Ich denke das dadurch das ein falscher Index in der Parallel-Schleife gespeichert wird, das Array ebenfalls falsch sortiert wird. Wie kann ich dieses Problem umgehen, bzw. die Fehlerquote mindern?

    MfG



  • Welchen Sinn soll denn Parallel.For haben? Nimm eine normale for-Schleife und gut ist.

    Ist das eine (Haus-)Aufgabe? Denn sonst würde man einfach Array.Sort() hier benutzen.

    PS: Besser wäre es übrigens, gleich ein Zahlen-Array zu benutzen (anstatt dauernd zu konvertieren - welches evtl. auch eine Exception werfen kann)!


Log in to reply