Quicksort loop tak terbatas jika ada nilai yang berulang

Saya memiliki program quicksort yang berfungsi dengan baik sampai saya mencoba mengurutkan array yang memiliki nomor berulang. Program ini terjebak dalam putaran tak terbatas. Saya yakin ini terjadi di blok kode While(lower < upper).

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);
}

c++ quicksort
person Kalmar    schedule 03.12.2013    source sumber
comment
Kamu benar. Melihat sekilas kode Anda, mungkin saja tidak ada yang lebih rendah yang dinaikkan atau yang lebih tinggi, yang menghasilkan inf. lingkaran. (menemukan kasus seperti itu mudah yaitu semua nomor diurutkan sama)   -  person gregory561    schedule 03.12.2013
comment
Apa yang terjadi jika ada beberapa contoh nilai pivot? Dua putaran while yang paling dalam tidak akan pernah menyebabkan lower dan upper bertemu. Yang satu harus < pivot dan yang lainnya >= pivot.   -  person Joe Z    schedule 03.12.2013
comment
Komentar Anda tentang hubungan antara atas/bawah dan pivot tidak sesuai dengan kode, jadi mungkin salah satunya salah.   -  person molbdnilo    schedule 03.12.2013
comment
@JoeZ Saya mencobanya tetapi akhirnya mendapatkan kesalahan segmentasi.   -  person Kalmar    schedule 03.12.2013
comment
Anda mungkin juga perlu menguji upper ›= lower di loop while itu.   -  person Joe Z    schedule 03.12.2013
comment
Apa array terkecil yang Anda temukan yang mengatasi bug ini? Apa yang terjadi saat Anda melakukan pengurutan array ini di debugger? Apa yang seharusnya terjadi?   -  person Useless    schedule 03.12.2013

Jawaban (1)


arrow_upward
7
arrow_downward

EDIT: Kode ditambahkan.

Dari Wikipedia, kode semu untuk quicksort di tempat adalah sebagai berikut:
(Bukan berarti mereka harus dipercaya begitu saja)

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)

Jadi Anda melihatnya sangat mirip dengan algoritma Anda, dengan sedikit modifikasi.

while(lower <= upper){

Anda juga perlu menukar hanya jika lower <= upper dan kemudian memperbarui indeks.

Dan kode Anda berbeda dalam panggilan rekursif:

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]}

Hal ini karena sekarang ia telah keluar dari perulangan while, nilai atas lebih kecil daripada nilai bawah.

Kode kerja penuh:

#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;
}

Keluaran:

1 2 3 7 7 7 7 8 9 10
person Abhishek Bansal    schedule 03.12.2013