QuickSort - Stack Overflow when keys are not randomized

  • (2 Pages)
  • +
  • 1
  • 2

25 Replies - 2598 Views - Last Post: 08 February 2013 - 03:06 PM Rate Topic: -----

#16 Adak  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 331
  • View blog
  • Posts: 1,168
  • Joined: 01-April 11

Re: QuickSort - Stack Overflow when keys are not randomized

Posted 07 February 2013 - 08:54 AM

Not a perfect answer, but a much better one:

This is the smartest stack handler in Quicksort that I could find.

I moved the stack size back to the default (which I believe is 1 MB), and it passed every input type test up to 1,234,567 EXCEPT descending - crashed on that one, even at 12,3456.

All this testing was with doubles. Times of the runs are included with the code, and swing dramatically. This program is pretty close to what your instructor had given you, in it's overall design. (it moves the pivot, etc.).


#include <stdio.h>
#include <stdlib.h>
#include <time.h>
/* from: The Practice of Programming (pp: 32-34)
 *   by: Brian W. Kernighan and Rob Pike
 */
/* swap: interchange v[i] and v[j] */
void swap( double v[], int i, int j )
{
  double tmp;
  tmp = v[i];
  v[i] = v[j];
  v[j] = tmp;
}
/* quicksort: sort v[0]..v[n-1] into increasing
 * order
 */
void quicksort( double v[], int n )
{
  int i = 0, last = 0;
  if ( n <= 1 )              /* nothing to do */
    return;
//not moving the pivot, means that v[0] becomes the pivot, with every recursive call
  //swap( v, 0, rand() % n );  // move pivot elem 
                                //to v[0] 
  for ( i = 1; i < n; i++ )  /* partition */
    if ( v[i] < v[0] )
      swap( v, ++last, i );
  swap( v, 0, last );        /* restore pivot */
  quicksort( v, last );      /* sort smaller
                                values */
  quicksort( v+last+1, n-last-1 );  /* sort larger
                                       values */
}
void print_array( const double array[], int elems )
{
   int i;
   for ( i = 0; i < elems; i++ )
      printf("%15.2f ", array[i] );
   printf("\n");
}
//1234567 random: 0.2 seconds, all ascending: 903 seconds, all descending (NUM==12345):0.2 seconds
//1234567 all equal: 906 seconds. 
#define NUM 1234567  
int main( void )
{
   double *arr=malloc(NUM * sizeof(double));
   if(!arr) {
      printf("Error allocting memory!\n");
      return 1;
   }
   for(int i=0;i<NUM;i++) {
      //arr[i]= rand() % 10000+1;  //all random
      //arr[i]=i*3.14159265358979; //all ascending 
      //arr[i]=(NUM-i+1)*3.14159265358979; //all descending
      arr[i]= NUM+0.12;  //all equal
      
   }
   /* commented out to aid in predictability
   * srand( (unsigned int) time(NULL) ); */
   //print_array(arr, NUM);
   //getchar();
   clock_t timer=clock();
   quicksort(arr, NUM);
   timer=(clock()-timer);
   print_array(arr, NUM);
   printf("Elapsed time: %f\n",(double) timer/CLOCKS_PER_SEC);
   return EXIT_SUCCESS;
}




If you want to make it work, even with a bad pivot, maybe simply swap some array values. Even swapping 100 random array[random index] numbers, would do wonders for a sort of 50,000 numbers, imo.

Thanks for the interesting thread. ;)/>/> Let me know how it works out.

This post has been edited by Adak: 07 February 2013 - 08:57 AM

Was This Post Helpful? 1
  • +
  • -

#17 mojo666  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 352
  • View blog
  • Posts: 770
  • Joined: 27-June 09

Re: QuickSort - Stack Overflow when keys are not randomized

Posted 07 February 2013 - 10:43 AM

View PostAdak, on 07 February 2013 - 03:54 PM, said:

If you want to make it work, even with a bad pivot, maybe simply swap some array values. Even swapping 100 random array[random index] numbers, would do wonders for a sort of 50,000 numbers, imo.


Do you suppose that instead of bashing quick sort, the point of this assignment was for students to figure out that they should shuffle the input before sorting in order to ensure that quicksort always gets acceptable run times?
Was This Post Helpful? 2
  • +
  • -

#18 Adak  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 331
  • View blog
  • Posts: 1,168
  • Joined: 01-April 11

Re: QuickSort - Stack Overflow when keys are not randomized

Posted 07 February 2013 - 11:03 AM

Could be. Requiring doubles for the data type (eating up more stack memory), and goofy pivot selections, leave me wondering.

Did you hear about the professor who created a Quicksort Killer program? He made a "scout" program to run first, that is able to analyze the stack on another system, and tell if it's using Quicksort on sorting requests. Also, it is able to figure out how the pivot is being selected, by analyzing the stack usage.

Then it generates a killer data file that brings Quicksort either to a crash, or a serious cripple.

I thought that was just wickedly brilliant.
Was This Post Helpful? 1
  • +
  • -

#19 axnjxn  Icon User is offline

  • D.I.C Head

Reputation: 14
  • View blog
  • Posts: 144
  • Joined: 04-February 12

Re: QuickSort - Stack Overflow when keys are not randomized

Posted 07 February 2013 - 11:24 AM

Damn it. I don't know what's wrong. Do I have a shitty compiler? I copy pasted that code (what you just posted) into its own file (named test.c) and compiled it with cc -std=c99 test.c. Then I ran it using the ascending input sequence and it's crashing. Tried the all equivalent one and it crashed for me as well. It worked for the random sequence and fast. But other than that, I don't know what's wrong with my ish. grr...

EDIT
I actually went back to the original function that I had posted and used your suggestion of randomizing the inputs. I actually did this for all inputs to make it "fair" (if you will). Even including an n-sized randomizing in the timing, it was still pretty damn fast and no crashes so far. HOWEVER, the all equivalent input is simply impossible. It won't even run for an input of 44000. Obviously, randomizing the keys won't do anything in this case. I'm really not sure what I'm supposed to do in this circumstance. I will consult my classmates and the professor tonight and (once again ;) ) get back to you guys.

This post has been edited by axnjxn: 07 February 2013 - 11:46 AM

Was This Post Helpful? 0
  • +
  • -

#20 mojo666  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 352
  • View blog
  • Posts: 770
  • Joined: 27-June 09

Re: QuickSort - Stack Overflow when keys are not randomized

Posted 07 February 2013 - 01:31 PM

Quote

HOWEVER, the all equivalent input is simply impossible.


You will have to add a seperate case for when the compared values are equal. Right now, you have one case for when the element is less than pivot.
if ( v[i] < v[0] )
     swap( v, ++last, i );  


Every value that is greater or equal is stored on the right side. So, when every value is the same, all elements are stored in the right half for every recursive call. You need to add logic to store equal values on the left side half of the time and keep them on the right the other half of the time.

This post has been edited by mojo666: 07 February 2013 - 01:32 PM

Was This Post Helpful? 2
  • +
  • -

#21 axnjxn  Icon User is offline

  • D.I.C Head

Reputation: 14
  • View blog
  • Posts: 144
  • Joined: 04-February 12

Re: QuickSort - Stack Overflow when keys are not randomized

Posted 07 February 2013 - 02:15 PM

AMAZING! Thank you so much, mojo666. I was completely overlooking that simple (and embarrassingly obvious) fact. I utilized the following code to make sure only half of any equal values were on either side of the pivot and it works! Not only that, but it's running faster now.

short equalitySwitch = 0;
for (int currentIndex = p; currentIndex <= r - 1; currentIndex++){	
	if(A[currentIndex] < pivot){
		//increment the counter & perform swap
		i++;
		swap(A[i], A[currentIndex]);			
	}else if(A[currentIndex] == pivot){
		if(equalitySwitch == 0){
			i++;
			swap(A[i], A[currentIndex]);
			equalitySwitch = 1;
		}else{
			equalitySwitch = 0;
		}
	}
}



Thank you guys so much. I was stumped. I wish I could give you more than 1 rep point per post!

This post has been edited by axnjxn: 07 February 2013 - 02:15 PM

Was This Post Helpful? 1
  • +
  • -

#22 Adak  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 331
  • View blog
  • Posts: 1,168
  • Joined: 01-April 11

Re: QuickSort - Stack Overflow when keys are not randomized

Posted 07 February 2013 - 02:44 PM

Well done, mojo666 and axnjxn!
Was This Post Helpful? 0
  • +
  • -

#23 mojo666  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 352
  • View blog
  • Posts: 770
  • Joined: 27-June 09

Re: QuickSort - Stack Overflow when keys are not randomized

Posted 07 February 2013 - 02:56 PM

No problem, axnjxn. I'm glad I could help.

View PostAdak, on 07 February 2013 - 06:03 PM, said:

Did you hear about the professor who created a Quicksort Killer program? He made a "scout" program to run first, that is able to analyze the stack on another system, and tell if it's using Quicksort on sorting requests. Also, it is able to figure out how the pivot is being selected, by analyzing the stack usage.

Then it generates a killer data file that brings Quicksort either to a crash, or a serious cripple.

I thought that was just wickedly brilliant.


I googled this and the technique is very clever. Generalized quicksorts allow a compare algorithm to be passed along with the data in order to be able to quicksort custom objects, so the programmer just writes the compare function to not only compare elements, but also track the results and generate the killer data as it identifies the candidate pivots. An example is at the end of this paper.
Was This Post Helpful? 0
  • +
  • -

#24 axnjxn  Icon User is offline

  • D.I.C Head

Reputation: 14
  • View blog
  • Posts: 144
  • Joined: 04-February 12

Re: QuickSort - Stack Overflow when keys are not randomized

Posted 08 February 2013 - 11:18 AM

I just wanted to tell everyone that my professor actually covered this exact problem in class last night. He actually made sure to point out the fact that randomizing the input is needed on the worst case inputs when using deterministic quicksort (ie a non-random pivot). We went forth proving why this was so. In the end, he didn't even expect us to find this out on our own. So, in this case, it would have paid off to be a procrastinator!

Thanks again. This helped me understand the subtleties of quicksort.
Was This Post Helpful? 0
  • +
  • -

#25 Adak  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 331
  • View blog
  • Posts: 1,168
  • Joined: 01-April 11

Re: QuickSort - Stack Overflow when keys are not randomized

Posted 08 February 2013 - 11:45 AM

Thanks for the feedback. I did add some code to my optimized Quicksort to help it deal with the non-random input.

I had to give up on the "better" Quicksort I posted - it was fine at small and medium size arrays - but it floundered badly at huge arrays of integers.

This is with int's, not doubles, but the improvements in the Optimized Quicksort with non-random input, is very nice, imo.

Quote

Sorting 12,345,678 integers, initially in random order. The first 8 numbers:
6731 9522 7943 510 4771 730 9743 2342
Optimized Quicksort: 44171065 swaps in 0.9210 seconds
Recursive Quicksort: 97980669 swaps in 0.9980 seconds
Shell sort: 793752229 swaps in 3.2450 seconds


Sorting 12,345,678 integers, initially in ascending order. The first 8 numbers:
0 3 6 9 12 15 18 21
Optimized Quicksort: 0 swaps in 0.1560 seconds
Recursive Quicksort: 8151374 swaps in 0.2500 seconds
Shell sort: 0 swaps in 0.3280 seconds


Sorting 12,345,678 integers, initially in descending order. The first 8 numbers:
38785088 38785085 38785081 38785078 38785075 38785072 38785069 38785066
Optimized Quicksort: 6172839 swaps in 0.1710 seconds
Recursive Quicksort: 14324213 swaps in 0.2650 seconds
Shell sort: 137328821 swaps in 0.6240 seconds


Sorting 12,345,678 integers, initially in equal order. The first 8 numbers:
1234 1234 1234 1234 1234 1234 1234 1234
Optimized Quicksort: 0 swaps in 0.1870 seconds
Recursive Quicksort: 140441119 swaps in 0.5780 seconds
Shell sort: 0 swaps in 0.3280 seconds


I love that zero swaps on equal keys. ;)/>/>

This post has been edited by Adak: 08 February 2013 - 11:46 AM

Was This Post Helpful? 0
  • +
  • -

#26 axnjxn  Icon User is offline

  • D.I.C Head

Reputation: 14
  • View blog
  • Posts: 144
  • Joined: 04-February 12

Re: QuickSort - Stack Overflow when keys are not randomized

Posted 08 February 2013 - 03:06 PM

EDITED OUT (mistake)

This post has been edited by axnjxn: 08 February 2013 - 03:12 PM

Was This Post Helpful? 0
  • +
  • -

  • (2 Pages)
  • +
  • 1
  • 2