Change 2d array bubble sort to counting sort

Question

The following code sorts rows by the first element using bubble method. I can't change it to counting sort.

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

Please help.

What have you tried to implement a counting sort? Have you looked at the various code samples available online? — scrappedcola, Nov 18 '15 at 22:06
Yes, I found the solution for 1d array, but I need to sort 2d array rows. http://rosettacode.org/wiki/Sorting_algorithms/Counting_sort#C.23 — Роман Горошко, Nov 18 '15 at 22:09
Counting sort is not applicable for `double`s. See http://stackoverflow.com/questions/33741875/sort-2d-array-rows-in-ascending-order-of-their-first-elements-in-c-sharp/33742498#33742498 for how you can effectively sort a 2d array. — Ivan Stoev, Nov 19 '15 at 11:26

M.kazem Akhgary · Accepted Answer · 2015-11-18T23:15:20.370

As you do bubble sort based on first element of each row. you should do counting sort like that too. so you just need to count first item of each row.

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

Here is the test.

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

Example Output:

{ 49,66,8 },{ 33,39,64 },{ 65,52,76 } // Original array
{ 33,39,64 },{ 49,66,8 },{ 65,52,76 } // Sorted array

Change 2d array bubble sort to counting sort

1 Answers1