Help..Heapp..Heapp..

Hi All,

I wrote a program to read a file then sort it using up and down heapsort.. Yet, it only shows me the result correctly if there are less than 8 values, i have been trying to debug and still can't find where is the logic error.. Would you tell me where's the logic error?

Thanks.. :D

Code:

---

#include<stdio.h>

int array[300000],maxElm,i,j,k;

void pullValues() {
        printf("\nSorted Array\n");
        maxElm = j;
        for(i = 1; i <= j; i++) {
                printf("%d\n", array[i]);               
        }
}

void upSort(int *array,int i) {
        int v = array[i];

        while((i > 1) && (array[i/2] < v))
        {
                array[i] = array[i/2];
                i = i / 2;
        }
        array[i] = v;
}

void downSort(int *array,int i,int maxElm) {
        int v = array[i];
        int j = i * 2;
        while(j <= maxElm)
        {
                if((j < maxElm) && (array[j] < array[j+1])) {
                        j++;
                }
                if(array[j] < array[j/2]) {
                        break;
                }
                array[j/2] = array[j];
                j = j * 2;
        }
        array[j/2] = v;
}

main() {
        FILE *fp;

        printf("\nPlease input the number of entries (k): ");
        scanf("%d", &maxElm);

        if((fp = fopen("test_dat.txt", "r")) == NULL) {
                printf("Failed to open test_dat.txt\n");
                return 0;
        } else {
                printf("Success to open test_dat.txt\n");
                while(!feof(fp)) {
                        for(i = 1 ; i <= maxElm; i++) {
                                fscanf(fp, "%d", &array[i]);
                                      upSort(array,i);
                        }
                }
        }

        j=maxElm;
        for(i = 1; i <= j; i++) {
                int temp;
                temp=array[1];
                array[1]=array[maxElm];
                array[maxElm]=temp;
                maxElm--;
                downSort(array,1,maxElm);
        }
        pullValues();
}

---

Silly question: do you have more than 8 numbers in test_dat.txt?

Actually, I have 200,000 numbers and each of them are 5 digits.. But I tried wit 10 numbers and it gives me weird results.. Any idea why it works with less than 8 inputs? :D

I forget to mention that the result is in ascending order, it gives me what I want with less than 8 inputs.. Thanks :D

The global variables and one-based arrays made me throw up in my mouth a bit, but the rest of the code was tolerable. Just a few notes before wewe get to your algorithm:

1. main needs to be int main and you should return an integer (preferably zero) when done
2. Arrays in C are zero-base, i.e. the first element is array[0], not array[1].
3. Global variables are evil and make debugging more difficult. Make all of them, except your array (because it's so big) local to main and pass them as function parameters.
4. Also, it would make more sense to leave maxElem the same and make j the value that changes (e.g. at the bottom of main). Less re-purposing of variables means you are less likely to have bugs.

And for the $64,000 question:

Quote:

---

Originally Posted by c3jcarmy

Code:

---

void downSort(int *array,int i,int maxElm) {
        int v = array[i];
        int j = i * 2;
        while(j <= maxElm)
        {
                if((j < maxElm) && (array[j] < array[j+1])) {
                        j++;
                }
                if(array[j] < array[j/2]) {
                        break;
                }
                array[j/2] = array[j];
                j = j * 2;
                // finish swapping here
        }
        array[j/2] = v;
}

---

---

Try moving the rest of that swap (red line) inside the while loop.

Okay I figured out what you mean by "up and down heapsort".

That's not the normal way of doing heapsort. You're build the heap the naieve O(n*log n) way whereas it is typically done in O(n). Of course the subsequent extraction of each value from the heap is O(n*log n), so it's still O(n*log n) either way. In practice is makes the process oh say twice as fast.

However for 200000 values that are only six digits, there must clearly be some duplicates.
There are certain algorithms that are tailored to this situation that are more efficient. For the best speed you should consider other algorithms such as Flashsort, Bucketsort, Countingsort, or Radixsort. These may easily be ten times or so faster again. Should you care about speed at all that is.

Thanks to anduril462... It works perfectly fine by now! lol..
I use A[1] instead of A[0] since it is easier for me to debug how the heap will be.. But yeah, I will try to use based 0 instead of 1!
About the global variables, I thought it is easier to initiate a global variable rather than initiate the variable in every functions.. Is it more efficient than local variables? Sorry for this silly question.. :D

Global variables might be a little more efficient in some regards, but not enough to justify their use everywhere. You are exhibiting "pre-optimization", which means you're trying to make your program faster before you know whether it's too slow. This usually leads to problems. Write your code as clearly and solidly as possible, then only optimize the parts that need it and only if they really need it.

Here is a great article on why globals are bad.

Wow.. thanks! That answers all my questions.. lol
I'll try other sorts also, thanks.. :D

Hint: My homepage as found in my sig below is mostly about a massive collection of sorting algorithms, though I no longer say this in the link title since I don't want beginners to go straight there and just copy the code.

Nothing wrong with '1' based arrays, especially for heapsort. Its algorithm depends on array indexes being multiplied by 2 which would be ugly if one started with 0. I would declare a pointer int *pnt = &array[-1] and use that.

That is not kosher according to others who have quoted me the standard before. Some machine may store that array at address zero, and subtraction of 1 may not go below zero, yadda yadda and other such crap that means negative array index isn't technically allowed, even if you never access it.
However it's not actually necessary. It's easy enough to do it zero based. See the code on my webpage.

OK, iMalc. I didn't realize calculating negative address could be a problem. I guess it depends on whether the compiler generates code for signed vs. unsigned integer at that point, even if it's for an intermediate result.

I don't wanna go to your webpage. There's no way to multiply the index of array[0] by 2 and get something meaningful. You'll have to put 'if' statements all over the place for that exception. No amount of webpage can make 0 x 2 = 1.

Your left and right children are i * 2 + 1 and i * 2 + 2, no if statements needed.

Good point. For some reason I always coded children are i * 2 and i * 2 + 1. I save an addition some of the time. :)

Code:

---

  other way            my way

      [0]                  [1]
  [1]    [2]          [2]    [3]
[3] [4] [5] [6]      [4] [5] [6] [7]

---

The only reason I know that [-1] isn't valid is because other's (myself included) have also had this same idea in the past, and it was discussed on another forum.

You may certainly reserve the right to not visit my personal webpage. I'm not particularly proud of it anyway as it's very web 1.0 (if that).
Anyway, here is the relevant code from my site, converted to C:

Code:

---

#define T int
void HeapSortDownHeap(T a[], int l, int r) {
    T tempItem = a[l];
    int child = (l<<1) + 1;
    while (child < r) {
        //use right child if it is bigger
        if ((child + 1 < r) && (a[child] < a[child + 1]))
            ++child;
        if (!(tempItem < a[child]))
            break;
        a[l] = a[child];
        l = child;
        child = (child<<1) + 1;
    }
    a[l] = tempItem;
}

void HeapSort(T a[], int n) {
    //build heap
    for (int i = n>>1; i >= 0; --i)
        HeapSortDownHeap(a, i, n);
    //extract max item successively
    for (int j = n-1; j > 0; --j) {
        Swap(a[0], a[j]);
        HeapSortDownHeap(a, 0, j);
    }
}

---

As you can see, it performs just one extra addition per loop iteration inside HeapSortDownHeap. Feel free to critique the code, by the way.
You'd be hard pressed to measure any performance difference in doing it by using [-1], and if it were ever a matter of performance, you'd switch algorithm.

Nice ASCII art btw!

Quote:

---

Originally Posted by anduril462

And for the $64,000 question:

Try moving the rest of that swap (red line) inside the while loop.

---

Actually it is best as-is.
One of the more obvious yet slower ways to code heap sort is to downheap by performing repeated swaps:
To go from D, A, B, C to A, B, C, D you perform three swaps. Each swap consists of three assignments/copies, so that's 9 copies all up.

The techinque which both the OP and myself used is to shuffle the items instead:
You first set aside a copy of D, then assign A to where D was, B to where A was, and C to where B was, then put D in its place and you've done just 5 copies all up.

Of course when it comes to C++ and you have a type with a specialised std::swap then the other way wins. Hmm if only there were a way for the algorithm to know if a specialised std::swap is available. I'm kinda tempted to start my own thread asking this.

I think that the actual logic error is in the way he's building the heap. I suggest building it the O(n) way as done in my post above.