2016-06-11 10 views
1

Eigentlich habe ich mit CodeAbbey Problem zu tun, also will ich nicht als Code antworten, aber Erklärung darüber, was ich falsch mache.Auswahl Sortierung Problem mit Indizes

Meine Auswahl Sort funktioniert eigentlich ohne Probleme, aber ich weiß nicht, warum ich nicht richtige Indizes (wenn Sortierung funktioniert!). I.e. für Eingabedaten: 5 1 3 6 2 4 7 9 8 0 Ich habe es nach 0 1 2 3 4 5 6 7 8 9 sortiert, wie ich es wünschte. Hier

ist der Code:

using System; 
using System.Collections.Generic; 
using System.Linq; 
using System.Text; 
using System.Threading.Tasks; 

namespace SelectionSort 
{ 
    class Program 
    { 
     static void Main(string[] args) 
     { 
     int howMany = int.Parse(Console.ReadLine()); //length of array 
     List<int> Base = new List<int>(Array.ConvertAll(Console.ReadLine().Split(), int.Parse)); //input to array (i.e. 5 1 3 6 2 4 7 9 8 0 => { 5, 1, 3, 6, 2, 4, 7, 9, 8, 0 }) 
     List<int> Output = new List<int>(); // list to store sorted array 

     string[] ans = new string[howMany]; // array for storing answers 

     int loops = Base.Count(); 

     for(int i = 0; i != loops; i++) 
     { 
      int topID = 0, topValue = 0; 
      for(int j = 0; j != Base.Count(); j++) 
      { 
       if (j == 0) 
       { 
        topID = 0; 
        topValue = Base[0]; 
       } 
       else 
       { 
        if(topValue < Base[j]) 
        { 
         topValue = Base[j]; 
         topID = j; 
        } 
       } 
      } 
      ans[i] = topID.ToString(); //after looping through array save topID to answer array 
      Output.Add(Base[topID]); //add topValue to output 
      Base.RemoveAt(topID);  //remove topValue with index topID from list 
     } 

     //Output.Reverse();     // Writing on stdout 
     //foreach(var s in Output)   // sorted array 
     //{         // 
     // Console.Write(s + " ");  // It works without any problems 
     //}         // 
     //Console.ReadLine();    // 

     foreach(var s in ans) 
     { 
      Console.Write(s + " "); // write on stdout stored indexes 
     } 
     Console.ReadLine(); 
    } 

    } 
} 

D.h. für einen solchen Testdaten:

124 144 146 4 121 106 142 153 168 122 42 135 127 126 16 193 52 29 161 186 83 152 72 51 125 37 116 187 133 183 132 80 53 185 129 7 189 98 128 32 33 56 157 49 50 10 77 11 196 160 162 68 43 14 181 112 113 94 100 165 79 172 159 156 57 9 6 66 86 17 63 46 178 130 88 192 124 105 182 34 18 76 155 24 89 123 12 179 109 188 13 40 5 163 45 27 85 103 93 69 58 25 81 145 92 30 138 154 177 158 140 91 171 139 67 175 184 120 8 54 147 84 174 95 55

bekam ich es nach: 4 5 6 7 8 9 10 11 12 13 14 16 17 18 24 25 27 29 30 32 33 34 37 40 42 43 45 46 49 50 51 52 53 54 55 56 57 58 63 66 67 68 69 72 76 77 79 80 81 83 84 85 86 88 89 91 92 93 94 95 98 100 103 105 106 109 112 113 116 120 121 122 123 124 125 126 127 128 129 130 132 133 135 138 139 140 142 144 145 146 147 152 153 154 155 156 157 158 159 160 161 162 163 165 168 171 172 174 175 177 178 179 181 182 183 184 185 186 187 188 189 192 193 196

und ich habe eine solche Indizes: 47 14 72 34 84 25 17 29 107 25 69 46 76 63 94 100 105 52 96 7 49 76 41 15 39 47 86 33 46 61 82 6 15 87 1 75 0 3 76 77 75 5 16 16 46 18 20 5 5 11 42 48 3 1 64 10 26 25 44 1 36 48 25 12 58 23 45 49 50 37 32 28 41 49 5 43 8 21 16 29 5 35 16 37 21 22 32 18 11 34 33 7 3 4 9 8 15 22 10 1 18 3 12 5 4 17 2 14 14 10 9 8 1 4 7 6 3 2 2 4 1 1 1 0

, als ich diese bekommen soll: 47 14 74 35 88 26 18 32 115 28 77 53 86 71 107 28 74 60 86 7 58 92 49 17 48 61 28 41 62 81 60 6 20 88 1 6 0 5 74 53 5 10 27 29 72 33 37 11 12 23 12 53 8 3 32 25 55 54 0 4 11 41 57 36 14 56 28 56 8 5 12 8 41 35 19 19 30 14 45 29 21 28 35 37 5 32 19 11 19 30 26 31 15 22 21 28 3 11 19 9 6 9 11 5 15 7 16 3 3 10 12 3 3 8 1 6 6 3 4 3 1 0 1

Was mache ich falsch? Grüße

+1

Ihr Code könnte von Code Review SE profitieren, sobald der Fehler behoben wurde. Es gibt eine Menge stilistischer Probleme, die Sie in Zukunft vielleicht verstehen und vermeiden möchten. – usr

+0

Können Sie das Problem mit einem sehr kurzen Array reproduzieren, z. Länge 3? – usr

+0

Eigentlich funktioniert es mit solchen kurzen Arrays ohne Probleme –

Antwort

0

Kurz, Sie folgen nicht den erwarteten Algorithmus, daher der Unterschied.

Die Erwartung ist, zu Austausch das gefunden max Element auf jeden Schritt mit dem aktuellen letzten Elemente, und Sie haben es anders implementiert durch das gefunden max Element zu entfernen. Während dies eine korrekte sortierte Ausgabe erzeugt, sind die Indizes unterschiedlich (RemoveAt verschiebt alle Indizes, nachdem die eine entfernt wurde).

Um die erwarteten Ergebnisse zu erhalten, implementieren Sie den Algorithmus genau wie in der Problembeschreibung beschrieben.

Oder die obigen Ausführungen wie folgt korrigieren:

ersetzen
for(int j = 0; j != Base.Count(); j++) 

mit

int lastID = Base.Count - 1 - i; 
for (int j = 0; j <= lastID; j++) 

dann ersetzen

Base.RemoveAt(topID); 

mit

Base[topID] = Base[lastID]; 
Base[lastID] = topValue; 

und Sie sind fertig.

Beachten Sie auch, dass dies inplace Algorithmus, und am Ende Base Liste wird das Sortierergebnis enthalten, so dass die Output Liste ist überflüssig.