2 Replies - 387 Views - Last Post: 09 February 2013 - 10:43 AM Rate Topic: -----

#1 axnjxn  Icon User is offline

  • D.I.C Head

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

NOT the same question: Randomized SELECTION not sorting

Posted 08 February 2013 - 03:21 PM

Instructions from professor are to implement the randomized quicksort that we find directly in our textbook. However, upon doing this, the output can be seen to be UNsorted. Often, it is almost sorted. Here's the book's pseudo code followed by my code. For some demented reason, the book uses PASCAL type arrays (ie A[1..n] instead of A[0..n-1]). So, some of my code will reflect that (such as making the argument for 'n' in the initial function call to be n-1).

Pseudo code from the book
RANDOMIZED-SELECT(A, p, r, i)
   if p == r
      return A[p]
   q = RANDOMIZED-PARTITION(A, p, r)
   k = q - p + 1
   if i == k
      return A[q]
   elseif i < k
   return RANDOMIZED-SELECT(A, p, q-1, i)
   else return RANDOMIZED-SELECT(A, q+1, r, i-k)

RANDOMIZED-PARTITION(A, p, r)
   i = RANDOM(p, r)
   exchange A[r] with A[i]
   return PARTITION(A, p, r)

PARTITION(A, p, r)
   x = A[r]
   i = p - 1
   for j = p to r - 1
      if A[j] <= x
         i = i + 1
         exchange A[i] with A[j]
   exchange A[i+1] with A[r]
   return i+1



My Code
Initial call: double result = qselect(A, 0, n-1, stat);
double qselect(double *A, const int &lo, const int &hi, const int &stat){
	if(lo == hi) return A[lo];
	
	int pivotIndex = randomPartition(A, lo, hi);
	int k = pivotIndex - lo + 1;
	if(stat == k){
		return A[pivotIndex];
	}
	else if(stat < k){
		return qselect(A, lo, pivotIndex - 1, stat);
	}
	else{
		return qselect(A, pivotIndex + 1, hi, stat - k);
	}
}

int randomPartition(double *A, const int &p, const int &r){
	
	srand(time(NULL));
	int randIndex = rand() % (r - p) + p;
	swap(A[randIndex], A[r]);
	
	double pivot = A[r];
	
	int i = p - 1;
	
	for (int j = p; j <= r - 1; j++){	
		if(A[j] < pivot){
			i++;
			swap(A[i], A[j]);			
		}
	}
	swap(A[i + 1], A[r]);
	return (i + 1);
}


As far as I can tell, it mirrors the pseudocode perfectly. In fact, the "randomized partition" function is exactly the same as Randomized Quicksort (which, if you read my last post, you know we got it to work perfectly). This leads me to believe the problem lies somewhere in the qselect code. I can't see it, though. Maybe another pair of eyes can.

Is This A Good Question/Topic? 0
  • +

Replies To: NOT the same question: Randomized SELECTION not sorting

#2 Adak  Icon User is offline

  • D.I.C Lover
  • member icon

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

Re: NOT the same question: Randomized SELECTION not sorting

Posted 09 February 2013 - 10:19 AM

I see "qselect" in the text, and I'm wondering whether this is supposed to be Quickselect or not? Quickselect is based on a lot of the same algorithm as Quicksort, and was created by the same programmer (Hoare).

Quickselect does not sort the entire array:
http://en.wikipedia....ction_algorithm
Was This Post Helpful? 1
  • +
  • -

#3 axnjxn  Icon User is offline

  • D.I.C Head

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

Re: NOT the same question: Randomized SELECTION not sorting

Posted 09 February 2013 - 10:43 AM

Yeah. That was my misconception. I realized this after running duplicate arrays through quickselect and then quicksort the duplicate & return the chosen stat. When they were equal after 10 runs of 1 million+ doubles, I realized that quickselect doesn't actually fully sort the array. <Blushing>

Thanks, Adak.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1