Actually, I thought I've fixed the problem of same values in the given array but now when I run the program for size of 200,000 elements, it takes more than 13 seconds to treat the array !! (although it's considered one of the quickest sort). At least the result is correct but...
Code:
struct Node *insert(struct Node *node, int value){
if(node == NULL)
return newNode(value);
if(value <= node->value)
node->left = insert(node->left, value);
else if (value > node->value)
node->right = insert(node->right, value);
return node;
}
Whereas with last writing it took 0.6 secs to run but the result wasn't correct, it pushed some values at the end of the array, as if we have inserted too much elements in the array. For example with a = [26 48 25 0 97 46 69 16 77 80 16 90 63 0 7] it returned --> 0 7 16 25 26 46 48 63 69 77 80 90 97 0 7
Code:
struct Node *insert(struct Node *node, int value){
if(node == NULL)
return newNode(value);
if(value < node->value)
node->left = insert(node->left, value);
else if (value > node->value)
node->right = insert(node->right, value);
return node;
}
So I'm a bit confused and don't have any clue to explain this big time difference and to have the correct function with the minimum time. I think the problem comes from the line in the binary tree sort function :
Code:
for(i = 0; i < n; i++)
insert(root, T[i]);
Even when adopting your writing, problems remain with odd sizes (N = 15) for example where a value is pushed at the end of the array
Code:
void binary_tree_sort(int T[], int n){
struct Node *root = NULL;
int i;
for(i = 0; i < n; i++)
root = insert(root, T[i]);
collect(root, T, 0);
}
So.. I must admit It's quite disturbing. I tried to "run" the program on a sheet of paper to make it function mentally but I haven't any clue to explain this problem of time difference either to solve it.
I hoped you could help me one more (last, I promess ) time...
Here is the complete source code:
Code:
#include <stdio.h>
#include<stdlib.h>
#define N 15
typedef int ARRAY[N];
void display_arr(ARRAY A, int n){
int i;
for(i = 0; i < n; i++)
printf("%d ", A[i]);
printf("\n\n");
}
struct Node{
int value;
struct Node *left, *right;
};
struct Node *newNode(int value){
struct Node *node = malloc(sizeof *node);
node->value = value;
node->left = NULL;
node->right = NULL;
return node;
}
struct Node *insert(struct Node *node, int value){
if(node == NULL)
return newNode(value);
if(value < node->value)
node->left = insert(node->left, value);
else if (value > node->value)
node->right = insert(node->right, value);
return node;
}
voidcollect(structNode *root, ARRAY A, int *i){
if(root != NULL){
collect(root->left, A, i);
A[(*i)++] = root->value;
collect(root->right, A, i);
}
}
voidbinary_tree_sort(ARRAY A, intn){
struct Node *root = NULL;
root = insert(root, A[0]);
int i;
for(i = 1; i < n; i++)
insert(root, A[i]);
i = 0;
collect(root, A, &i);
}
int main(void){
ARRAY A;
int r;
srand(time(0));
for(r = 0; r < N; r++)
A[r] = ((unsigned int)rand()%100);
printf("Array to sort : ");
display_arr(A, N);
binary_tree_sort(A, N);
printf("Array sorted : ");
display_arr(A, N);
return 0;
}