2

I am very interested in how to sort 5 items using only 7 comparisons. I think I understand the theory how to do it but unfortunately I'm not able to write it as a code. Here I found an example in LISP

I really tried to understand it but it seems to me be not working. For example on the numbers 5,4,3,2,1.

Could anybody please give me an example code, but not in LISP? I prefer Java or C/C++. It would really help me in school.

Thank you in advance

P.S. Sorry for my english

Edit: Here I add some piece of code I wrote in Java. Variables a,b,c,d,e are there only for my better orientation in code. I'm able to write specific code for specific input items, that's no problem. But I can't write general code.

public static void sort(int p[]) {

    int a = 0;
    int b = 1;
    int c = 2;
    int d = 3;
    int e = 4;


    if (p[a] > p[b]) {
        swap(p,a,b);
        }
    if (p[c] > p[d]){
        swap(p,c,d);

        }

    if (p[b] > p[d]){
        swap(p,b,d);

    }

    if (p[e] < p[b]) {

        if (p[e] < p[a]) {

            swap(p,a,e);
            swap(p,d,e);
            //swap(p,b,d);//BLBE
        }else{

            swap(p,b,e);
            swap(p,d,e);
        }
    }else {
        if (p[e] < p[d]) {
            swap(p,d,e);

        }
    }

    if (p[c] < p[b]) {

        if (p[c] < p[a]) {

            swap(p,a,c);
            swap(p,b,c);
        }else
        {

            swap(p,c,b);
        }
    }else {
     if (p[c] > p[d]) {

        swap(p,d,c);
     }
    }

}
Community
  • 1
  • 1
vojtak
  • 55
  • 2
  • 7
  • 12
    If you understand the theory, and you have already tried to write some code yourself, then I suggest posting what you have written and describing what specific problems you are having. Questions that simply ask for code are not likely to get a lot of answers over here. – Grodriguez Nov 21 '10 at 22:14
  • 6
    1. Write a program that creates a binary tree, inserting all numbers sorted inside of it. That's 0+1+2+3+4 = 10 comparisons. 2. Modify the program so that right before the fourth insertion, the graph is balanced around the middle number. This will give you 0+1+2+2+3 = 8 comparisons. 3. Modify the program so that before the fifth insertion the bigger subtree of the root element is balanced the same way that you did in step 2, this will give you one less comparison. – Rosh Oxymoron Nov 21 '10 at 23:10
  • 1
    @Rosh: This is the answer, why don't you post it as one? – Daniel Feb 02 '11 at 08:22

1 Answers1

0

Writing a general comparison-based sorting algorithm takes O(n lg n) comparisons. If I'm not mistaken, then all O(n lg n) sorting algorithms will sort 5 items in about 7 comparisons. Mergesort, Heapsort and Quicksort if you're lucky.

Jeffrey Greenham
  • 1,382
  • 5
  • 16
  • 33