[axnjxn]

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.

[jimblumberg]

Duplicate post, closed. See this topic: Quicksort

Jim