C ++ sorting 2d array using Tree sort

Question

I need to sort a 2d array. My idea is to turn the matrix into 1d array, then sort and convert the resulting array back into a matrix.

But while working, I encountered a problem. Here are the screenshots of output at the moment.

output 1

output 2

The first row is a transformed matrix filled with random numbers. And the second - the result of sorting. At first I thought that only part is sorted, but there is a certain pattern. It just first writes the numbers from 0 to 10 that occur in the array; and then displays the remaining numbers. And I dont understand why depends on how to make it sort properly. I also send the code

#include <iostream>
#include <iomanip>
#include<bits/stdc++.h>

using namespace std;


// Tree Sort

struct Node
{
    int key;
    struct Node *left, *right;
};

// Допоміжна функція для створення нового вузла 
struct Node *newNode(int item)
{
    struct Node *temp = new Node;
    temp->key = item;
    temp->left = temp->right = NULL;
    return temp;
}

// Stores inorder traversal of the BST
// in arr[]
void storeSorted(Node *root, int arr[], int &i)
{
    if (root != NULL)
    {
        storeSorted(root->left, arr, i);
        arr[i++] = root->key;
        storeSorted(root->right, arr, i);
    }
}

/*Допоміжна функція для вставки нового
вузла із заданим ключем */
Node* insert(Node* node, int key)
{
    /* Якщо дерево порожнє до нового вузла */
    if (node == NULL) return newNode(key);

    /* В іншому випадку  вниз по дереву */
    if (key < node->key)
        node->left = insert(node->left, key);
    else if (key > node->key)
        node->right = insert(node->right, key);

    /* повернути (без змін) покажчик вузла */
    return node;
}

// функция сортировки arr[0..n-1] Tree Sort
void treeSort(int arr[], int n)
{
    struct Node *root = NULL;

    // Construct the BST
    root = insert(root, arr[0]);
    for (int i=1; i<n; i++)
        root = insert(root, arr[i]);

    // Store inorder traversal of the BST
    // in arr[]
    int i = 0;
    storeSorted(root, arr, i);
}
//перетворення матриці в одновимірний масив
int main() {
    //матриця
    int n=2, m=12;
    srand(time(NULL)); // генератор випадкових чисел.
    int a[n][m];

    {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
                a[i][j] = rand()%11 ;
        }
    }
}

// переобразование
    int arr[n*m];
    
    
    // одновимірний масив
    memcpy(arr,a,24*sizeof(int));
  
    for (int i=0; i<n*m; i++) {
    cout<<arr[i]<<" ";
    }
    cout<<endl;
    
 
    treeSort( arr, n*m);
     for (int i=0; i<n*m; i++) {
        
    cout<<arr[i]<<" ";
    }
    
    return 0;
}

Answer 1

"I dont understand why depends on how to make it sort properly" -

Belaying the non-standard VLA hoops (which should be addressed regardless), this specific problem can be broken down to a simple matter of value-indifference.Look carefully at your code building the tree from the array and ask yourself what happens when you land on an element that is neither less-than nor greater-than the prospect value. (e.g. they're equivalent).

    /* В іншому випадку  вниз по дереву */
    if (key < node->key)
        node->left = insert(node->left, key);
    else if (key > node->key)
        node->right = insert(node->right, key);

    // ELSE ?????

Note that you only insert items into your tree if they're not already in the tree. When you encounter a duplicate value it is simply ignored.

You can address this a few ways. Obviously the easiest way would be just to remove the second conditional:

    /* В іншому випадку  вниз по дереву */
    if (key < node->key)
        node->left = insert(node->left, key);
    else
        node->right = insert(node->right, key);

Now everything not-less-than is hung on the right side, including duplicates. And this will work ok.

---

Counting Duplicates

You can make this considerably more efficient if you expect a significant number of duplicates by using a value counter in your tree node.

struct Node
{
    int key;
    int count; // <====== HERE
    struct Node *left, *right;
};

struct Node *newNode(int item)
{
    struct Node *temp = new Node;
    temp->key = item;
    temp->count = 1; // <====== HERE
    temp->left = temp->right = NULL;
    return temp;
}

Now, when adding the node, you can do this:

Node *insert(Node *node, int key)
{
    /* Якщо дерево порожнє до нового вузла */
    if (node == NULL)
        return newNode(key);

    /* В іншому випадку  вниз по дереву */
    if (key < node->key)
        node->left = insert(node->left, key);
    else if (node->key < key)
        node->right = insert(node->right, key);
    else
        ++node->count; // <==== HERE

    /* повернути (без змін) покажчик вузла */
    return node;
}

And finally, when storing the sorted values back to the original array, that requires only one more modification:

// Stores inorder traversal of the BST
// in arr[]
void storeSorted(const Node *root, int arr[], int &i)
{
    if (root != NULL)
    {
        storeSorted(root->left, arr, i);
        for (int j=0; j<root->count; ++j) // <=== HERE
            arr[i++] = root->key;
        storeSorted(root->right, arr, i);
    }
}

This just dumps whatever the value of the node is count times,, updating i each time.