randomized_quicksort [英] randomized_quicksort
问题描述
这code没有告诉我任何输出
this code does not show me any output
#include <cstdlib>
#include <iostream>
using namespace std;
int partition(int a[], int left, int right) {
int i = left;
int j = right;
int temp;
int pivot = a[left];
while(i <= j) {
while(a[i] < pivot)
i++;
while(a[j] > pivot)
j--;
if(i>j) break;
if (i<j){
temp = a[i];
a[i] = a[j];
a[j] = temp;
i++;
j--;
}
}
return i;
}
int randomized_partition(int a[], int left, int right){
int t = left + rand() % (right - left + 1);
std::swap(a[right], a[t]);
return partition(a, left, right);
}
void randomized_quicksort(int a[], int l, int r){
if(l> = r) return;
int q = randomized_partition(a, l, r);
randomized_quicksort(a, l, q-1);
randomized_quicksort(a, q+1, r);
}
int main(){
int a[] = {12, 6, 4, 7, 9, 10, 11, 14, 13, 19, 18, 21, 20};
int n = sizeof(a) / sizeof(n);
randomized_quicksort(a, 0, n-1);
for (int i = 0; i < n; i++){
cout << a[i] << " " << endl;
}
return 0;
}
这是randomized_quicksort从引进算法第三版,请您帮
it is randomized_quicksort from introduction in algorithms third edition and please help
推荐答案
该计划被卡在调用分区(2,4)
。数组的相关部分是 6,9,7
的时间,所以透视
获取初始化为 6
。
The program gets stuck in the call to partition(2, 4)
. The relevant part of the array is 6, 9, 7
at the time, so pivot
get initialized to 6
.
您进入主,而
循环,而我
循环立即终止,因为它总是在第一时间各地,因为 A [1] ==透视
。所以,你输入Ĵ
循环,执行两次,因为 7
和 9
都比透视
,这是更大的 6
。该Ĵ
循环结束时,Ĵ== 2
,因为 A [J] ==透视
。
You enter the main while
loop, and the i
loop terminates immediately, as it always does the first time around, because a[i] == pivot
. So you enter the j
loop, which executes twice because 7
and 9
are both greater than pivot
, which is still 6
. The j
loop terminates when j == 2
because a[j] == pivot
.
移动以来,第一个条件是假
,因为我
不大于更大Ĵ
。第二个条件是假
,因为我
不大于Ĵ少
。这标志着主,而
循环结束,所以我们检查循环的条件,并发现它的真
,因为我
等于Ĵ
。我们没有改变任何数组元素的值,因此内,而
回路永远不会再运行,并且条件语句仍然假
。你陷在一个无限循环,永远不会取得任何进展。
Moving along, the first conditional is false
because i
is not greater than j
. The second conditional is false
because i
is not less than j
. That marks the end of the main while
loop, so we check the loop's condition and find that it's true
because i
is equal to j
. We haven't changed any of the array elements' values, so the inner while
loops never run again, and the conditionals remain false
. You get stuck in an infinite loop, never making any progress.
快来看看你的教科书。无论是有书中的错误,或者你犯了一个错误抄录吧。
Take a closer look at your textbook. Either there's a mistake in the book, or you made a mistake transcribing it.
这篇关于randomized_quicksort的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!