الگوریتم Bubble Sort یا همون مرتب سازی حبابی

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

نحوه کار کرد این الگوریتم به این نحوه که میاد ایندکس اول رو با ایندکس دوم مقایسه می کنه اگر عدد اول بزرگ تر بود جاشو با عدد دوم عوض می کنه اگر نه دست بهش نمی زنه

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

ما اینجا یک ارایه از اعداد مثل ارایه پایین داریم

let array = [ 5 , 1 , 4 , 2 , 8 ]

خب عکسو ببینید

توی پالس اول 5 بزرگ تر از 1 هستش پس جاشو عوض می کنه

خط بعدی باز 5 از 4 بزرگ تره جاشونو عوض می کنه

خط سوم 5 از 2 بزرگ تره باز هم جا به جایی صورت می گیره

حظ چهارم 5 از 8 کوچیک تره جا به جایی صورت نمی گیره

و می ره برای پالس بعدی

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

خب به صورت تئوری فهمیدیم این الگوریتم به چه شکله حالا بیاید کد جاوااسکریپتیش رو بنویسیم

function bubbleSort(array) {
 	let swapped = true;                                       //(1)
 	do {
 		swapped = false;
 		for (let j = 0; j < array.length; j++) {
 			if (array[j] > array[j + 1]) {             //(2)
 				let temp = array[j];                 //(3)
 				array[j] = array[j + 1];
 				array[j + 1] = temp;
 				swapped = true;                    //(4)
 			}
 		}
 	}
 while (swapped);
 	return array;
 }

کد بالا رو ببینید

• (1) اول اومدیم یه متغییر تعریف کردیم تا بتونیم تشخیص بدیم که ایا توی هر پالس جا به جایی صورت می گیره یا نه
• (2) شرط گذاشتیم که ایندکسمون با ایندکس بعدیش بزرگ تره یا نه و اگر بزرگ تر باشه جا به جایی انجام می شه در غیر این صورت هیچ اتفاقی نمی افته
• (3) حین جا به جایی ایندکس فعلی رو می ریزیم توی یک متغییر به اسم temp تا داشته باشیم و خط بعدش میایم ایندکس فعلی رو با اندکس بعدیش جا به جا می کنیم و مقدار temp رو می ریزیم تو ایندکس بعدی
• (4) وقتی شرط اجرا می شه در واقع یعنی یک جا به جایی صورت گرفته و بالاتر توضیح دادم که وقتی جا به جایی داشته باشیم به این معنی که پالس بعدی هم داریم و باید انقدر پالس ها رو اجرا کنیم تا هیچ جا به جایی اتفاق نیفته پس مقدار رو true می کنیم تا do while یک بار دیگه اجرا بشه

پیچیدگی زمانی این الگوریتم توی بهترین حالت برابر (n)O هستش و در حالت متوسط و بد (n * n)O هستش و بهترین حالت وقتیه که ارایه از قبل مرتب شده باشه و بدترین حالت وقتیه که ارایه برعکس مرتب شده باشه که ذاتا پرفرمنس خوبی نداره و الگوریتم های بهتری (از نظر زمان) برای مرتب سازی وجود داره که توی پست های بعدی معرفی خواهم کرد

این الگوریتم یک روش مرتب سازی درجا هستش یعنی برای مرتب سازی از فضای جانبی کمک نمی گیره و با جا به جا کردن ایندکس های خود ارایه اون ها رو مرتب می کنه

امیدوارم مفید باشه :)

آقا داود