Binary Search Tree sort

**ElPosto** · 12-31-2017

Originally Posted by jimblumberg

What instructions? IMO, that typedef is horrible and all it really does is aid in confusion.

What examples are you talking about, I don't see anything "below"?

The following is probably a good reason using that typdef is confusing:

Code:

void merge(ARRAY A, int left, int middle, int right){
    ARRAY TEMP;
...

What is the size of the TEMP array?

Why is it that size?

If you don't understand dynamic memory then perhaps you shouldn't be using such large numbers for your array sizes.

*above sorry, I mistook because I'm not native english so I don't speak english the best way.
Don't be so agressive, I HAD to use typedef because I HAVE instructions in my homework and I HAVE to use such large arrays. What don't you understand in this ?

I didn't say I don't understand dynamic memory, I just said I'm not used to use them

**ElPosto** · 12-31-2017

Originally Posted by jimblumberg

What instructions? IMO, that typedef is horrible and all it really does is aid in confusion.

What examples are you talking about, I don't see anything "below"?

The following is probably a good reason using that typdef is confusing:

Code:

void merge(ARRAY A, int left, int middle, int right){
    ARRAY TEMP;
...

What is the size of the TEMP array?

Why is it that size?

If you don't understand dynamic memory then perhaps you shouldn't be using such large numbers for your array sizes.

By the way, there is little evidence that TEMP has the size defined by his type ARRAY : N elements !

**ElPosto** · 12-31-2017

Originally Posted by john.c

The easiest way to allow the allocation of a large object is to allocate the large object statically.

Code:

int main(void) {
    static ARRAY a;

Dynamic allocation is better, though, since it allows you to let the user choose the size. Get rid of the ARRAY typedef and just accept the array as an int* in functions.

Code:

int main(int argc, char **argv) {
    if (argc != 2) {
        fprintf(stderr, "Usage: treesort ARRAYSIZE\n");
        exit(EXIT_FAILURE);
    }

    int size = atoi(argv[1]);
    if (size < 1) {
        fprintf(stderr, "Error: ARRAYSIZE must be > 0\n");
        exit(EXIT_FAILURE);
    }

    int *a = malloc(size * sizeof *a);
    if (a == NULL) {
        perror("Error: malloc");
        exit(EXIT_FAILURE);
    }

    // ...

    free(a);
    return 0;
}

One more time, Thank you very much for helping me john.c. You are a pearl !

**jimblumberg** · 12-31-2017

I HAD to use typedef because I HAVE instructions in my homework and I HAVE to use such large arrays.

What does using that horrible typedef have to do about using such large arrays?

By the way, there is little evidence that TEMP has the size defined by his type ARRAY : N elements !

What? There is a lot of evidence that TEMP is defined with a size of N, which is probably about twice as large as it needs to be.

**ElPosto** · 12-31-2017

Originally Posted by jimblumberg

What does using that horrible typedef have to do about using such large arrays?

What? There is a lot of evidence that TEMP is defined with a size of N, which is probably about twice as large as it needs to be.

So, if there is no correlation between them, why should I get rid of it ?

+It is quite normal that TEMP has the same size as ARRAY, as TEMP is used to fill ARRAY in the merge function. --> I already tried to reduce it but the algorithm won't fullfill the desired purpose.
The merge algorithm I wrote is as clear as possible and has just what it needs where it is needed.

**rcgldr** · 12-31-2017

Originally Posted by ElPosto

TEMP has the same size as ARRAY

Modified example where the temp array allocation is only as large as it needs to be:

Code:

#include <stdio.h>
#include <stdlib.h>

void merge(int a[], int left, int middle, int right){
    /* only allocate what is needed */
    int * tmp = malloc((right+1-left)*sizeof(int));
    int i = left, j = middle + 1, k = 0;
    while(i <= middle && j <= right){
        if(a[i] <= a[j])
            tmp[k++] = a[i++];
        else
            tmp[k++] = a[j++];
    }
    while(i <= middle)
        tmp[k++] = a[i++];
    while(j <= right)
        tmp[k++] = a[j++];
    for(i = left; i <= right; i++)
        a[i] = tmp[i-left];        /* this handles variable size tmp[] */
    free(tmp);
}


void merge_sort_gen(int a[], int left, int right){
    int middle;
    if(left < right){
        middle = (left + right) / 2;
        merge_sort_gen(a, left, middle);
        merge_sort_gen(a, middle + 1, right);
        merge(a, left, middle, right);
    }
}

void merge_sort(int a[], int n){
    merge_sort_gen(a, 0, n-1);
}

#define N (1024*1024)

int main(void){
    int *a = malloc(N * sizeof(int));
    int i;
    for(i = 0; i < N; i++)
        a[i] = rand();
    merge_sort(a, N);
    for(i = 1; i < N; i++){
        if(a[i-1] > a[i]){
            printf("sort failed\n");
            break;
        }
    }
    if(i == N)
        printf("sort passed\n");
    free(a);
    return 0;
}

**rcgldr** · 12-31-2017

A somewhat optimized top down merge sort that does a one time allocation and uses two mutually recursive routines to change the direction of merge based on level of recursion instead of copying data in the merge function. This version is a bit over twice as fast as the example in my prior post. The right index in this example is the index to the end of the array == index to last element + 1.

As for the original post, I'll add an example of using a linked list merge sort and converting to binary search tree later if it turns out to be faster.

Code:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void SplitMergeAtoA(int a[], int b[], size_t ll, size_t ee);
void SplitMergeAtoB(int a[], int b[], size_t ll, size_t ee);
void Merge(int a[], int b[], size_t ll, size_t rr, size_t ee);

void MergeSort(int a[], size_t n)       // entry function
{
int *b;
    if(n < 2)                           // if size < 2 return
        return;
    b = malloc(n*sizeof(int));
    SplitMergeAtoA(a, b, 0, n);
    free(b);
}

void SplitMergeAtoA(int a[], int b[], size_t ll, size_t ee)
{
size_t rr;
    if((ee - ll) == 1)                  // if size == 1 return
        return;
    rr = (ll + ee)>>1;                  // midpoint, start of right half
    SplitMergeAtoB(a, b, ll, rr);
    SplitMergeAtoB(a, b, rr, ee);
    Merge(b, a, ll, rr, ee);            // merge b to a
}

void SplitMergeAtoB(int a[], int b[], size_t ll, size_t ee)
{
size_t rr;
    if((ee - ll) == 1){                 // if size == 1 copy a to b
        b[ll] = a[ll];
        return;
    }
    rr = (ll + ee)>>1;                  // midpoint, start of right half
    SplitMergeAtoA(a, b, ll, rr);
    SplitMergeAtoA(a, b, rr, ee);
    Merge(a, b, ll, rr, ee);            // merge a to b
}

void Merge(int a[], int b[], size_t ll, size_t rr, size_t ee)
{
size_t o = ll;                          // b[]       index
size_t l = ll;                          // a[] left  index
size_t r = rr;                          // a[] right index
    while(1){                           // merge data
        if(a[l] <= a[r]){               // if a[l] <= a[r]
            b[o++] = a[l++];            //   copy a[l]
            if(l < rr)                  //   if not end of left run
                continue;               //     continue (back to while)
            while(r < ee)               //   else copy rest of right run
                b[o++] = a[r++];
            break;                      //     and return
        } else {                        // else a[l] > a[r]
            b[o++] = a[r++];            //   copy a[r]
            if(r < ee)                  //   if not end of right run
                continue;               //     continue (back to while)
            while(l < rr)               //   else copy rest of left run
                b[o++] = a[l++];
            break;                      //     and return
        }
    }
}

#define N (16*1024*1024)

int main(void){
int *a = malloc(N * sizeof(int));
int i;
clock_t ctTimeStart;            // clock values
clock_t ctTimeStop;
    for(i = 0; i < N; i++)
        a[i] = rand();
    ctTimeStart = clock();
    MergeSort(a, N);
    ctTimeStop = clock();
    for(i = 1; i < N; i++){     // check for error 
        if(a[i-1] > a[i]){
            printf("sort failed\n");
            break;
        }
    }
    if(i == N){
        printf("sort passed\n");
        printf("# of ticks %d\n", ctTimeStop-ctTimeStart);
    }
    free(a);
    return 0;
}

**jimblumberg** · 12-31-2017

So, if there is no correlation between them, why should I get rid of it ?

Because that typedef is trying to hide something that shouldn't be hidden.

Do you realize that the following are all equivalent?

Code:

int someFunction1(int *value);
int someFunction2(int value[]);
int someFunction3(int value[10]);

Also note that the number in that last line is completely ignored by the compiler. You could call that function with an array with the size of one million and the code will still compile.

**ElPosto** · 01-01-2018

Originally Posted by john.c

The easiest way to allow the allocation of a large object is to allocate the large object statically.

Code:

int main(void) {
    static ARRAY a;

Dynamic allocation is better, though, since it allows you to let the user choose the size. Get rid of the ARRAY typedef and just accept the array as an int* in functions.

Code:

int main(int argc, char **argv) {
    if (argc != 2) {
        fprintf(stderr, "Usage: treesort ARRAYSIZE\n");
        exit(EXIT_FAILURE);
    }

    int size = atoi(argv[1]);
    if (size < 1) {
        fprintf(stderr, "Error: ARRAYSIZE must be > 0\n");
        exit(EXIT_FAILURE);
    }

    int *a = malloc(size * sizeof *a);
    if (a == NULL) {
        perror("Error: malloc");
        exit(EXIT_FAILURE);
    }

    // ...

    free(a);
    return 0;
}

BTW, using static makes the test program run considerably faster. Insted of having a 200,000 element array sorted in 0,33 secs, it is now sorted in 0,04 with the merge sort ! Is this normal ?

**ElPosto** · 01-01-2018

Originally Posted by ElPosto

BTW, using static makes the test program run considerably faster. Insted of having a 200,000 element array sorted in 0,33 secs, it is now sorted in 0,04 with the merge sort ! Is this normal ?

I've done some further tests to know if the arrays to be sorted were the sames, which could have explained why it's run so fast, but it's now sure they contain different values

**rcgldr** · 01-01-2018

The allocate for the array should be allocating based on the size of integers, not the size of a pointer to integer (this would make a difference with a 64 bit build, 64 bit pointers, 32 bit integers).

Code:

/* ... */
    int *a = malloc(size * sizeof(int));

**john.c** · 01-02-2018

Originally Posted by ElPosto

I've done some further tests to know if the arrays to be sorted were the sames, which could have explained why it's run so fast, but it's now sure they contain different values

That seems like an inordinate speedup. I'd have to see both versions of the code.

**rcgldr** · 01-03-2018

Originally Posted by ElPosto

Instead of having a 200,000 element array sorted in 0.33 secs, it is now sorted in 0.04 with the merge sort ! Is this normal ?

With the merge sort I posted in my prior post, I get a time of 0.014 seconds for 200,000 element array on my system (Intel 3770K 3.5ghz), so the 0.04 seems reasonable, while the 0.33 seems unusually slow.

Thread: Binary Search Tree sort

Thread Tools

Search Thread

Display

Similar Threads

Binary Search Tree-search method help?

binary search tree

binary interface to binary search tree giving me SUCH A HEADACHE!!

A Binary Search Tree of... Binary Search Trees...

Search Engine - Binary Search Tree

Tags for this Thread