选择使用索引排序故障 [英] Selection Sort trouble with indexes

问题描述

其实我正在处理CodeAbbey问题，所以我不想回答代码，而是对此进行阐述，我做错了什么。 http://www.codeabbey.com/index/task_view/selection-sort

Actually I'm dealing with CodeAbbey problem, so I don't want answer as code, but explenation about that, what I am doing wrong. http://www.codeabbey.com/index/task_view/selection-sort

我的选择排序实际上没有任何问题，但我不知道为什么我没有得到正确的索引（当排序工作时！）。即输入数据： 5 1 3 6 2 4 7 9 8 0 我把它分类到 0 1 2 3 4 5 6 7 8 ，正如我所希望的那样。

My Selection Sort actually works without any problems, but I don't know why I do not get proper indexes (when sorting works!). I.e. for input data:5 1 3 6 2 4 7 9 8 0 I got it sorted to 0 1 2 3 4 5 6 7 8 9, as I wished.

以下是代码：

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();
    }

  }
}

I.e。对于这样的测试数据：

I.e. for such a test data:

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

我把它分类为：
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

和我得到这样的指数：
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 0 0

and I got such an indexes: 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

当我应该得到这些：
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

我做错了什么？
Greetings

What am I doing wrong? Greetings

推荐答案

很快，您没有遵循预期的算法，因此存在差异。

Shortly, you are not following the expected algorithm, hence the difference.

期望是使用当前最后一个元素交换每个步骤中找到的最大元素，并且您通过删除来实现它找到最大元素。虽然这会产生正确的排序输出，但索引是不同的（ RemoveAt 在删除之后重新定位所有索引。）

The expectation is to exchange the found max element on each step with the current last element, and you have implemented it differently by removing the found max element. While this produces correct sorted output, the indices are different (RemoveAt relocates all indices after the one being removed).

要获得预期结果，请完全按照问题描述中的描述实施算法。

To get the expected results, implement the algorithm exactly as described in the problem description.

或者按如下方式更正上述实现：

Or correct the above implementations as follows:

替换

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

with

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

然后替换

Base.RemoveAt(topID);

with

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

您已完成。

请注意，这是 inplace 算法，最后 Base 列表将包含排序结果，因此输出列表是多余的。

Also note that this is inplace algorithm, and at the end Base list will contain the sorted result, so the Output list is redundant.

这篇关于选择使用索引排序故障的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！