Bagaimana cara kerja sort () Javascript?

Bagaimana kode berikut mengurutkan array ini dalam urutan numerik?

var array=[25, 8, 7, 41]

array.sort(function(a,b){
  return a - b
})

Saya tahu jika hasil penghitungannya adalah ...

Kurang dari 0 : "a" diurutkan menjadi indeks yang lebih rendah dari "b".
Nol: "a" dan "b" dianggap sama, dan tidak ada penyortiran yang dilakukan.
Lebih dari 0: "b" diurutkan menjadi indeks yang lebih rendah dari "a".

Apakah fungsi callback sortir array dipanggil berkali-kali selama pengurutan?

Jika demikian, saya ingin tahu dua angka mana yang diteruskan ke fungsi setiap kali. Saya berasumsi bahwa yang pertama mengambil "25" (a) dan "8" (b), diikuti oleh "7" (a) dan "41" (b), jadi:

25 (a) - 8 (b) = 17 (lebih besar dari nol, jadi urutkan "b" menjadi indeks yang lebih rendah dari "a"): 8, 25

7 (a) - 41 (b) = -34 (kurang dari nol, jadi urutkan "a" menjadi indeks yang lebih rendah dari "b": 7, 41

Bagaimana kedua kumpulan angka tersebut kemudian diurutkan dalam hubungannya satu sama lain?

Tolong bantu pemula yang kesulitan!

Apakah fungsi callback sortir array dipanggil berkali-kali selama pengurutan?

Iya

Jika demikian, saya ingin tahu dua angka mana yang diteruskan ke fungsi setiap kali

Anda bisa menemukan diri Anda dengan:

array.sort((a,b) => {
  console.log(`comparing ${a},${b}`);
  return a > b ? 1
               : a === b ? 0 
                         : -1;
});

EDIT

Ini adalah hasil yang saya dapatkan:

25,8
25,7
8,7
25,41

Penafsir JavaScript memiliki semacam implementasi algoritma pengurutan yang dibangun di dalamnya. Ini memanggil fungsi perbandingan beberapa kali selama operasi pengurutan. Berapa kali fungsi perbandingan dipanggil bergantung pada algoritme tertentu, data yang akan diurutkan, dan urutannya sebelum pengurutan.

Beberapa algoritme pengurutan berkinerja buruk pada daftar yang sudah diurutkan karena menyebabkan mereka membuat jauh lebih banyak perbandingan daripada dalam kasus biasa. Yang lain menangani dengan baik daftar yang telah disortir sebelumnya, tetapi memiliki kasus lain di mana daftar tersebut dapat "ditipu" agar berkinerja buruk.

Ada banyak algoritme pengurutan yang umum digunakan karena tidak ada algoritme tunggal yang sempurna untuk semua tujuan. Dua yang paling sering digunakan untuk penyortiran generik adalah Quicksort dan merge sort . Quicksort sering kali lebih cepat dari keduanya, tetapi jenis gabungan memiliki beberapa properti bagus yang dapat menjadikannya pilihan keseluruhan yang lebih baik. Merge sort stabil , sedangkan Quicksort tidak. Kedua algoritme dapat diparalelkan, tetapi cara kerja merge sort membuat implementasi paralel lebih efisien, yang lainnya sama.

Penerjemah JavaScript khusus Anda mungkin menggunakan salah satu dari algoritme tersebut atau yang lainnya sama sekali. The ECMAScript standar tidak menentukan algoritma pelaksanaan sesuai harus menggunakan. Bahkan secara eksplisit menolak kebutuhan akan stabilitas.

Pasangan nilai dibandingkan, satu pasang pada satu waktu. Pasangan yang dibandingkan adalah detail implementasi - jangan berasumsi bahwa keduanya akan sama di setiap browser. Callback bisa apa saja (jadi Anda bisa mengurutkan string atau angka Romawi atau apa pun di mana Anda bisa mendapatkan fungsi yang mengembalikan 1,0, -1).

Satu hal yang perlu diingat dengan jenis JavaScript adalah bahwa JavaScript tidak dijamin stabil.

Apakah fungsi callback sortir array dipanggil berkali-kali selama pengurutan?

Ya, begitulah. Callback digunakan untuk membandingkan pasangan elemen dalam larik yang diperlukan untuk menentukan urutannya. Implementasi fungsi perbandingan itu tidak atipikal saat berhadapan dengan urutan numerik. Detail di spesifikasi atau di beberapa situs lain yang lebih mudah dibaca .

Apakah fungsi callback sortir array dipanggil berkali-kali selama pengurutan?

Karena ini adalah jenis perbandingan, dengan N item, fungsi panggilan balik harus dipanggil rata-rata (N * Lg N) kali untuk pengurutan cepat seperti Quicksort . Jika algoritma yang digunakan adalah seperti Bubble Sort , maka fungsi callback akan dipanggil rata-rata (N * N) kali.

Jumlah minimum pemanggilan untuk semacam perbandingan adalah (N-1) dan itu hanya untuk mendeteksi daftar yang sudah diurutkan (yaitu keluar lebih awal di Bubble Sort jika tidak terjadi pertukaran).

Pengetahuan Mendalam

Jika hasilnya negatif a disortir sebelum b.

Jika hasilnya positif b disortir sebelum a.

Jika hasilnya 0, tidak ada perubahan yang dilakukan dengan urutan kedua nilai tersebut.

CATATAN:

Kode ini adalah tampilan di dalam metode sortir selangkah demi selangkah.

KELUARAN:

let arr = [90, 1, 20, 14, 3, 55];
var sortRes = [];
var copy = arr.slice();		//create duplicate array
var inc = 0;	//inc meant increment
copy.sort((a, b) => {
	sortRes[inc] = [ a, b, a-b ];
	inc += 1;
	return a - b;
});
var p = 0;
for (var i = 0; i < inc; i++) {
	copy = arr.slice();
	copy.sort((a, b) => {
		p += 1;
		if (p <= i ) {
			return a - b;
		}
		else{
			return false;
		}
	});
	p = 0;
	console.log(copy +' \t a: '+ sortRes[i][0] +' \tb: '+ sortRes[i][1] +'\tTotal: '+ sortRes[i][2]);
}

jalankan kode ini. Anda dapat melihat proses penyortiran langkah demi langkah yang tepat dari awal hingga akhir.

var array=[25, 8, 7, 41]
var count = 1;
array.sort( (a,b) => { 
console.log(`${count++}). a: ${a} | b: ${b}`);
return a-b;
});
console.log(array);

Untuk membantu memperjelas perilaku Array#sortdan pembandingnya, pertimbangkan jenis penyisipan naif ini yang diajarkan di kursus pemrograman awal:

const sort = arr => {
  for (let i = 1; i < arr.length; i++) {
    for (let j = i; j && arr[j-1] > arr[j]; j--) {
      [arr[j], arr[j-1]] = [arr[j-1], arr[j]];
    }
  }
};

const array = [3, 0, 4, 5, 2, 2, 2, 1, 2, 2, 0];
sort(array);
console.log("" + array);

Mengabaikan pilihan insertion sort sebagai algoritma, fokus pada hardcoded pembanding: arr[j-1] > arr[j]. Ini memiliki dua masalah yang relevan dengan diskusi:

1. The >Operator dipanggil pada pasang elemen array tetapi banyak hal yang mungkin ingin mengurutkan seperti benda tidak menanggapi >dengan cara yang wajar (sama akan menjadi kenyataan jika kita menggunakan -).
2. Bahkan jika Anda bekerja dengan angka, seringkali Anda menginginkan pengaturan lain selain jenis menaik yang telah dipanggang di sini.

Kami dapat memperbaiki masalah ini dengan menambahkan comparefnargumen yang Anda kenal:

const sort = (arr, comparefn) => {
  for (let i = 1; i < arr.length; i++) {
    for (let j = i; j && comparefn(arr[j-1], arr[j]) > 0; j--) {
      [arr[j], arr[j-1]] = [arr[j-1], arr[j]];
    }
  }
};

const array = [3, 0, 4, 5, 2, 2, 2, 1, 2, 2, 0];
sort(array, (a, b) => a - b);
console.log("" + array);

sort(array, (a, b) => b - a);
console.log("" + array);

const objArray = [{id: "c"}, {id: "a"}, {id: "d"}, {id: "b"}];
sort(objArray, (a, b) => a.id.localeCompare(b.id));
console.log(JSON.stringify(objArray, null, 2));

Sekarang jenis rutinitas yang naif digeneralisasikan. Anda dapat melihat dengan tepat kapan callback ini dipanggil, menjawab rangkaian masalah pertama Anda:

Apakah fungsi callback sortir array dipanggil berkali-kali selama pengurutan? Jika demikian, saya ingin tahu dua angka mana yang diteruskan ke fungsi setiap kali

Menjalankan kode di bawah ini menunjukkan bahwa, ya, fungsinya dipanggil berkali-kali dan Anda dapat menggunakan console.loguntuk melihat nomor mana yang diteruskan:

const sort = (arr, comparefn) => {
  for (let i = 1; i < arr.length; i++) {
    for (let j = i; j && comparefn(arr[j-1], arr[j]) > 0; j--) {
      [arr[j], arr[j-1]] = [arr[j-1], arr[j]];
    }
  }
};

console.log("on our version:");
const array = [3, 0, 4, 5];
sort(array, (a, b) => console.log(a, b) || (a - b));
console.log("" + array);

console.log("on the builtin:");
console.log("" + 
  [3, 0, 4, 5].sort((a, b) => console.log(a, b) || (a - b))
);

Anda bertanya:

Bagaimana kedua kumpulan angka tersebut kemudian diurutkan dalam hubungannya satu sama lain?

Tepatnya dengan terminologi, adan bbukan kumpulan angka - mereka adalah objek dalam array (dalam contoh Anda, mereka adalah angka).

Sebenarnya, tidak masalah bagaimana mereka diurutkan karena bergantung pada implementasi. Seandainya saya menggunakan algoritme pengurutan yang berbeda dari jenis penyisipan, pembanding mungkin akan dipanggil pada pasangan angka yang berbeda, tetapi di akhir panggilan pengurutan, invarian yang penting bagi pemrogram JS adalah bahwa larik hasil diurutkan sesuai dengan pembanding, dengan asumsi pembanding mengembalikan nilai yang sesuai dengan kontrak yang Anda nyatakan (<0 saat a < b, 0 saat a === bdan> 0 saat a > b).

Dalam arti yang sama bahwa saya memiliki kebebasan untuk mengubah implementasi sortir saya selama saya tidak melanggar spesifikasi saya, implementasi ECMAScript bebas untuk memilih implementasi sortir dalam batasan spesifikasi bahasa , jadi Array#sortkemungkinan akan menghasilkan panggilan pembanding yang berbeda di mesin yang berbeda. Seseorang tidak akan menulis kode di mana logika bergantung pada beberapa urutan perbandingan tertentu (pembanding juga tidak harus menghasilkan efek samping di tempat pertama).

Misalnya, mesin V8 (pada saat penulisan) memanggil Timsort ketika larik lebih besar dari beberapa jumlah elemen yang dihitung sebelumnya dan menggunakan semacam penyisipan biner untuk potongan larik kecil. Namun, biasanya menggunakan quicksort yang tidak stabil dan kemungkinan akan memberikan urutan argumen dan panggilan yang berbeda ke pembanding.

Karena penerapan pengurutan yang berbeda menggunakan nilai hasil fungsi pembanding secara berbeda, hal ini dapat menyebabkan perilaku yang mengejutkan saat pembanding tidak mematuhi kontrak. Lihat utas ini sebagai contoh.

var array=[25, 8, 7, 41]

array.sort(function(a,b){
  console.log(`a = ${a} , b = ${b}`);
  return a - b
});

KELUARAN

• a = 8, b = 25
• a = 7, b = 8
• a = 41, b = 7
• a = 41, b = 8
• a = 41, b = 25

di Browser saya (Google Chrome Versi 70.0.3538.77 (Build Resmi) (64-bit)) pada iterasi pertama, argumen a adalah elemen Kedua dalam array dan argumen b adalah elemen pertama dari sebuah array.

jika fungsi Bandingkan kembali

1. Nilai Negatif dari b dipindahkan ke depan a.
2. Nilai positif dari a dimajukan ke b.
3. 0 (Nol) a & b akan tetap apa adanya.