مرتب‌سازی حبابی در مقابل مرتب‌سازی درج
مرتب‌سازی حبابی یک الگوریتم مرتب‌سازی است که با مرور کردن فهرستی که به طور مکرر مرتب می‌شوند و در حین مقایسه جفت‌هایی از عناصر مجاور با یکدیگر مرتب می‌شوند، عمل می‌کند. اگر یک جفت از عناصر در ترتیب نامناسبی قرار داشته باشند، برای قرار دادن آنها در ترتیب صحیح تعویض می شوند. این پیمایش تا زمانی که نیازی به تعویض بیشتر نباشد تکرار می شود. مرتب‌سازی درج نیز یک الگوریتم مرتب‌سازی است که با قرار دادن یک عنصر در لیست ورودی در موقعیت صحیح در لیستی که قبلا مرتب شده است عمل می‌کند. این فرآیند به طور مکرر اعمال می شود تا زمانی که لیست مرتب شود.
مرتب‌سازی حبابی چیست؟
مرتب‌سازی حبابی یک الگوریتم مرتب‌سازی است که با مرور کردن فهرستی که به طور مکرر مرتب می‌شوند و در حین مقایسه جفت‌هایی از عناصر مجاور با یکدیگر مرتب می‌شوند، عمل می‌کند. اگر یک جفت از عناصر در ترتیب نامناسبی قرار داشته باشند، برای قرار دادن آنها در ترتیب صحیح تعویض می شوند. این پیمایش تا زمانی تکرار می شود که نیازی به مبادله بیشتر نباشد (که به این معنی است که لیست مرتب شده است). از آنجایی که عناصر کوچکتر در لیست به عنوان یک حباب به سطح بالا می آیند، نام مرتب سازی حباب به آن داده شده است. مرتب‌سازی حبابی یک الگوریتم مرتب‌سازی بسیار ساده است، اما در مرتب‌سازی فهرستی با n عنصر دارای پیچیدگی زمانی متوسط O(n2) است. به همین دلیل، مرتب‌سازی حبابی برای مرتب‌سازی فهرست‌هایی با تعداد عناصر زیاد مناسب نیست. اما به دلیل سادگی، مرتب‌سازی حبابی در طول مقدمه الگوریتم‌ها آموزش داده می‌شود.
Insertion Sort چیست؟
Insertion مرتب‌سازی یکی دیگر از الگوریتم‌های مرتب‌سازی است که با قرار دادن یک عنصر در لیست ورودی در موقعیت صحیح در لیست (که قبلا مرتب شده است) عمل می‌کند.این فرآیند به طور مکرر اعمال می شود تا زمانی که لیست مرتب شود. در مرتب سازی درج، مرتب سازی در محل انجام می شود. بنابراین پس از تکرار تکرار الگوریتم، اولین ورودی های i+1 در لیست مرتب می شوند و بقیه لیست مرتب نمی شوند. در هر تکرار، اولین عنصر در قسمت مرتب نشده لیست گرفته می شود و در جای درست در قسمت مرتب شده لیست درج می شود. مرتب‌سازی درج دارای پیچیدگی زمانی میانگین O(n2) است. به همین دلیل، مرتب‌سازی درج برای مرتب‌سازی فهرست‌های بزرگ نیز مناسب نیست.
تفاوت بین مرتب‌سازی حبابی و مرتب‌سازی درج چیست؟
اگرچه هر دو الگوریتم مرتب‌سازی حبابی و مرتب‌سازی درج دارای پیچیدگی‌های زمانی میانگین O(n2) هستند، مرتب‌سازی حبابی تقریباً در همه زمان‌ها از مرتب‌سازی درج بهتر است. این به دلیل تعداد مبادله های مورد نیاز دو الگوریتم است (انواع حبابی به مبادله های بیشتری نیاز دارد). اما به دلیل سادگی مرتب سازی حبابی، اندازه کد آن بسیار کوچک است.همچنین گونه‌ای از مرتب‌سازی درج به نام مرتب‌سازی پوسته وجود دارد که پیچیدگی زمانی O(n3/2) دارد که امکان استفاده عملی از آن را فراهم می‌کند. علاوه بر این، مرتب‌سازی درج برای مرتب‌سازی فهرست‌های «تقریباً مرتب‌شده» در مقایسه با مرتب‌سازی حبابی بسیار کارآمد است.
