Quick Sort Help

This is a discussion on Quick Sort Help within the C Programming forums, part of the General Programming Boards category; Greetings All, I am trying to write a program for sorting number by quick sort method. I am posting the ...

  1. #1
    Registered User
    Join Date
    Mar 2012
    Posts
    24

    Quick Sort Help

    Greetings All,

    I am trying to write a program for sorting number by quick sort method.

    I am posting the Code, There is no Compiler error but the result is wrong.

    can anyone please point me out the mistake.

    Thank you in Advance.

    Code:
    #include <Stdio.h>
    #include <conio.h>
    
    int sorted(int *l, int *u)
    {
        int mark;
        while(l<=u)
        {
            if((*l)<(*(l+1)))
                mark=1;
            else
                return 0;
            l++;
        }
        return 1;
    }
    
    
    
    
    void quick(int *a, int *b)
    {
        int hold,s;
        int *ll=(a+1);
        int *ul=b;
        for(;ll<=ul;ll++,ul--)
        {
            if((*ll>*a)&&(*ul<*a))
            {
                hold=*ul;
                *ul=*ll;
                *ll=hold;
            }
        }
        *a=*ll;
        *ll=hold;
        s=sorted(a,b);
        if(s==0)
        {
            quick(a,ll-1);
            quick(ll+1,b);
        }
    }
    
    int main()
    {
        int *a;
        int *b;
        int arr[50];
        int n,count;
        clrscr();
        printf("Entre the length of the Array to be sorted");
        scanf("%d",&n);
        printf("Entre the Array");
        for(count=0;count<n;count++)
        {
            scanf("%d",arr[count]);
        }
        a=&(arr[0]);
        b=&(arr[n-1]);
        quick(a,b);
        printf("The sorted Array is");
        for(count=0;count<n;count++)
        {
            printf("%d",arr[count]);
        }
        getch();
        return 0;
    }

  2. #2
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Try printing out the array right after you input it. This is problem #1:
    Code:
    scanf("%d",arr[count]);

  3. #3
    Registered User
    Join Date
    Mar 2012
    Posts
    24
    OK guys I kind of Fixed this but the problem is--

    1) It works upto 6 input.

    2) When I give 7 or more Numbers to sort. It gives no response.

    Please tell me whats wrong with my code.

    Code:
    #include <Stdio.h>
    #include <conio.h>
    
    int sorted(int *l, int *u)
    {
        int mark;
        while(l<u)
        {
            if(*l<*(l+1))
                mark=1;
            else
                return 0;
            l++;
        }
        return 1;
    }
    
    
    
    
    void quick(int *a, int *b)
    {
        int count;
        int hold,s;
        int *ll=(a+1);
        int *ul=b;
    
    
        while(ll<=ul)
        {
            if(*ll>*a)
            {
                if(*ul<*a)
                {
                    hold=*ul;
                    *ul=*ll;
                    *ll=hold;
                }
            }
            if(*ll<*a)
            {
                ll++;
            }
            if(*ul>*a)
            {
                ul--;
            }
        }
        hold=*a;
        *a=*ul;
        *ul=hold;
    
        s=sorted(a,b);
        if(s==0)
        {
            quick(a,ul-1);
            quick(ul+1,b);
        }
    
    }
    
    int main()
    {
        int *a;
        int *b;
        int arr[50];
        int n,count;
        clrscr();
        printf("Entre the length of the Array to be sorted");
        scanf("%d",&n);
        printf("Entre the Array");
        for(count=0;count<n;count++)
        {
            scanf("%d",&arr[count]);
        }
    
    
        a=&arr[0];
        b=&arr[n-1];
    
        getch();
        quick(a,b);
        printf("The sorted Array is");
        for(count=0;count<n;count++)
        {
            printf("\n%d",arr[count]);
        }
        getch();
        return 0;
    }

  4. #4
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    "Lost a planet have you?"

    Seriously, I can't look at your code and spot the error. I would have to put in some print statements with getchar() immediately afterward, and then enter 7 values to be sorted, and run it, and study the output as it goes.

    Using a debugger, you could also step through the program, and watch the values that way. My point is that either of the above you can do, and should learn and practice. Code errors are not going away, and learning to debug your programs is an essential skill.

    Since this is obviously not your original program, why don't you look back at that original program, and see where the error is?

  5. #5
    Registered User
    Join Date
    Oct 2008
    Location
    TX
    Posts
    2,047
    At the very least try 'n understand quicksort before implementing it.
    Here is a interactive tutorial that helps in comprehending its basics.

  6. #6
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,288
    Think about what will happen if ul, ll, and a all point to the same value. Not necessarily the same place, just the same values wherever they point.
    That's called an infinite loop!
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  7. #7
    Registered User
    Join Date
    Mar 2012
    Posts
    24
    Thanks for the Comments. I Solved it. There was some problem with swaping the numbers.

    Here is the final Code.

    Code:
    #include <Stdio.h>
    #include <conio.h>
    
    int sorted(int *l, int *u)
    {
    
        while(l<u)
        {
              if(*l>*(l+1))
            return 0;
              else
            l++;
        }
        return 1;
    }
    
    
    
    
    void quick(int *a, int *b)
    {
        int *i;
        int *u;
        int *l;
        int count;
        int hold,s;
        int *ll=(a+1);
        int *ul=b;
    
    
        while(ll<ul)
        {
            if(*ll>*a)
            {
                if(*ul<*a)
                {
                    hold=*ul;
                    *ul=*ll;
                    *ll=hold;
                }
            }
            if(*ll<*a)
            {
                ll++;
            }
            if(*ul>*a)
            {
                ul--;
            }
        }
        hold=*a;
        u=ul;
        l=ll;
        i=a;
        count=0;
        while(i<l)
        {
            *(a+count)=*(a+count+1);
            count++;
            i++;
        }
        *(a+count)=hold;
    
        s=sorted(a,b);
        if(s==0)
        {
            if(ll>a)
                quick(a,ll-1);
            if (ll<b)
                quick(ll+1,b);
        }
    
    }
    
    
    int main()
    {
        int *a;
        int *b;
        int arr[50];
        int n,count;
        clrscr();
        printf("Entre the length of the Array to be sorted");
        scanf("%d",&n);
        printf("Entre the Array");
        for(count=0;count<n;count++)
        {
            scanf("%d",&arr[count]);
        }
    
    
        a=&arr[0];
        b=&arr[n-1];
    
        getch();
        quick(a,b);
        printf("The sorted Array is");
        for(count=0;count<n;count++)
        {
            printf("\n%d",arr[count]);
        }
        getch();
        return 0;
    }

  8. #8
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Congratulations, sunny!

    I've seen several way of implementing the Quicksort algorithm, but yours is a type I've not seen before. Very interesting!

  9. #9
    Registered User
    Join Date
    May 2009
    Posts
    2,493
    Simple question about include
    Code:
    #include <Stdio.h>
    Will the capital S of "Stdio.h" work on Linux/UNIX systems?

    Tim S.
    "Programming today is a race between software engineers striving to build bigger and better idiot-proof programs, and the universe trying to produce bigger and better idiots. So far, the Universe is winning." Rick Cook

  10. #10
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Shouldn't work, since they're case sensitive. Really shouldn't use the capital S in the header file.

  11. #11
    Registered User
    Join Date
    May 2012
    Posts
    1,066
    Doesn't work:
    Code:
    $ cat test.c
    #include <Stdio.h>
     
    int main(void)
    {
        printf("test");
    
        return 0;
    }
    $ gcc -Wall -Wextra -o test test.c
    test.c:1:19: fatal error: Stdio.h: file not found
    compilation terminated.
    Bye, Andreas

  12. #12
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,288
    You didn't pay any attention to my post did you.

    Try using it to sort an array that hold just three copies of the number 42.
    Lets just say I wont be waiting around for the program to finish and you to then repost with the results, as I don't have... forever.

    Oh how I wish educational institutions taught Test Driven Development!
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Quick Sort
    By chriscolden in forum C Programming
    Replies: 3
    Last Post: 06-07-2006, 06:44 AM
  2. Quick Sort or Merge Sort???
    By swanley007 in forum C++ Programming
    Replies: 6
    Last Post: 11-10-2005, 05:48 PM
  3. Quick sort VS Merge Sort
    By sachitha in forum Tech Board
    Replies: 7
    Last Post: 09-03-2004, 11:57 PM
  4. Shell Sort vs Heap Sort vs Quick Sort
    By mackol in forum C Programming
    Replies: 6
    Last Post: 11-22-2002, 07:05 PM
  5. Quick sort
    By Saiyanman in forum C Programming
    Replies: 4
    Last Post: 07-30-2002, 10:16 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21