如果有重复值，则快速排序无限循环 [英] Quicksort infinite loop if there are repeating values

问题描述

我有一个快速排序程序，工作伟大，直到我尝试排序具有重复数字的数组。程序陷入无限循环。我相信这发生在 While（lower< upper）代码块中。

 code> void quickSort（int array []，int size）{
 if（size< 2）return; 
 
 int pivot，lower，upper，temp; 
 
 //设置第一个和最后一个元素的缩进
 lower = 0; 
 upper = size  -  1; 
 
 //随机选择枢轴元素
 pivot = array [rand（）％（size）]; 
 
 while（lower< upper）{
 // Lower必须是数字<而不是一个数字> = pivot 
 while（array [lower]< pivot）{
 lower ++; 
} 
 while（array [upper]> pivot）{
 upper--; 
} 
 
 //上下交换
 temp = array [lower]; 
 array [lower] = array [upper]; 
 array [upper] = temp; 
} 
 
 //递归地对数组的两个分区重复过去的操作
 quickSort（array，lower）; 
 quickSort（& array [lower + 1]，size-lower-1）; 
} 
  

解决方案

/ p>

从维基百科，就地快速排序的伪代码如下：

（不是说他们应该盲目信任）

  function quicksort（array）
如果length（array）> 1 
 pivot：=选择数组中的任何元素
 left：=数组的第一个索引
 right：=数组的最后一个索引
 while left right right 
 while array [左] pivot 
 left：= left + 1 
 while array [right]> pivot 
 right：= right  -  1 
如果left≤right 
 swap数组[left] with数组[right] 
 left：= left + 1 
 right： right-1 
 quicksort（从第一个索引到右侧的数组）
 quicksort（数组从左到上索引）
  

因此，您看到它与您的算法非常相似，只需稍加修改。

  while < = upper）{
  

此外，只有当

您的代码在递归调用中有所不同：

  quicksort（数组从第一个索引到右侧）{array [0]到array [upper]} 
 quicksort这是因为现在它已经退出while循环了，因为它已经退出了一个循环。 
  
 #include< iostream> 
 #include< cstdlib> 
 using namespace std; 
 
 void quickSort（int array []，int size）{
 if（size< 2）return; 
 
 int pivot，lower，upper，temp; 
 
 //设置第一个和最后一个元素的缩进
 lower = 0; 
 upper = size  -  1; 
 
 //随机选择枢轴元素
 pivot = array [rand（）％（size）]; 
 
 while（lower< = upper）{
 // Lower必须是数字<而不是一个数字> = pivot 
 while（array [lower]< pivot）{
 lower ++; 
} 
 while（array [upper]> pivot）{
 upper--; 
} 
 
 //交换上下
 if（lower< = upper）{
 temp = array [lower]; 
 array [lower] = array [upper]; 
 array [upper] = temp; 
 lower ++; 
 upper--; 
} 
} 
 
 //递归地对数组的两个分区重复过去的操作
 quickSort（array，upper + 1）; 
 quickSort（& array [lower]，size-lower）; 
} 
 
 int main（）{
 //你的代码在这里
 int myArray [] = {10，9，8，7，7，7， 7，3，2，1}; 
 quickSort（myArray，10）; 
 for（int i = 0; i <10; i ++）
 cout< myArray [i]< ; 
 return 0; 
} 
  
输出：
  1 2 3 7 7 7 7 8 9 10 
  
 
I have a quicksort program that works great until I try to sort an array that has a repeating number. The program gets stuck in an infinite loop. I believe this is happening in the While(lower < upper) block of code.
void quickSort(int array[], int size){
  if(size < 2) return;

  int pivot, lower, upper, temp;

  //Set the indeces for the first and last elements                                 
  lower = 0;
  upper = size - 1;

  //Select pivot element randomly                                                   
  pivot = array[rand() % (size)];                                                                                                     

  while(lower < upper){
    //Lower must be a number < than pivot and upper a number >= pivot               
    while(array[lower] < pivot){
      lower++;
    }
    while(array[upper] > pivot){
      upper--;
    }

    //Swap upper and lower                                                          
    temp = array[lower];
    array[lower] = array[upper];
    array[upper] = temp;
  }

  //Repeat the past actions on the two partitions of the array recursively          
  quickSort(array, lower);
  quickSort(&array[lower+1], size-lower-1);
}

解决方案
EDIT: Code added.

From Wikipedia, the pseudo-code for in-place quicksort is as follows:

(Not saying that they should be trusted blindly)
function quicksort(array)
    if length(array) > 1
        pivot := select any element of array
        left := first index of array
        right := last index of array
        while left ≤ right
            while array[left] < pivot
                left := left + 1
            while array[right] > pivot
                right := right - 1
            if left ≤ right
                swap array[left] with array[right]
                left := left + 1
                right := right - 1
        quicksort(array from first index to right)
        quicksort(array from left to last index)
So you see it is quite similar to your algorithm, with minor modifications.
while(lower <= upper){
Also you need to swap only if lower <= upper and then update the indices.

And your code differs in the recursive calls:
quicksort(array from first index to right) {array[0] to array[upper]}
quicksort(array from left to last index) {array[lower] to array[size-1]}
This is because now that it has exited the while loop, upper is less than lower.

Full working code:
#include <iostream>
#include <cstdlib>
using namespace std;

void quickSort(int array[], int size){
  if(size < 2) return;

  int pivot, lower, upper, temp;

  //Set the indeces for the first and last elements                                 
  lower = 0;
  upper = size - 1;

  //Select pivot element randomly                                                   
  pivot = array[rand() % (size)];                                                                                                     

  while(lower <= upper){
    //Lower must be a number < than pivot and upper a number >= pivot               
    while(array[lower] < pivot){
      lower++;
    }
    while(array[upper] > pivot){
      upper--;
    }

    //Swap upper and lower                                                          
    if ( lower <= upper ) {
        temp = array[lower];
        array[lower] = array[upper];
        array[upper] = temp;
        lower++;
        upper--;
    }
  }

  //Repeat the past actions on the two partitions of the array recursively          
  quickSort(array, upper+1);
  quickSort(&array[lower], size-lower);
}

int main() {
    // your code goes here
    int myArray[] = { 10, 9, 8, 7, 7, 7, 7, 3, 2, 1};
    quickSort( myArray, 10 );
    for ( int i = 0; i < 10; i++ )
        cout << myArray[i] << " ";
    return 0;
}
Output:
1 2 3 7 7 7 7 8 9 10


                        
这篇关于如果有重复值，则快速排序无限循环的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！