Pertanyaan Pengulangan tak terbatas dalam JavaScript quicksort?


Ini dia quicksort kode yang saya tulis. Fungsi ini tidak berfungsi karena tidak dapat menjangkau kotak dasar. Jika saya log pivot, r dan l ke konsol, mereka tetap sama tidak peduli berapa kali fungsi semacam itu disebut. Jadi saya bertanya-tanya apakah argumennya l, r tidak benar-benar dimasukkan ke dalam fungsi sebagai data. Kenapa ini terjadi?

function sort(data){
    if(data.length < 2){
        return data;
    }
    else{
        var l = [];
        var r = [];
        var pivot = parseInt(data.length/2);
        for(i=0; i<data.length; i++){
            if(data[i] > data[pivot]){
                r.push(data[i]);
            }
            else{
                l.push(data[i]);
            }
        }
        return sort(l).concat(sort(r));
    }
}

31
2018-02-07 21:09


asal


Jawaban:


Saya pikir bahwa masalah di sini adalah bahwa langkah partisi Anda tidak selalu mengecilkan array input. Sebagai contoh, mari kita telusuri apa yang terjadi jika Anda mencoba menyortir [1, 2]. Dalam hal ini, elemen pivot Anda akan menjadi elemen 2. Karena 1> 2 salah, 1 ditambahkan ke daftar l. Karena 2> 2 salah, 2 ditambahkan ke daftar l. Akibatnya, panggilan rekursif Anda pada daftar l akan memiliki argumen yang persis sama dengan panggilan asli Anda, menyebabkan rekursi tak terbatas.

Untuk memperbaikinya, cobalah membagi masukan ke dalam tiga daftar - satu dari nilai yang lebih kecil, satu dari nilai yang sama, dan satu dari nilai yang lebih besar. Kode ini ditampilkan di sini:

function sort(data){
  if (data.length < 2){
    return data;
  } else {
    var l = [];
    var r = [];
    var e = [];
    var i = 0;
    var pivot = (data.length / 2) | 0;

    for(i = 0; i < data.length; i++) {
      if (data[i] > data[pivot]) {
        r.push(data[i]);
      } else if (data[i] < data[pivot]) {
        l.push(data[i]);
      } else {
        e.push(data[i]);
      }
    }  
    return sort(l).concat(e, sort(r)); 
  }
}

Versi baru ini secara eksplisit mengelompokkan elemen yang sama ke dalam daftar mereka sendiri, sehingga mereka tidak secara rekursif diurutkan berdasarkan salah satu panggilan rekursif. Ini juga dengan anggun menangani elemen duplikat.

Semoga ini membantu!


327
2018-02-07 21:20



Jika Anda memilih nilai terbesar dari array sebagai elemen pivot, maka semua nilai data akan berakhir di larik l dan tidak satu pun di r. Dengan demikian akan membuat rekursi tidak pernah berhenti (dan pertahankan l, r dan pivot pada nilai yang sama). Kecuali ini adalah latihan otak, menggunakan data.sort() harus melakukan pekerjaan yang lebih baik. ;)


1
2018-02-07 21:25



JavaScript melewatkan objek berdasarkan referensi (array adalah objek juga). Jika Anda ingin melewatkannya berdasarkan nilai, Anda perlu menggunakan fungsi sambatan seperti yang dijelaskan sini.

Perhatikan bahwa ini akan membuat banyak salinan data Anda. Anda mungkin ingin menggunakan fungsi sortir asli ().


0
2018-02-07 21:23