[sumi1234]

I need to implement quicksort (without using stacks) with the first element as pivot. I tried to write the code but i am getting some problems with it. here is what i have got so far

//Quicksort program
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>

const int MAX_ELEMENTS = 10;

void swap(int *a,int *B)/>
{
    int temp=*a;
    *a=*b;
    *b=temp;
}

void printlist(int list[],int n)
{
    int i;
    for(i=0;i<n;i++)
        printf("%d\t",list[i]);
}

void partition(int list[],int low,int high,int pivot)
{
    int x,left,right;
    x=list[low];
    right=high;
    left=low+1;
    while(left<right)
    {
        while((list[left]<=x) && (left<right))
            left++;
        while(list[right]>x)
            right--;
        if(list[left]<list[right])
        {
            swap(&list[right],&list[left]);
            left++;
            right--;
        }
    }
        swap(&list[low],&list[right]);

}






int quicksort(int list[],int low,int high)
{
    if(low>high)
        return 0;
    int pos=low;
    partition(list,low,high,pos);
    quicksort(list,low,pos-1);
    quicksort(list,pos+1,high);

}



int main()
{

	   int list[MAX_ELEMENTS];

	     int i = 0;

	     for(i = 0; i < MAX_ELEMENTS; i++ )
            list[i] = rand();

	     printf("The list before sorting is:\n");
	     printlist(list,MAX_ELEMENTS);


	     quicksort(list,0,MAX_ELEMENTS-1);

	      printf("The list after sorting using quicksort algorithm:\n");
	   printlist(list,MAX_ELEMENTS);


	   return 0;
}

I think there is a logical problem with the code( plus i have a suspicion that the recursive call is not working because i am not doing the call correctly). I am not clear on the concept of quicksort. If someone could point out the mistakes in the code it would be appreciated. Thank you

[blackcompe]

void partition(int list[],int low,int high,int pivot)

You never assign anything to pivot. So

int pos=low;
quicksort(list,low,pos-1);

is equivalent to

quicksort(list,low,low-1);

So your not halving the array. The first recursive call sorts an array with basically no elements, and the second calls sorts the full array.

To fix, put return right; at the end of partition and change the function signature as needed. Other than that, your partition function is right, so returning the pivot should be all that's needed. So you should end up with this:

int pivot = partition(list,low,high);
quicksort(list,low,pivot);
quicksort(list,pivot+1,high);

Once your algorithm is correct, try sorting 10⁶ integers in reverse sorted order to see whether your algo is efficient. If not, you need to randomize the sort by choosing a different pivot for each partition. You can simply swap a random element with list[low] before calling partition.

int randomizedPartition(int a[], int low, int high) {
        srand(time(NULL));
        int i = low + (rand()%(high-low)) + 1; //random number from 1 to high
        swap(a, low, i);
        return partition(a, low, high);
}

[sumi1234]

I didn't notice that by assigning low to pivot i was not halving the array. Thanks for pointing that out

I modified the code as you said( return right in partition and int pivot=partition(list,low,high) in the quicksort function) but it is still not running. The while loop and/or recursive call is not terminating on running the program so i only get the screen showing the list before sorting and the program hangs.

//Quicksort program
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>

const int MAX_ELEMENTS = 10;

void swap(int *a,int *B)/>
{
    int temp=*a;
    *a=*b;
    *b=temp;
}

void printlist(int *list,int n)
{
    int i;
    for(i=0;i<n;i++)
        printf("%d\t",list[i]);
}

int partition(int *list,int low,int high)
{
    int x,left,right;
    x=list[low];
    right=high;
    left=low+1;
    while(left<right)
    {
        while((list[left]<=x) && (left<right))
            left++;
        while(list[right]>x)
            right--;
        if(list[left]<list[right])
        {
            swap(&list[right],&list[left]);
            left++;
            right--;
        }
    }
        swap(&list[low],&list[right]);

        return right;

}






int quicksort(int *list,int low,int high)
{
    if(low>high)
        return 0;

    int pivot = partition(list,low,high);

    quicksort(list,low,pivot-1);
    quicksort(list,pivot+1,high);

}



int main()
{

	   int list[MAX_ELEMENTS];

	     int i = 0;

	     for(i = 0; i < MAX_ELEMENTS; i++ )
            list[i] = rand();

	     printf("The list before sorting is:\n");
	     printlist(list,MAX_ELEMENTS);


	     quicksort(list,0,MAX_ELEMENTS-1);

	      printf("The list after sorting using quicksort algorithm:\n");
	   printlist(list,MAX_ELEMENTS);


	   return 0;
}

[blackcompe]

When I ran your program it didn't even print the list to be sorted, so that has nothing to do with quicksort, and I noticed you didn't seed the random number generator, using srand.

[sumi1234]

i already tried the code without using rand() .. by taking an array containing 10 numbers as the list to be sorted... but the program still did not work

[blackcompe]

I don't know .......... when I took out the call to quicksort, the list to be sorted printed correctly. But when I call the sort, the list doesn't show, so quicksort is the problem. One problem is

quicksort(list,low,pivot-1);

That should be

quicksort(list,low,pivot);

Also,

int quicksort(int *list,int low,int high)
{
    if(low>high)
        return 0;

should be

int quicksort(int *list,int low,int high)
{
    if(low>=high)
        return 0;

If you put a debug statement in the outer while loop in partition, you'll see that it's an infinite loop.

And here

if(list[left]<list[right]) {
            swap(&list[right],&list[left]);
            left++;
            right--;
        }

You don't want to test if list[left] < list[right]. You want to test that the less than and greater than regions haven't overlapped.

if(left<right) {
            swap(&list[right],&list[left]);
            left++;
            right--;
        }

After those fixes your sort will work. Just to verify so, you might want to run a few hundred tests on large inputs and create a function isSorted(int*) for your tests.

Also, if your calling rand, you need to call srand(time(NULL)) from <time.h>.

This post has been edited by blackcompe: 07 November 2011 - 02:40 PM

[jimblumberg]

I would recommend that you get the program to run with a "fixed" array. Once you get the program to work then you can test further by using a "random" array.

One thing you may want to do is in your printlist function is to flush the output buffer so you can see the array printed out. You can just add a printf("\n"); before the function returns.

All of my testing is done using a fixed array of: int list[] = {3,6,78,23,1,7,33,22,12,87}; .

Next you should run this program through your debugger. With this input you should find that you have an endless loop inside your partition function.

I think you should review the quicksort algorithm.

Jim

[sumi1234]

blackcompe, on 07 November 2011 - 02:38 PM, said:

I don't know .......... when I took out the call to quicksort, the list to be sorted printed correctly. But when I call the sort, the list doesn't show, so quicksort is the problem. One problem is

quicksort(list,low,pivot-1);

That should be

quicksort(list,low,pivot);

Also,

int quicksort(int *list,int low,int high)
{
    if(low>high)
        return 0;

should be

int quicksort(int *list,int low,int high)
{
    if(low>=high)
        return 0;

If you put a debug statement in the outer while loop in partition, you'll see that it's an infinite loop.

And here

if(list[left]<list[right]) {
            swap(&list[right],&list[left]);
            left++;
            right--;
        }

You don't want to test if list[left] < list[right]. You want to test that the less than and greater than regions haven't overlapped.

if(left<right) {
            swap(&list[right],&list[left]);
            left++;
            right--;
        }

After those fixes your sort will work. Just to verify so, you might want to run a few hundred tests on large inputs and create a function isSorted(int*) for your tests.

Also, if your calling rand, you need to call srand(time(NULL)) from <time.h>.

Thank you for the help. I was finally able to get the program to work .. had to change

right=low+1[code] to 

right=low[/code](which was causing the infinite while loop)

[blackcompe]

No problem.

Quote

Thank you for the help. I was finally able to get the program to work .. had to change right=low+1 to

right=low

(which was causing the infinite while loop)

That's interesting. That's not how it's traditionally done. right should point to the end of the array and left to the beginning.

If you have a working solution ... great. I just did some testing on the quicksort code I tried fixing for you yesterday and it failed a lot of sorts. I briefly checked the results and assumed it was correct. If you want to test your solution insert your quicksort and partition functions into the following code and you should get all 0's for the output.

#include<stdio.h>
#include<stdlib.h>
#include<time.h>

void swap(int *a, int *B)/>
{
    int temp=*a;
    *a=*b;
    *b=temp;
}

void printlist(int *list,int n)
{
    int i;
    for(i=0; i<n; i++)
        printf("%d\n",list[i]);
}

int partition(int *list,int low,int high)
{
//your impl
}

int quicksort(int *list,int low,int high)
{
//your impl
}

int isSorted(int* list, int size) {
    int i;
    for(i = 0; i < size-1; i++)
        if(list[i] > list[i+1])
            return -1;
    return 0;
}

void test(int size, int debug)
{
    int list[size];

    int i;
    for(i = 0; i < size; i++ )
        list[i] = rand();

    quicksort(list,0,size-1);

    if(debug)
        printlist(list, size);

    printf("Is sorted = %d\n\n", isSorted(list, size));
}

int main()
{
    int numTests = 10;
    int inputSize = 1000000;
    int debug = 0; //1 to output list elements, 0 otherwise

    srand(time(NULL));
    for(int i = 0; i < numTests; i++)
        test(inputSize, debug);
    return 0;
}

This post has been edited by blackcompe: 08 November 2011 - 01:50 PM

[sumi1234]

blackcompe, on 08 November 2011 - 01:46 PM, said:

No problem.

Quote

Thank you for the help. I was finally able to get the program to work .. had to change right=low+1 to

right=low

(which was causing the infinite while loop)

That's interesting. That's not how it's traditionally done. right should point to the end of the array and left to the beginning.

If you have a working solution ... great. I just did some testing on the quicksort code I tried fixing for you yesterday and it failed a lot of sorts. I briefly checked the results and assumed it was correct. If you want to test your solution insert your quicksort and partition functions into the following code and you should get all 0's for the output.

#include<stdio.h>
#include<stdlib.h>
#include<time.h>

void swap(int *a, int *B)/>
{
    int temp=*a;
    *a=*b;
    *b=temp;
}

void printlist(int *list,int n)
{
    int i;
    for(i=0; i<n; i++)
        printf("%d\n",list[i]);
}

int partition(int *list,int low,int high)
{
//your impl
}

int quicksort(int *list,int low,int high)
{
//your impl
}

int isSorted(int* list, int size) {
    int i;
    for(i = 0; i < size-1; i++)
        if(list[i] > list[i+1])
            return -1;
    return 0;
}

void test(int size, int debug)
{
    int list[size];

    int i;
    for(i = 0; i < size; i++ )
        list[i] = rand();

    quicksort(list,0,size-1);

    if(debug)
        printlist(list, size);

    printf("Is sorted = %d\n\n", isSorted(list, size));
}

int main()
{
    int numTests = 10;
    int inputSize = 1000000;
    int debug = 0; //1 to output list elements, 0 otherwise

    srand(time(NULL));
    for(int i = 0; i < numTests; i++)
        test(inputSize, debug);
    return 0;
}

I was following the conventional method only ..... what i meant was that i changed

left=low+1

to

left=low

(Had a bit of a typo) ..

When i tried to run the test program that you provided using my implementation of partition and quicksort functions i got the stack overflow message. How can I fix that??

[jimblumberg]

Quote

When i tried to run the test program that you provided using my implementation of partition and quicksort functions i got the stack overflow message. How can I fix that??

Post the code where you tried the "test program" with your implementation. Post the complete compilable program.

Jim

[sumi1234]

jimblumberg, on 09 November 2011 - 09:38 AM, said:

Quote

When i tried to run the test program that you provided using my implementation of partition and quicksort functions i got the stack overflow message. How can I fix that??

Post the code where you tried the "test program" with your implementation. Post the complete compilable program.

Jim

#include<stdio.h>
#include<stdlib.h>
#include<time.h>

void swap(int *a, int *B)/>
{
    int temp=*a;
    *a=*b;
    *b=temp;
}

void printlist(int *list,int n)
{
    int i;
    for(i=0; i<n; i++)
        printf("%d\n",list[i]);
}

int partition(int *list,int low,int high)
{
	 int x,left,right;
	 x=list[low];
	 right=high;
	 left=low;
	 while(left<right)
	 {
		  while((list[left]<=x) && (left<right))
				left++;
		  while(list[right]>x)
				right--;
		  if(left<right)
		  {
				swap(&list[right],&list[left]);
				left++;
				right--;
		  }

	 }
		  swap(&list[low],&list[right]);

		  return right;

}






int quicksort(int *list,int low,int high)
{
	 if(low>=high)
		  return 0;

	 int pivot = partition(list,low,high);

	 quicksort(list,low,pivot);
	 quicksort(list,pivot+1,high);
	 return 0;
}
int isSorted(int* list, int size) {
    int i;
    for(i = 0; i < size-1; i++)
        if(list[i] > list[i+1])
            return -1;
    return 0;
}

void test(int size, int debug)
{
    int list[size];

    int i;
    for(i = 0; i < size; i++ )
        list[i] = rand();

    quicksort(list,0,size-1);

    if(debug)
        printlist(list, size);

    printf("Is sorted = %d\n\n", isSorted(list, size));
}

int main()
{
    int numTests = 10;
    int inputSize = 1000000;
    int debug = 0; //1 to output list elements, 0 otherwise

    srand(time(NULL));
    for(int i = 0; i < numTests; i++)
        test(inputSize, debug);
    return 0;
}

[blackcompe]

By decreasing the inputSize to 10⁴ (for me), the overflow stops. I'm surprised you found out that it was an overflow error, GCC just threw a seg fault. You have to randomize the choice of the pivot (see my earlier posts). If you get a large input that's in an unfavorable order, your sort will degrade towards n² runtime and result in a crap load of recursive calls, which cause the stack overflow error. You can immediately test that by sorting elements in reverse sorted order.

But even after decreasing the inputSize, each test failed, so your sort logic is wrong. quicksort() is correct, so partition() is the problem. In partition() you have:

 if(left<right) {
            swap(&list[right],&list[left]);
            left++;
            right--;
        }

You shouldn't be extending the left and right regions after a swap. When you loop around again they will be extended. Remove left++ and right--;. After that, randomize the sort and try bigger inputs.

This post has been edited by blackcompe: 09 November 2011 - 03:01 PM

[Karel-Lodewijk]

Implementing an in-place quicksort like you are trying to do is indeed really tricky. If it is not part of the requirements, consider a quicksort that is not in place it's actually really easy. In pseudo-code

quicksort(list) {
    choose pivot
    
    create a new list of all elements < pivot
    call quicksort on that list

    create a list of all elements == pivot

    create a new list of all elements > pivot
    call quicksort on that list

    now concatenate those 3 lists and return
}

This post has been edited by Karel-Lodewijk: 09 November 2011 - 05:53 PM

[sumi1234]

blackcompe, on 09 November 2011 - 02:56 PM, said:

By decreasing the inputSize to 10⁴ (for me), the overflow stops. I'm surprised you found out that it was an overflow error, GCC just threw a seg fault. You have to randomize the choice of the pivot (see my earlier posts). If you get a large input that's in an unfavorable order, your sort will degrade towards n² runtime and result in a crap load of recursive calls, which cause the stack overflow error. You can immediately test that by sorting elements in reverse sorted order.

But even after decreasing the inputSize, each test failed, so your sort logic is wrong. quicksort() is correct, so partition() is the problem. In partition() you have:

 if(left<right) {
            swap(&list[right],&list[left]);
            left++;
            right--;
        }

You shouldn't be extending the left and right regions after a swap. When you loop around again they will be extended. Remove left++ and right--;. After that, randomize the sort and try bigger inputs.

i was wondering if you could explain how to randomize the sort(by randomizing the pivot one ach call to partition).. i read your previous post on it but could not get it ... thank you