1 Replies - 184 Views - Last Post: 08 February 2013 - 03:14 PM Rate Topic: -----

#1 axnjxn  Icon User is offline

  • D.I.C Head

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

Randomized Select is not sorting the array

Posted 08 February 2013 - 03:12 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: Randomized Select is not sorting the array

#2 jimblumberg  Icon User is online

  • member icon


Reputation: 4003
  • View blog
  • Posts: 12,351
  • Joined: 25-December 09

Re: Randomized Select is not sorting the array

Posted 08 February 2013 - 03:14 PM

Duplicate post, closed. See this topic: Quicksort

Jim
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1