Изменить пузырьковую сортировку двумерного массива на сортировку подсчетом

Следующий код сортирует строки по первому элементу, используя пузырьковый метод. Я не могу изменить его на сортировку подсчетом.

public void SortStack(double[,] n)
{
   for (int i = 0; i < n.GetLength(0) - 1; i++)
   {
       for (int j = i; j < n.GetLength(0); j++)
       {
           if (n[i, 0] > n[j, 0]) 
           {
               for (int k = 0; k < n.GetLength(1); k++)
               {
                   var temp = n[i, k];
                   n[i, k] = n[j, k];
                   n[j, k] = temp;
               }
           }
        }
   }
}

Пожалуйста помоги.


arrays c# sorting counting-sort
person Роман Горошко    schedule 18.11.2015    source источник
comment
Что вы пытались реализовать сортировку подсчетом? Вы смотрели на различные образцы кода, доступные в Интернете?   -  person scrappedcola    schedule 19.11.2015
comment
Да, я нашел решение для массива 1d, но мне нужно отсортировать строки массива 2d. rosettacode.org/wiki/Sorting_algorithms/Counting_sort#C.23   -  person Роман Горошко    schedule 19.11.2015
comment
Сортировка подсчетом неприменима для doubles. См. title="сортировать строки массива 2d в порядке возрастания их первых элементов в c Sharp"> stackoverflow.com/questions/33741875/, чтобы узнать, как эффективно сортировать массив 2d.   -  person Ivan Stoev    schedule 19.11.2015

Ответы (1)


arrow_upward
0
arrow_downward

Как вы делаете пузырьковую сортировку на основе первого элемента каждой строки. вы тоже должны делать такой подсчет. поэтому вам просто нужно подсчитать первый элемент каждой строки.

private static int[,] CountingSort2D(int[,] arr)
{
    // find the max number by first item of each row
    int max = arr[0, 0];
    for (int i = 0; i < arr.GetLength(0); i++)
    {
        if (arr[i, 0] > max) max = arr[i, 0]; 
    }

    // we want to get count of first items of each row. thus we need 1d array.
    int[] counts = new int[max + 1]; 

    // do the counting. again on first index of each row
    for (int i = 0; i < arr.GetLength(0); i++)
    {
        counts[arr[i, 0]]++; 
    }
    for (int i = 1; i < counts.Length; i++)
    {
        counts[i] += counts[i - 1];
    }

    // result is sorted array
    int[,] result = new int[arr.GetLength(0), arr.GetLength(1)];

    for (int i = arr.GetLength(0) - 1; i >= 0; i--)
    {
        counts[arr[i, 0]]--;

        // now we need to copy columns too. thus we need another loop
        for (int j = 0; j < arr.GetLength(1); j++)
        {
            result[counts[arr[i, 0]], j] = arr[i, j];
        }
    }

    return result;
}

Вот тест.

static void Main()
{
    Random rand = new Random();
    int[,] arr = new int[3,3];
    for (int i = 0; i < 3; i++)
    {
        for (int j = 0; j < 3; j++)
        {
            arr[i, j] = rand.Next(0, 100);
        }
    }

    int[,] newarr = CountingSort2D(arr);

    for (int i = 0; i < arr.GetLength(0); i++)
    {
        Console.Write("{ ");
        for (int j = 0; j < arr.GetLength(1); j++)
        {
            Console.Write(arr[i, j] + " ,");
        }
        Console.Write("} ,");
    }

    Console.WriteLine();

    for (int i = 0; i < newarr.GetLength(0); i++)
    {
        Console.Write("{ ");
        for (int j = 0; j < newarr.GetLength(1); j++)
        {
            Console.Write(newarr[i, j] + " ,");
        }
        Console.Write("} ,");
    }

    Console.WriteLine();
}

Пример вывода:

{ 49,66,8 },{ 33,39,64 },{ 65,52,76 } // Original array
{ 33,39,64 },{ 49,66,8 },{ 65,52,76 } // Sorted array
person M.kazem Akhgary    schedule 18.11.2015