از طریق منوی جستجو مطلب مورد نظر خود در وبلاگ را به سرعت پیدا کنید
مرتب‌سازی حبابی و مرتب‌سازی کوکتل در جاوا اسکریپت مرتب‌سازی حباب، که گاهی اوقات به عنوان مرتب‌سازی غرق‌شده نیز شناخته می‌شود، یکی از شناخته‌شده‌ترین الگوریتم‌های مرتب‌سازی است. این معمولاً یکی از اولین الگوریتم‌های مرتب‌سازی است که دانش‌آموزان CS به دلیل سادگی و این واقعیت که کاملاً شهودی و آسان برای ترجمه به کد هستند با آن مواجه می‌شوند.
سرفصلهای مطلب
معرفی
مرتب سازی حباب، گاهی اوقات به عنوان طبقه بندی غرق یکی از شناخته شده ترین الگوریتم های مرتب سازی است. این معمولاً یکی از اولین الگوریتم‌های مرتب‌سازی است که دانش‌آموزان CS به دلیل سادگی و این واقعیت که کاملاً بصری و آسان برای ترجمه به کد هستند، با آن مواجه می‌شوند.
با این حال، این الگوریتم ساده عملکرد ضعیفی را در مسائل واقعی نشان داده است. به خصوص در مقایسه با الگوریتم های سریع تر، محبوب تر و پرکاربردتر مانند Quicksort یا Merge Sort. به همین دلیل است که مرتب سازی حباب در درجه اول به عنوان یک ابزار آموزشی استفاده می شود.
در این مقاله روش عملکرد Bubble Sort و پیاده سازی آن در جاوا اسکریپت را توضیح خواهیم داد. ما همچنین پیچیدگی زمانی آن را بررسی می کنیم و آن را با برخی از الگوریتم های مرتب سازی دیگر مقایسه می کنیم.
علاوه بر این، ما یکی از انواع آن را اجرا خواهیم کرد – کوکتل شیکر مرتب سازی در تلاش برای بهینه سازی آن
مرتب سازی حباب
مرتب‌سازی حبابی یک الگوریتم مرتب‌سازی از نوع مقایسه است. این بدان معنی است که آن مقایسه می کند عناصر فردی در مجموعه در طول زمان اجرا. بسته به روی نوع داده و هدف شما، مقایسه را می توان از طریق یک عملگر رابطه ای یا از طریق یک تابع مقایسه سفارشی انجام داد.
ایده پشت Bubble Sort نسبتاً ساده است. از ابتدای مجموعه ای که می خواهیم مرتب شود – عناصر را در یک جفت مقایسه می کنیم. اگر جفت به ترتیب دلخواه باشد، کاری انجام نمی دهیم. اگر اینطور نیست، ما swap عناصری که از آن تشکیل شده است
این کار دوباره و دوباره انجام می شود تا زمانی که تمام عناصر مجموعه مرتب شوند. بیایید به یک نمایش تصویری از روش عملکرد مرتب سازی حباب نگاه کنیم:
نگاهی به عنصر با مقدار 8، ما می توانیم آن را از ابتدای آرایه تا محل مناسب خود “حباب بالا” ببینیم. نام «مرتب‌سازی حباب‌ها» از اینجا می‌آید.
پیاده سازی مرتب سازی حباب
اکنون که ایده پشت مرتب سازی حباب را بررسی کردیم، می توانیم با پیاده سازی شروع کنیم:
function bubbleSort(inputArr) {
let n = inputArr.length;
for(let i = 0; i < n; i++) {
for(let j = 0; j < n; j++) {
// Comparing and swapping the elements
if(inputArr(j) > inputArr(j+1)){
let t = inputArr(j);
inputArr(j) = inputArr(j+1);
inputArr(j+1) = t;
}
}
}
return inputArr;
}
پیاده سازی بسیار شهودی است. ما از طریق آرایه تکرار می کنیم n بار با a for حلقه، کجا n طول آرایه است. برای هر تکرار، یک عنصر را به جای درستش “حباب” می کنیم. این کار از طریق دیگری انجام می شود for حلقه ای که عنصر را با عنصر مجاور خود مقایسه می کند و در صورت نیاز آنها را تغییر می دهد.
در نهایت آرایه مرتب شده را برمی گردانیم. بیایید یک آرایه را پر کنیم و مرتب کنیم:
let inputArr = (5,1,4,2,8);
bubbleSort(inputArr);
console.log(inputArr);
با اجرای این کد به دست می آید:
(5) (1, 2, 4, 5, 8)
بیایید به روش انجام این کار با مقادیر مشخص نگاهی بیندازیم:
تکرار اول:
(5، 14, 2, 8) -> (1، 5، 4، 2، 8) – ما در حال تعویض 5 و 1 هستیم، زیرا 5 > 1
(1، 5، 42, 8) -> (1, 4، 5، 2، 8) – ما در حال تعویض 5 و 4 هستیم، زیرا 5 > 4 است
(1، 4، 5، 2، 8) -> (1، 4، 2، 5، 8) – ما در حال تعویض 5 و 2 هستیم، زیرا 5 > 2 است
(1، 4، 2، 5، 8) -> (1، 4، 2، 5، 8) – بدون تغییر، از 5 < 8
تکرار دوم:
(1، 42, 5, 8) -> (1، 4، 2، 5، 8) – بدون تغییر، از 1 < 4
(1، 4، 25, 8) -> (1, 2، 4، 5، 8) – ما در حال تعویض 4 و 2 هستیم، از 4 > 2
(1، 2، 4، 5، 8) -> (1، 2، 4، 5، 8) – بدون تغییر، از 4 < 5
(1، 2، 4، 5، 8) -> (1، 2، 4، 5، 8) – بدون تغییر، از 5 < 8
آرایه در دو تکرار مرتب شده است، با این حال، الگوریتم ما به اجرای خود ادامه خواهد داد n بارها و بارها و بارها همه عناصر را با هم مقایسه کنید. این به این دلیل است که ما به آن گفته ایم که تکرار شود inputArr.length بار.
مرتب سازی حبابی به خودی خود ناکارآمد است – به خصوص با نقصی مانند این. با این حال، دو کار برای بهینه سازی آن وجود دارد.
بهینه سازی ها
اولین بهینه‌سازی که می‌توانیم پیاده‌سازی کنیم این است – اگر آرایه مرتب شده است، الگوریتم را خاتمه دهیم – یعنی هیچ تعویضی انجام نمی‌شود. این را می توان از طریق a انجام داد boolean پرچم. هر بار ما swap هر عنصر، تنظیم شده است true:
function bubbleSort(inputArr) {
let n = inputArr.length;
let sorted = false;
while (!sorted) {
sorted = true;
for(let i = 0; i < n; i++){
if(inputArr(i) > inputArr(i+1)){
let t = inputArr(i);
inputArr(i) = inputArr(i+1);
inputArr(i+1) = t;
sorted = false;
}
}
}
return inputArr;
}
به محض اینکه تکرار را از طریق آرایه به پایان رساندیم، و هیچ تعویضی انجام نشد، while حلقه حلقه زدن متوقف می شود و آرایه برگردانده می شود.
بیایید دوباره آرایه را پر کنیم و مرتب کنیم:
let inputArr = (5,1,4,2,8);
bubbleSort(inputArr);
console.log(inputArr);
این کد نتیجه می دهد:
(1, 2, 4, 5, 8)
نکته ای که شایان ذکر است این است که با اتمام اولین تکرار، بزرگترین عنصر در انتهای آرایه قرار خواهد گرفت. تکرار بعدی دومین عنصر بزرگ را قبل از بزرگترین عنصر قرار می دهد و به همین ترتیب روی.
این بدان معناست که با هر تکرار، ما واقعاً نیازی به نگاه کردن به آخرین عنصر نداریم، زیرا می دانیم که در جای درست قرار دارد. بنابراین، در k-th تکرار، ما فقط باید واقعاً نگاهی به آن بیندازیم n-k+1 تکرارها:
function bubbleSort(inputArr) {
let n = inputArr.length;
let sorted = false;
let numOfIterations = 0;
while(!sorted) {
sorted = true;
for(let i = 0; i < n-numOfIterations+1; i++){
if(inputArr(i) > inputArr(i+1)){
let t = inputArr(i);
inputArr(i) = inputArr(i+1);
inputArr(i+1) = t;
sorted = false;
numOfIterations++;
}
}
}
return inputArr;
}
بیایید دوباره آرایه را پر کنیم و مرتب کنیم:
let inputArr = (5,1,4,2,8);
bubbleSort(inputArr);
console.log(inputArr);
این کد نتیجه می دهد:
(5) (1, 2, 4, 5, 8)
کوکتل شیکر مرتب سازی در مقابل مرتب سازی حباب
یکی دیگر از بهینه سازی های Bubble Sort، نوع مشتق شده آن به نام است کوکتل شیکر مرتب سازی، همچنین به عنوان شناخته شده است مرتب سازی حباب دو جهته یا به سادگی مرتب سازی کوکتل.
این الگوریتم مرتب سازی حباب را با عملکرد در دو جهت گسترش می دهد. به جای اینکه از ابتدا تا انتها برود و آن را تکرار کند، از ابتدا تا انتها و سپس از پایان به شروع دوباره در یک تکرار کامل می رود. به طور موثر، کار مرتب سازی حباب را در یک تکرار کامل انجام می دهد، اگرچه در عمل معمولاً دو برابر سریعتر انجام نمی شود.
این به این دلیل است که تعداد مقایسه مشابهی دارد. عناصر بیشتری را در هر تکرار نسبت به مرتب‌سازی حبابی معمولی مقایسه می‌کند و تعویض‌ها را در هر تکرار دو برابر می‌کند. دلیل سریعتر بودن آن این است که دامنه تعویض‌های ممکن در هر تکرار کوچک‌تر و کوچک‌تر می‌شود و عملکرد کمی بهتر به آن می‌دهد.
بیایید جلو برویم و الگوریتم را پیاده سازی کنیم:
function cocktailShakerSort(inputArr) {
let n = inputArr.length;
let sorted = false;
while (!sorted) {
sorted = true;
for (let i = 0; i < n - 1; i++) {
if (inputArr(i) > inputArr(i + 1)){
let tmp = inputArr(i);
inputArr(i) = inputArr(i + 1);
inputArr(i+1) = tmp;
sorted = false;
}
}
if (sorted)
break;
sorted = true;
for (let j = n - 1; j > 0; j--) {
if (inputArr(j-1) > inputArr(j)) {
let tmp = inputArr(j);
inputArr(j) = inputArr(j + 1);
inputArr(j+1) = tmp;
sorted = false;
}
}
}
return inputArr;
}
قسمت اول همان Bubble Sort معمولی است. گرچه، پس از عبور از جلو، به عقب می رویم. ابتدا بررسی می کنیم که آیا آرایه با گذر جلویی قبلی مرتب شده است یا خیر. اگر نه، به عقب می رویم و در صورت لزوم تعویض می کنیم. اگر مبادله ای انجام نشود، الگوریتم خاتمه یافته و نتیجه برگردانده می شود.
اگر در پاس دوم، مبادله را بررسی نکردیم، باید زمان بیشتری را به جلو بگذرانیم تا بررسی کنیم که آیا آرایه مرتب شده است یا خیر.
بیایید نگاهی به مثال دستی قبلی بیندازیم – این بار با کوکتل شیکر:
(5، 14, 2, 8) -> (1، 5، 4، 2، 8) – ما در حال تعویض 5 و 1 هستیم، زیرا 5 > 1
(1، 5، 42, 8) -> (1, 4، 5، 2، 8) – ما در حال تعویض 5 و 4 هستیم، زیرا 5 > 4 است
(1، 4، 5، 2، 8) -> (1، 4، 2، 5، 8) – ما در حال تعویض 5 و 2 هستیم، زیرا 5 > 2 است
(1، 4، 2، 5، 8) -> (1، 4، 2، 5، 8) – بدون تغییر، از 5 < 8
(1، 4، 2، 5، 8) -> (1، 4، 2، 5، 8) – بدون تغییر، از 5 > 2
(1، 4، 25, 8) -> (1, 2، 4، 5، 8) – ما در حال تعویض 4 و 2 هستیم، زیرا 2 < 4
(1، 24, 5, 8) -> (1، 2، 4، 5، 8) – بدون تغییر، از 2 > 1
در اینجا، آرایه ما در 1 تکرار مرتب شده است، برخلاف 2 تکرار مرتب سازی حباب. Cocktail Sort این کار را با 7 مقایسه انجام داد، در حالی که Bubble Sort این کار را با 8 انجام داد. این در این مقیاس زیاد نیست، اگرچه با اعداد بزرگتر، شاهد افزایش عملکرد خواهیم بود.
به طور معمول، این منجر به عملکرد 33٪ سریعتر می شود.
Donald E. Knuth در مونوگراف معروف خود از Cocktail Shaker Sort به همراه چند نوع مشابه Bubble Sort یاد کرد. “هنر برنامه نویسی کامپیوتری”:
اما هیچ یک از این اصلاحات به الگوریتمی بهتر از درج مستقیم (یعنی مرتب سازی درج) منجر نمی شود. و ما قبلاً می دانیم که درج مستقیم برای N بزرگ مناسب نیست. (…)
به طور خلاصه، به نظر می رسد که مرتب سازی حبابی چیزی برای توصیه به آن ندارد، به جز یک نام جذاب و این واقعیت که منجر به مشکلات نظری جالبی می شود.
پیچیدگی زمانی و مقایسه
از آنجایی که آرایه ما شامل n عناصر، مرتب سازی حباب انجام می دهد بر) مقایسه ها، n بار. این ما را به زمان اجرای کل هدایت می کند بر2) – متوسط و بدترین حالت این یک پیچیدگی زمانی وحشتناک برای یک الگوریتم مرتب سازی است.
برای مرجع، اکثر الگوریتم‌های مرتب‌سازی رایج، مانند Quicksort یا Merge Sort، میانگین زمان اجرا دارند. O(nlogn).
از نظر تئوری، مرتب سازی حباب می تواند یک بر) پیچیدگی، اگر آن را اجرا کنیم روی یک مجموعه مرتب شده، که عملکرد بهتری دارد همه الگوریتم های دیگر به جز Insertion Sort و Cube Sort. اگرچه، نادر بودن این مورد، استفاده از آن را در عمل توجیه نمی کند.
با استفاده از داخلی console.time() تابع، ما می توانیم زمان لازم برای اجرای کد را با هم مقایسه کنیم روی آرایه هایی با طول های مختلف:
console.time('bubble');
bubbleSort(inputArr);
console.timeEnd('bubble');
ما این کار را برای آرایه های اندازه انجام خواهیم داد 100، 1000 و 10000:
| تعداد عناصر | مرتب سازی حباب بهینه نشده | مرتب‌سازی حباب‌دار با پرچم «بولی». | مرتب سازی حباب با تکرارهای n-k+1 | کوکتل شیکر مرتب سازی |
|---|---|---|---|---|
| 100 | 2 میلی ثانیه | 1 میلی ثانیه | 1 میلی ثانیه | 1 میلی ثانیه |
| 1000 | 8 میلی‌ثانیه | 6 میلی‌ثانیه | 1 میلی ثانیه | 1 میلی ثانیه |
| 10000 | 402 میلی‌ثانیه | 383 میلی‌ثانیه | 2 میلی ثانیه | 1 میلی ثانیه |
آنچه در اینجا مشهود است این است که اجرای اول در مقایسه با انواعی مانند Cocktail Shaker چقدر ناکارآمد است.
نتیجه
اگر چه Bubble Sort بسیار شهودی است و درک و پیاده سازی آن آسان است، اما برای حل اکثر مشکلات بسیار غیر عملی است.
متوسط و بدترین زمان اجرا دارد بر2)، و فقط می تواند اجرا شود روی بهترین زمان اجرای آن بر) زمانی که آرایه از قبل مرتب شده است.
پیچیدگی فضایی آن است O (1)، که است عالی. متأسفانه، این تقریباً برای جبران پیچیدگی زمان وحشتناک کافی نیست.
حتی در میان ساده بر2) الگوریتم‌های مرتب‌سازی، مرتب‌سازی درج یا مرتب‌سازی انتخاب معمولاً کارآمدتر هستند.
به دلیل سادگی، مرتب سازی حبابی اغلب به عنوان مقدمه ای برای الگوریتم های مرتب سازی در دوره های مقدماتی علوم کامپیوتر استفاده می شود.
منتشر شده در 1403-01-20 23:54:05
