مرتب‌سازی حبابی در مقابل مرتب‌سازی انتخابی
مرتب‌سازی حبابی یک الگوریتم مرتب‌سازی است که با مرور کردن فهرستی که به طور مکرر مرتب می‌شوند و در حین مقایسه جفت‌هایی از عناصر مجاور با یکدیگر مرتب می‌شوند، عمل می‌کند. اگر یک جفت از عناصر در ترتیب نامناسبی قرار داشته باشند، برای قرار دادن آنها در ترتیب صحیح تعویض می شوند. این پیمایش تا زمانی که نیازی به تعویض بیشتر نباشد تکرار می شود. مرتب‌سازی انتخابی نیز یک الگوریتم مرتب‌سازی است که با یافتن حداقل عنصر در لیست و تعویض آن با عنصر اول شروع می‌شود. این فرآیند برای بقیه لیست با قرار دادن عناصر مبادله شده به ترتیب تکرار می شود.
مرتب‌سازی حبابی چیست؟
مرتب‌سازی حبابی یک الگوریتم مرتب‌سازی است که با مرور کردن فهرستی که به طور مکرر مرتب می‌شوند و در حین مقایسه جفت‌هایی از عناصر مجاور با یکدیگر مرتب می‌شوند، عمل می‌کند. اگر یک جفت از عناصر در ترتیب نامناسبی قرار داشته باشند، برای قرار دادن آنها در ترتیب صحیح تعویض می شوند. این پیمایش تا زمانی تکرار می شود که نیازی به مبادله بیشتر نباشد (که به این معنی است که لیست مرتب شده است). از آنجایی که عناصر کوچکتر در لیست به عنوان یک حباب به سطح بالا می آیند، نام مرتب سازی حباب به آن داده شده است. مرتب‌سازی حبابی یک الگوریتم مرتب‌سازی بسیار ساده است، اما در مرتب‌سازی فهرستی با n عنصر دارای پیچیدگی زمانی متوسط O(n2) است. به همین دلیل، مرتب‌سازی حبابی برای مرتب‌سازی فهرست‌هایی با تعداد عناصر زیاد مناسب نیست. اما به دلیل سادگی، مرتب‌سازی حبابی در طول مقدمه الگوریتم‌ها آموزش داده می‌شود.
مرتب‌سازی انتخاب چیست؟
Selection مرتب‌سازی نیز یکی دیگر از الگوریتم‌های مرتب‌سازی است که با یافتن حداقل عنصر در لیست و تعویض آن با عنصر اول شروع می‌شود.سپس حداقل عنصر از باقی مانده لیست (از عنصر دوم تا آخرین عنصر لیست) پیدا می شود و با عنصر دوم تعویض می شود. این فرآیند برای بقیه لیست با قرار دادن عناصر مبادله شده به ترتیب تکرار می شود. بنابراین در مرتب سازی انتخابی، در هر مرحله از الگوریتم، لیست به دو قسمت تقسیم می شود که یک قسمت شامل عناصر مرتب شده و قسمت دیگر شامل عناصر مرتب نشده است. با ادامه الگوریتم، لیست مرتب شده از چپ به راست رشد می کند. مرتب‌سازی انتخاب نیز دارای پیچیدگی میانگین زمانی O(n2) است. بنابراین برای مرتب سازی لیست های بزرگ نیز مناسب نیست.
تفاوت بین مرتب‌سازی حبابی و مرتب‌سازی انتخابی چیست؟
اگرچه هر دو الگوریتم مرتب‌سازی حبابی و مرتب‌سازی انتخاب دارای پیچیدگی‌های زمانی متوسط O(n2) هستند، مرتب‌سازی حبابی تقریباً در همه زمان‌ها از مرتب‌سازی انتخابی بهتر عمل می‌کند. این به دلیل تعداد مبادله های مورد نیاز دو الگوریتم است (انواع حبابی به مبادله های بیشتری نیاز دارد).اما به دلیل سادگی مرتب سازی حبابی، اندازه کد آن بسیار کوچک است. پایداری یکی دیگر از تفاوت های این دو الگوریتم است. الگوریتم مرتب‌سازی پایدار، الگوریتم مرتب‌سازی است که در صورتی که فهرست حاوی عناصری با مقدار مساوی باشد، ترتیب رکوردها را حفظ می‌کند. از این نظر، مرتب‌سازی انتخابی یک الگوریتم پایدار نیست، در حالی که مرتب‌سازی حبابی یک الگوریتم پایدار است.
