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;
}

---

Try printing out the array right after you input it. This is problem #1:

Code:

---

scanf("%d",arr[count]);

---

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;
}

---

"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?

At the very least try 'n understand quicksort before implementing it.
Here is a interactive tutorial that helps in comprehending its basics.

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!

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;
}

---

Congratulations, sunny!

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

Simple question about include

Code:

---

#include <Stdio.h>

---

Will the capital S of "Stdio.h" work on Linux/UNIX systems?

Tim S.

Shouldn't work, since they're case sensitive. Really shouldn't use the capital S in the header file.

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

You didn't pay any attention to my post did you. :rolleyes:

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! :D