CODEWITHSUNDEEP
cquicksort
apps
apps

Reputation: 37

endless loop in Quicksort

I was implementing the Quicksort Algorithm, but I have some error and I'm not able to figure out. I'm using the rand() function to generate random numbers. I'm limiting these numbers in mod(100). mod (100) works well but when I make it mod(10) it doesn't work. The program runs but stops after printing the random unsorted array.

Here's my code:

#include <stdio.h>
#include <stdlib.h>
int a[50];
void quicksort(int l, int r)
{
    int s;
    if(l<r)
    {
        s=partition(l, r);
        quicksort(l, s-1);
        quicksort(s+1, r);
    }
}

int partition(int l, int r)
{
    int p, i, j, temp;
    p = a[l];
    i=l;
    j=r+1;
    while(i<=j)
    {
        while(a[i]<=p && i<r+1)
            i=i+1;
        while(a[j]>=p && j>l)
            j=j-1;
        temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
    temp = a[i];
    a[i] = a[j];
    a[j] = temp;
    temp = a[l];
    a[l] = a[j];
    a[j] = temp;
    return j;
}
int main()
{
    int n, i;
    printf("Enter number of elements: \n");
    scanf("%d", &n);
    printf("Random Array: \n");
    for(i=0; i<n; i++)
    {
        a[i] = rand()%100; // The error seems to be here for rand()%10
        printf("%d  ", a[i]);
    }
    quicksort(0,n-2);
    printf("\n Solution: \n");
    for(i=0; i<n; i++)
    {
        printf("%d  ", a[i]);
    }
    return 0;
}

Any help would be appreciated. Thanks.

Upvotes: 1

Views: 93

Answers (1)

Yunnosch
Yunnosch

Reputation: 26703

This loop condition inside partition() can end up in an endless loop:

while(i<=j)

To avoid change it to

while(i<j)

It never needs to swap at two identical indexes anyway.

Upvotes: 1

Related Questions