مرتبسازی - تابع sort() در جاوااسکریپت چگونه کار میکند؟

این کد چگونه این آرایه را به ترتیب عددی مرتب میکند؟

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

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

میدانم که اگر نتیجه محاسبه... باشد

کمتر از 0: «a» به گونهای مرتب میشود که ایندکس پایینتری نسبت به «b» داشته باشد.
صفر: «a» و «b» برابر در نظر گرفته میشوند و هیچ مرتبی انجام نمیشود.
بیشتر از 0: «b» به گونهای مرتب میشود که ایندکس پایینتری نسبت به «a» داشته باشد.

آیا تابع بازخوانی مرتبسازی آرایه در طول فرآیند مرتبسازی چندین بار فراخوانی میشود؟

اگر چنین است، دوست دارم بدانم هر بار کدام دو عدد به تابع وارد میشوند. من فرض کردم ابتدا «25» (a) و «8» (b) گرفته میشود، سپس «7» (a) و «41» (b)، بنابراین:

۲۵(a) - ۸(b)=۱۷ (بزرگتر از صفر، بنابراین "b" را در اندیس پایینتر از "a" مرتب کنید): ۸، ۲۵

۷(a) - ۴۱(b)=-۳۴ (کمتر از صفر، بنابراین «a» را به شاخصی پایینتر از «b» مرتب کنید: ۷، ۴۱

پس این دو مجموعه اعداد چگونه نسبت به یکدیگر مرتب میشوند؟

لطفاً به یک تازهکار در حال مبارزه کمک کنید!

پاسخ شماره ۱

آیا تابع بازخوانی مرتبسازی آرایه در طول فرآیند مرتبسازی چندین بار فراخوانی میشود؟

بله

اگر چنین است، مایلم بدانم هر بار کدام دو عدد به تابع وارد میشوند

شما میتوانید خودتان با این پیدا کنید:

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

ویرایش

این خروجیای است که من به دست آوردهام:

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

پاسخ شماره ۲

تفسیرگر جاوااسکریپت نوعی الگوریتم مرتبسازی را به صورت داخلی در خود دارد. این الگوریتم تابع مقایسه را چندین بار در طول عملیات مرتبسازی فراخوانی میکند. تعداد دفعاتی که تابع مقایسه فراخوانی میشود به الگوریتم خاص، دادههایی که باید مرتب شوند و حالتی که دادهها قبل از مرتبسازی در آن قرار دارند، بستگی دارد.

برخی الگوریتمهای مرتبسازی در فهرستهایی که از قبل مرتب شدهاند عملکرد ضعیفی دارند زیرا این موضوع باعث میشود آنها مقایسههای بسیار بیشتری نسبت به حالت معمول انجام دهند. برخی دیگر با فهرستهای از قبل مرتب شده خوب کنار میآیند، اما موارد دیگری وجود دارد که میتوان آنها را "فریب داد" تا ضعیف عمل کنند.

الگوریتمهای مرتبسازی زیادی به طور معمول استفاده میشوند زیرا هیچ الگوریتم واحدی برای همه اهداف کامل نیست. دو الگوریتم که بیشتر برای مرتبسازی عمومی استفاده میشوند، سریعمرتبسازی (Quicksort) و مرتبسازی ادغامی (Merge Sort) هستند. سریعمرتبسازی اغلب از نظر سرعت از دیگری سریعتر است، اما مرتبسازی ادغامی ویژگیهای خوبی دارد که میتواند آن را به انتخاب بهتری در کل تبدیل کند. مرتبسازی ادغامی پایدار است، در حالی که سریعمرتبسازی پایدار نیست. هر دو الگوریتم قابلیت موازی شدن دارند، اما نحوه عملکرد مرتبسازی ادغامی باعث میشود پیادهسازی موازی آن کارآمدتر باشد، با فرض برابر بودن سایر شرایط.

مفسر جاوااسکریپت خاص شما ممکن است از یکی از این الگوریتمها یا چیزی کاملاً متفاوت استفاده کند. استاندارد ECMAScript مشخص نمیکند که یک پیادهسازی منطبق باید از کدام الگوریتم استفاده کند. حتی بهطور صریح نیاز به ثبات را رد میکند.

پاسخ شماره ۳

دانش عمیق

اگر نتیجه منفی باشد، a قبل از b مرتب میشود.

اگر نتیجه مثبت باشد، b قبل از a مرتب میشود.

اگر نتیجه ۰ باشد، هیچ تغییری در ترتیب مرتبسازی این دو مقدار انجام نمیشود.

توجه:

این کد نمای داخلی متد sort را گام به گام نشان میدهد.

خروجی:

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

پاسخ شماره ۴

جفتهای مقادیر با هم مقایسه میشوند، یکی یکی. جفتهایی که مقایسه میشوند یک جزئیات پیادهسازی هستند--فرض نکنید که در هر مرورگر یکسان خواهند بود. تابع بازخوانی میتواند هر چیزی باشد (بنابراین میتوانید رشتهها یا اعداد رومی یا هر چیز دیگری را مرتب کنید به شرطی که بتوانید تابعی ارائه دهید که 1، 0، -1 برگرداند).

یک نکته که باید در مورد مرتبسازی جاوااسکریپت به خاطر داشته باشید این است که تضمینی برای پایدار بودن آن وجود ندارد.

پاسخ شماره ۵

برای کمک به روشن شدن رفتار Array#sort و مقایسهکنندهی آن، این مرتبسازی ساده با درج را در نظر بگیرید که در دورههای ابتدایی برنامهنویسی آموزش داده میشود:

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

نادیده گرفتن انتخاب مرتبسازی درجی به عنوان الگوریتم، بر روی مقایسهکننده ثابتشده تمرکز کنید: arr[j-1] > arr[j]. این دو مشکل دارد که به بحث مرتبط هستند:

1. عملگر > بر روی جفتهای عناصر آرایه فراخوانی میشود، اما بسیاری از چیزهایی که ممکن است بخواهید مرتب کنید، مانند اشیاء، به صورت معقول به > پاسخ نمیدهند (همان مورد درست خواهد بود اگر از - استفاده میکردیم).
2. حتی اگر با اعداد کار میکنید، اغلب اوقات میخواهید ترتیبی غیر از ترتیب صعودی که اینجا به صورت پیشفرض قرار داده شده داشته باشید.

ما میتوانیم این مشکلات را با افزودن یک آرگومان comparefn که با آن آشنا هستید، برطرف کنیم:

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

اکنون برنامه مرتبسازی ساده تعمیم داده شده است. شما میتوانید دقیقا ببینید که این کالبک چه زمانی فراخوانی میشود و به اولین مجموعه نگرانیهای شما پاسخ میدهد:

آیا تابع callback مرتبسازی آرایه در طول فرآیند مرتبسازی چندین بار فراخوانی میشود؟ اگر چنین است، دوست دارم بدانم هر بار چه دو عددی به تابع داده میشوند

اجرای کد زیر نشان میدهد که بله، این تابع چندین بار فراخوانی میشود و شما میتوانید از console.log استفاده کنید تا ببینید کدام اعداد ارسال شدهاند:

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

تو میپرسی:

پس این دو مجموعه اعداد چگونه نسبت به یکدیگر مرتب میشوند؟

برای دقت در اصطلاحات، a و b مجموعهای از اعداد نیستند--آنها اشیاء در آرایه هستند (در مثال شما، آنها اعداد هستند).

حقیقت این است که فرقی نمیکند چگونه مرتب شدهاند زیرا این به پیادهسازی بستگی دارد. اگر من از الگوریتم مرتبسازی متفاوتی به جای مرتبسازی درج استفاده میکردم، احتمالاً مقایسهکننده روی جفتهای مختلفی از اعداد فراخوانی میشد، اما در پایان فراخوانی مرتبسازی، اصل ثابتی که برای برنامهنویس JS مهم است این است که آرایه نتیجه طبق مقایسهکننده مرتب شده است، به شرطی که مقایسهکننده مقادیری را بازگرداند که با قراردادی که شما بیان کردهاید مطابقت داشته باشد (< 0 وقتی که a < b، 0 وقتی که a === b و > 0 وقتی که a > b).

به همان معنایی که من این آزادی را دارم که پیادهسازی مرتبسازی خود را تغییر دهم تا زمانی که مشخصات خود را نقض نکنم، پیادهسازیهای ECMAScript نیز آزادند که پیادهسازی مرتبسازی را در چارچوب مشخصات زبان انتخاب کنند، بنابراین Array#sort احتمالاً فراخوانیهای مقایسهگر متفاوتی را در موتورهای مختلف تولید خواهد کرد. کسی نباید کدی بنویسد که منطق آن به توالی خاصی از مقایسات وابسته باشد (و همچنین مقایسهگر نباید در درجه اول اثرات جانبی ایجاد کند).

برای مثال، موتور V8 (در زمان نگارش) زمانی که آرایه بزرگتر از یک تعداد از پیش محاسبه شده از عناصر باشد، Timsort را فراخوانی میکند و برای بخشهای کوچک آرایه از مرتبسازی درج دودویی استفاده میکند. با این حال، قبلاً از quicksort استفاده میکرد که ناپایدار است و احتمالاً توالی متفاوتی از آرگومانها و فراخوانیها به مقایسهکننده میداد.

از آنجا که پیادهسازیهای مختلف مرتبسازی از مقدار بازگشتی تابع مقایسهگر به صورت متفاوت استفاده میکنند، این میتواند منجر به رفتار غیرمنتظرهای شود زمانی که تابع مقایسهگر به قرارداد پایبند نباشد. برای یک مثال به این بحث مراجعه کنید.