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.

Answer 1

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