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

قبل از اینکه شروع کنیم ما در این مقاله به صورت یکم تخصصی بررسی خواهیم کرد پس استفاده از نماد O بزرگ برای تجزیه و تحلیل پیچیدگی زمانی و پیچیدگی فضایی الگوریتم‌های مختلف می باشد. اما ما همچنین مرورهای سطح بالایی را ارائه خواهیم کرد که باید به راحتی توسط اکثر افراد قابل درک باشد.

ما همچنین در آنوفل به صورت جداگانه الگوریتم های مرتب سازی در زبان جاوااسکریپت نیز بررسی کردیم.

الگوریتم مرتب سازی چیست؟

اساساً، یک الگوریتم مرتب‌سازی یک برنامه کامپیوتری است که داده‌ها را به ترتیب خاصی، مانند ترتیب حروف الفبا یا ترتیب عددی، معمولاً صعودی یا نزولی، سازمان‌دهی(مرتب) می‌کند.

الگوریتم های مرتب سازی برای چه مواردی استفاده می شوند؟

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

چرا الگوریتم های مرتب سازی بسیار مهم هستند؟

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

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

انواع مختلف مرتب سازی در ساختارهای داده

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

الگوریتم های مرتب سازی مبتنی بر مقایسه

این الگورتیم ها آیتم های مجموعه داده را با هم مقایسه می کنند و ترتیب آنها را بر اساس نتیجه مقایسه تعیین می کنند. نمونه‌هایی از الگوریتم‌های مرتب‌سازی مبتنی بر مقایسه عبارتند از مرتب‌سازی حبابی، مرتب‌سازی insertion، مرتب‌سازی سریع، مرتب‌سازی ادغامی و مرتب‌سازی heap .

الگوریتم های مرتب سازی غیر مبتنی بر مقایسه

این الگورتیم ها آیتم ها را مستقیماً با هم مقایسه نمی کنند، بلکه از ویژگی های دیگر مجموعه داده برای تعیین ترتیب آنها استفاده می کنند. نمونه‌هایی از الگوریتم‌های مرتب‌سازی غیرمقایسه‌ای شامل مرتب‌سازی شمارش، مرتب‌سازی ریشه(radix) و مرتب‌سازی bucket است.

الگوریتم های مرتب سازی در لوکال

این الگوریتم‌ها مجموعه داده‌ها را در جای خود مرتب می‌کنند، به این معنی که برای ذخیره نتایج میانی به حافظه اضافی نیاز ندارند. نمونه‌هایی از الگوریتم‌های مرتب‌سازی در لوکال شامل مرتب‌سازی حبابی، مرتب‌سازی insertion، مرتب‌سازی سریع و مرتب‌سازی shell می‌شوند.

الگوریتم های مرتب سازی پایدار

این الگورتیم ها ترتیب نسبی آیتم های برابر را در مجموعه داده حفظ می کنند. نمونه‌هایی از الگوریتم‌های مرتب‌سازی پایدار عبارتند از مرتب‌سازی insertion، مرتب‌سازی ادغام و Timsort.

الگوریتم های مرتب سازی تطبیقی

این الگورتیم ها از هر ترتیب موجود در مجموعه داده برای بهبود کارایی خود بهره می برند. نمونه‌هایی از الگوریتم‌های مرتب‌سازی تطبیقی شامل مرتب‌سازی insertion، مرتب‌سازی حبابی و Timsort هستند.

10 الگوریتم برتر مرتب سازی که باید بدانید

بیایید اکنون ده مورد از بهترین الگوریتم های مرتب سازی را بررسی کنیم تا هنگام انتخاب یکی از آنها آگاه باشیم.

مرتب سازی حبابی

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

مرتب‌سازی حبابی گاهی اوقات به عنوان "مرتب‌سازی sinking " نیز شناخته می‌شود.

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

تاریخچه مرتب سازی حبابی

ریشه‌های مرتب‌سازی حبابی به اواخر دهه 1950 بازمی‌گردد، و دونالد کنوت آن را در کتاب کلاسیک خود در سال 1968 به نام هنر برنامه‌نویسی کامپیوتری محبوب کرد.

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

مزایا و معایب نوع حبابی

مرتب‌سازی حبابی به عنوان یک الگوریتم مرتب‌سازی نسبتاً ناکارآمد در نظر گرفته می‌شود، زیرا پیچیدگی متوسط و بدترین حالت آن هر دو $O(n^2)$ است. این باعث می شود کارایی آن نسبت به سایر الگوریتم های مرتب سازی، مانند مرتب سازی سریع یا ادغام، بسیار کمتر باشد.

نکته فنی: پیچیدگی $O(n^2)$ به این معنی است که مدت زمانی که طول می کشد تا یک الگوریتم به پایان برسد با مربع اندازه ورودی متناسب است. این بدان معنی است که اندازه ورودی بزرگتر باعث می شود که تکمیل الگوریتم به طور قابل توجهی بیشتر طول بکشد.

برای مثال، اگر الگوریتمی را در نظر بگیرید که آرایه‌ای از اعداد را مرتب می‌کند، ممکن است مرتب‌سازی یک آرایه ده عددی یک ثانیه طول بکشد، اما مرتب‌سازی یک آرایه 20 عددی ممکن است چهار ثانیه طول بکشد. این به این دلیل است که الگوریتم باید هر آیتم در آرایه را با هر آیتم دیگری مقایسه کند، بنابراین باید 20 مقایسه برای آرایه بزرگتر انجام دهد، در حالی که تنها ده مورد برای آرایه کوچکتر است.

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

در چه مواردی ازمرتب سازی حبابی استفاده کنید

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

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

نحوه اجرای مرتب سازی حبابی

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

مرتب سازی حبابی در پایتون:

def bubble_sort(items):
    for i in range(len(items)):
        for j in range(len(items)-1-i):
            if items[j] > items[j+1]:
                items[j], items[j+1] = items[j+1], items[j]
    return items

items = [6,20,8,19,56,23,87,41,49,53]
print(bubble_sort(items))

مرتب سازی حبابی در جاوا اسکریپت:

function bubbleSort(items) {
  let swapped;
  do {
    swapped = false;
    for (let i = 0; i < items.length - 1; i++) {
      if (items[i] > items[i + 1]) {
        let temp = items[i];
        items[i] = items[i + 1];
        items[i + 1] = temp;
        swapped = true;
      }
    }
  } while (swapped);
  return items;
}

let items = [6, 20, 8, 19, 56, 23, 87, 41, 49, 53];
console.log(bubbleSort(items));

مرتب سازی insertion

مرتب‌سازی insertion الگوریتم ساده دیگری است که آرایه مرتب‌شده نهایی را هر بار یک آیتم می‌سازد، و به دلیل نحوه قرار دادن آیتم های کوچکتر در موقعیت‌های صحیح خود در آرایه مرتب‌شده، به این شکل نام‌گذاری شده است.

نحوه کار کردن این مرتب سازی :لیست مرتب شده جزئی در ابتدا فقط شامل اولین آیتم در لیست است. با هر تکرار، یک آیتم از داده های ورودی "هنوز برای سفارش بررسی نشده" حذف می شود و در لیست مرتب شده insertion می شود.

تاریخچه مرتب سازی insertion

در هنر برنامه‌نویسی کامپیوتر، کنوت اظهار می‌کند که مرتب‌سازی insertion «در اوایل سال 1946 توسط جان ماچلی در اولین بحث منتشر شده درباره مرتب‌سازی رایانه ذکر شد» و آن را به‌عنوان یک الگوریتم «طبیعی» توصیف کرد که به راحتی قابل درک و پیاده‌سازی است.

در اواخر دهه 1950، دونالد ال. شل مجموعه‌ای از پیشرفت‌ها را در روش مرتب‌سازی shell خود انجام داد (که در زیر پوشش داده می‌شود)، که آیتم های جدا شده را با فاصله‌ای که در هر پاس کاهش می‌یابد مقایسه می‌کند و پیچیدگی الگوریتم را به $(O(n^{3/2}$ کاهش می‌دهد. و $O(n^{4/3})$ در دو نوع مختلف این ممکن است چندان به نظر نرسد، اما برای کاربردهای عملی یک پیشرفت قابل توجه است!

نکات فنی: پیچیدگی‌های $O(n^{3/2})$ و $O(n^{4/3})$ کارآمدتر از پیچیدگی $O(n^2)$ هستند، به این معنی که اتمام آنها زمان کمتری می‌برد. . این به این دلیل است که آنها به اندازه پیچیدگی $O(n^2)$ نیازی به مقایسه ندارند.

برای مثال، مرتب کردن یک آرایه ده عددی با استفاده از الگوریتم $O(n^2)$ ممکن است یک ثانیه طول بکشد، اما مرتب کردن همان آرایه با استفاده از $O(n^{3/2})$ ممکن است 0.5 ثانیه طول بکشد. الگوریتم این به این دلیل است که الگوریتم هنگام استفاده از الگوریتم $O(n^{3/2})$ می‌تواند مقایسه‌های کمتری انجام دهد که در نتیجه زمان اجرا سریع‌تر می‌شود.

در سال 2006، Bender، Martin Farach-Colton و Mosteiro نوع جدیدی از مرتب‌سازی insertion را به نام مرتب‌سازی کتابخانه‌ای یا «مرتب‌سازی با شکاف» منتشر کردند که تعداد کمی از فضاهای استفاده نشده (یا «شکاف‌ها») را در سراسر آرایه پخش می‌کند و باعث بهبود بیشتر می‌شود. زمان اجرا به $O(n \log n)$ .

نکات فنی: پیچیدگی $O(n \log n)$ کارآمدتر از پیچیدگی $O(n^2)$ و $O(n^{3/2})$ و $O(n^{4/3})$ می باشد.پیچیدگی ها به این دلیل است که از رویکرد divide-and-conquer استفاده می کند، به این معنی که می تواند مشکل را به قطعات کوچکتر تقسیم کند و سریعتر آنها را حل کند.

برای مثال، مرتب کردن یک آرایه ده عددی با استفاده از الگوریتم $O(n^2)$ ممکن است یک ثانیه طول بکشد، و مرتب سازی همان آرایه با استفاده از الگوریتم $O(n^{3/2})$ که 0.5 ثانیه طول بکشد. اما مرتب کردن همان آرایه با استفاده از الگوریتم $O(n \log n)$ ممکن است 0.1 ثانیه طول بکشد. این به این دلیل است که الگوریتم می تواند آرایه را به قطعات کوچکتر تقسیم کند و آنها را به صورت موازی حل کند و در نتیجه زمان اجرا سریعتر شود.

مزایا و معایب نوع insertion

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

درست مانند مرتب‌سازی حبابی، پیچیدگی زمانی آن در بدترین حالت و میانگین حالت آن $O(n^2)$ است. اما برخلاف مرتب‌سازی حبابی، مرتب‌سازی insertion می‌تواند برای مرتب‌سازی مجموعه‌های داده در لوکال استفاده شود، به این معنی که برای ذخیره نتایج میانی به حافظه اضافی نیاز ندارد.

در چه مواردی از مرتب سازی insertion استفاده کنید

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

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

نحوه پیاده سازی مرتب سازی insertion

یک لیست مرتب نشده بردارید و اولین مورد را به عنوان "pivot" انتخاب کنید.
در لیست تکرار کنید، pivot را در جای درست خود در لیست مرتب شده قرار دهید.
فرآیند را با مورد بعدی در لیست تکرار کنید.
ادامه دهید تا لیست مرتب شود.

مرتب سازی insertion در پایتون:

def insertion_sort(items):
    for i in range(1, len(items)):
        j = i
        while j > 0 and items[j-1] > items[j]:
            items[j-1], items[j] = items[j], items[j-1]
            j -= 1
    return items

items = [6,20,8,19,56,23,87,41,49,53]
print(insertion_sort(items))

مرتب سازی insertion در جاوا اسکریپت:

function insertionSort(items) {
  for (let i = 1; i < items.length; i++) {
    let j = i;
    while (j > 0 && items[j - 1] > items[j]) {
      let temp = items[j];
      items[j] = items[j - 1];
      items[j - 1] = temp;
      j--;
    }
  }
  return items;
}

let items = [6, 20, 8, 19, 56, 23, 87, 41, 49, 53];
console.log(insertionSort(items));

مرتب سازی سریع

Quicksort یک الگوریتم مرتب‌سازی محبوب تقسیم کنید و بر اساس اصل تقسیم‌بندی یک آرایه به دو آرایه فرعی است - یکی حاوی آیتم های کوچک‌تر از آیتم pivot و دیگری حاوی آیتم های بزرگ‌تر از آیتم pivot است. سپس دو آرایه فرعی به صورت بازگشتی مرتب می شوند.

مراحل اساسی مرتب سازی سریع عبارتند از:

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

تاریخچه مرتب سازی سریع

Quicksort توسط تونی هور در سال 1959 اختراع شد. هور در شرکت کامپیوتر برادران الیوت در بریتانیا کار می کرد که الگوریتمی را به عنوان راهی برای مرتب کردن کلمات در حافظه کامپیوتر Ferranti Mark I توسعه داد.

Quicksort در ابتدا به عنوان یک مقاله تحقیقاتی در سال 1961 منتشر شد و به سرعت به یکی از پرکاربردترین الگوریتم های مرتب سازی بدلیل سادگی، کارایی و سهولت اجرا تبدیل شد.

مزایای مرتب سازی سریع

میانگین پیچیدگی زمانی موردی آن $O(n \log n)$ است.
به حافظه اضافی بسیار کمی نیاز دارد، زیرا آرایه را در جای خود مرتب می کند.
پیاده سازی آن آسان است و به طور گسترده قابل درک است.
به راحتی می توان آن را موازی کرد.

معایب مرتب سازی سریع

در بدترین حالت پیچیدگی زمانی آن $O(n^2)$ است، زمانی که pivot ضعیف انتخاب شده باشد، که کارایی آن را نسبت به سایر الگوریتم‌ها مانند ادغام مرتب‌سازی یا heapsort در شرایط خاص کمتر می‌کند.

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

در چه مواردی از مرتب سازی سریع استفاده کنید

به عنوان یک الگوریتم مرتب‌سازی بسیار کارآمد، مرتب‌سازی سریع طیف وسیعی از کاربردها را دارد.

مجموعه داده های بزرگ پیچیدگی زمانی متوسط آن $O(n \log n)$ است، به این معنی که می تواند مقادیر زیادی از داده ها را به سرعت مرتب کند.
داده های تصادفی بر روی داده های مرتب شده به طور تصادفی خوب عمل می کند، زیرا برای تقسیم داده ها به دو آرایه فرعی که به صورت بازگشتی مرتب می شوند، به آیتم pivot متکی است. هنگامی که داده ها تصادفی هستند، آیتم pivot احتمالاً نزدیک به میانه است که منجر به عملکرد خوب می شود.
پردازش موازی. به راحتی می توان آن را موازی کرد، که آن را برای مرتب سازی مجموعه داده های بزرگ در پردازنده های چند هسته ای ایده آل می کند. با تقسیم داده ها به آرایه های فرعی کوچکتر، الگوریتم را می توان بر روی چندین هسته به طور همزمان اجرا کرد که منجر به عملکرد سریعتر می شود.
مرتب سازی خارجی اغلب به عنوان بخشی از یک الگوریتم مرتب‌سازی خارجی استفاده می‌شود، که برای مرتب‌سازی داده‌هایی استفاده می‌شود که بیش از حد بزرگ هستند که در حافظه جای بگیرند. در این مورد، داده ها به تکه هایی مرتب می شوند، که سپس با استفاده از یک الگوریتم ادغام مرتب سازی ادغام می شوند.
متراکم سازی داده ها. در برخی از الگوریتم‌های فشرده‌سازی داده‌ها، مانند تبدیل Burrows-Wheeler، که در نرم‌افزار فشرده‌سازی bzip2 استفاده می‌شود. این الگوریتم برای مرتب‌سازی داده‌ها در ماتریس Burrows-Wheeler استفاده می‌شود که سپس برای تولید داده‌های فشرده تبدیل می‌شود.

نحوه اجرای مرتب سازی سریع

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

مرتب سازی سریع در پایتون:

def quick_sort(items):
    if len(items) > 1:
        pivot = items[0]
        left = [i for i in items[1:] if i < pivot]
        right = [i for i in items[1:] if i >= pivot]
        return quick_sort(left) + [pivot] + quick_sort(right)
    else:
        return items

items = [6,20,8,19,56,23,87,41,49,53]
print(quick_sort(items))

مرتب سازی سریع در جاوا اسکریپت:

function quickSort(items) {
  if (items.length > 1) {
    let pivot = items[0];
    let left = [];
    let right = [];
    for (let i = 1; i < items.length; i++) {
      if (items[i] < pivot) {
        left.push(items[i]);
      } else {
        right.push(items[i]);
      }
    }
    return quickSort(left).concat(pivot, quickSort(right));
  } else {
    return items;
  }
}

let items = [6, 20, 8, 19, 56, 23, 87, 41, 49, 53];
console.log(quickSort(items));

مرتب سازی bucket

مرتب‌سازی bucket یک الگوریتم مفید برای مرتب‌سازی داده‌های توزیع شده یکنواخت است و به راحتی می‌توان آن را برای بهبود عملکرد موازی کرد.

مراحل اساسی مرتب سازی bucket عبارتند از:

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

مزایای مرتب سازی bucket

برای داده های توزیع شده یکنواخت کارآمد است، با پیچیدگی زمانی متوسط $O(n+k)$ ، که $n$ تعداد آیتم های و $k$ تعداد سطل ها است.
به راحتی می توان آن را موازی کرد و به آن اجازه می دهد از چندین هسته در پردازنده های مدرن استفاده کند.
پایدار است، به این معنی که نظم نسبی آیتم های مساوی را در آرایه اصلی حفظ می کند.
می توان از آن برای داده هایی با توزیع های غیر یکنواخت با تنظیم تابع سطل استفاده کرد.

نکته فنی: پیچیدگی $O(n+k)$ کارآمدتر از پیچیدگی $O(n^{3/2})$ و $O(n^{4/3}) است. پیچیدگی $O(n \log n)$ به این دلیل است که فقط باید تعداد خطی عملیات را بدون توجه به اندازه ورودی انجام دهد.

به عنوان مثال، الگوریتمی را در نظر بگیرید که آرایه ای از اعداد را مرتب می کند. مرتب‌سازی آرایه‌ای از ده عدد با استفاده از الگوریتم $O(n^2)$ ممکن است یک ثانیه طول بکشد، مرتب‌سازی همان آرایه با استفاده از الگوریتم $O(n^{3/2})$ هم 0.5 ثانیه و 0.1 ثانیه طول بکشد. مرتب سازی همان آرایه با استفاده از الگوریتم $O(n \log n)$ ، اما مرتب سازی همان آرایه با استفاده از الگوریتم $O(n+k)$ ممکن است 0.05 ثانیه طول بکشد. این به این دلیل است که الگوریتم نیازی به مقایسه های زیادی ندارد.

معایب نوع bucket

مرتب‌سازی bucket نسبت به سایر الگوریتم‌های مرتب‌سازی روی داده‌هایی که به طور یکنواخت توزیع نشده‌اند، با عملکرد بدترین حالت $O(n^2)$ کارآمدتر است. علاوه بر این، برای ذخیره سازی سطل ها به حافظه اضافی نیاز دارد که می تواند برای مجموعه داده های بسیار بزرگ مشکل ساز باشد.

تاریخچه مرتب سازی bucket

این روش در دهه 1950 پیاده سازی شده است و منابع ادعا می کنند که این روش از دهه 1940 وجود داشته است.

در هر صورت، این روزها هنوز در حال استفاده گسترده است.

در چه مواردی از برای مرتب سازی bucket استفاده کنید

درست مانند مرتب‌سازی سریع، مرتب‌سازی bucket را می‌توان به راحتی موازی کرد و برای مرتب‌سازی خارجی استفاده کرد، اما مرتب‌سازی bucket به‌ویژه در هنگام برخورد با داده‌های توزیع شده یکنواخت مفید است.

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

نحوه اجرای مرتب سازی bucket
لیستی از اقلام را به "bucket" تقسیم کنید.
هر bucket با استفاده از یک الگوریتم مرتب سازی متفاوت مرتب می شود.
سپس bucket ها دوباره در یک لیست مرتب شده ادغام می شوند.

مرتب سازی bucket در پایتون:

def bucket_sort(items):
    buckets = [[] for _ in range(len(items))]
    for item in items:
        bucket = int(item/len(items))
        buckets[bucket].append(item)
    for bucket in buckets:
        bucket.sort()
    return [item for bucket in buckets for item in bucket]

items = [6,20,8,19,56,23,87,41,49,53]
print(bucket_sort(items))

مرتب سازی bucket در جاوا اسکریپت:

function bucketSort(items) {
  let buckets = new Array(items.length);
  for (let i = 0; i < buckets.length; i++) {
    buckets[i] = [];
  }
  for (let j = 0; j < items.length; j++) {
    let bucket = Math.floor(items[j] / items.length);
    buckets[bucket].push(items[j]);
  }
  for (let k = 0; k < buckets.length; k++) {
    buckets[k].sort();
  }
  return [].concat(...buckets);
}

let items = [6, 20, 8, 19, 56, 23, 87, 41, 49, 53];
console.log(bucketSort(items));

مرتب سازی shell

مرتب‌سازی shell از یک الگوریتم مرتب‌سازی insertion استفاده می‌کند، اما به جای مرتب‌سازی کل لیست به یکباره، لیست به لیست‌های فرعی کوچک‌تر تقسیم می‌شود. سپس این زیر لیست ها با استفاده از یک الگوریتم مرتب سازی insertion مرتب می شوند، بنابراین تعداد تبادلات مورد نیاز برای مرتب سازی لیست کاهش می یابد.

همچنین به عنوان "روش شل" شناخته می شود، این روش ابتدا با تعریف دنباله ای از اعداد صحیح به نام دنباله افزایشی کار می کند. دنباله افزایش برای تعیین اندازه زیر لیست هایی که به طور مستقل مرتب می شوند استفاده می شود. متداول ترین دنباله افزایشی استفاده شده "دنباله Knuth" است که به صورت زیر تعریف می شود (که $h$ بازه با مقدار اولیه است و $n$ طول لیست است):

h = 1
while h < n:
  h = 3*h + 1

هنگامی که توالی افزایش تعریف شد، الگوریتم مرتب‌سازی shell با مرتب‌سازی لیست‌های فرعی آیتم های پیش می‌رود. لیست‌های فرعی با استفاده از الگوریتم مرتب‌سازی insertion، با ترتیب افزایشی به عنوان اندازه گام مرتب می‌شوند. این الگوریتم لیست‌های فرعی را مرتب می‌کند، از بزرگترین افزایش شروع می‌شود و سپس تا کوچک‌ترین افزایش تکرار می‌شود.

این الگوریتم زمانی متوقف می‌شود که اندازه افزایشی 1 باشد، که در آن نقطه معادل یک الگوریتم مرتب‌سازی insertion منظم است.

تاریخچه مرتب سازی shell

مرتب‌سازی shell توسط دونالد شل در سال 1959 به‌عنوان گونه‌ای از مرتب‌سازی insertion اختراع شد، که هدف آن بهبود عملکرد آن با شکستن لیست اصلی به لیست‌های فرعی کوچک‌تر و مرتب‌سازی این لیست‌های فرعی به طور مستقل است.

مزایای مرتب سازی shell

این یک تعمیم مرتب سازی insertion است و بنابراین درک و پیاده سازی آن آسان است.
این پیچیدگی زمانی دارد که برای بسیاری از توالی داده های ورودی بهتر از $O(n^2)$ است.
این یک الگوریتم مرتب سازی در لوکال است، به این معنی که به حافظه اضافی نیاز ندارد.

معایب مرتب سازی shell

پیش‌بینی پیچیدگی زمانی مرتب‌سازی shell می‌تواند دشوار باشد، زیرا به انتخاب ترتیب افزایشی بستگی دارد.

برای مرتب سازی shell از کیسه ها استفاده کنید

مرتب‌سازی shell یک الگوریتم همه منظوره برای مرتب‌سازی داده‌ها در برنامه‌های مختلف است، به‌ویژه هنگام مرتب‌سازی مجموعه‌های داده بزرگ مانند مرتب‌سازی سریع و مرتب‌سازی bucket.

مرتب سازی داده های عمدتاً مرتب شده مرتب‌سازی shell، تعداد مقایسه‌ها و مبادله‌های مورد نیاز برای مرتب‌سازی داده‌ها را کاهش می‌دهد. این باعث می شود در این سناریوی خاص، آن را سریعتر از سایر الگوریتم های مرتب سازی مانند مرتب سازی سریع یا مرتب سازی ادغام کنید.

مرتب سازی آرایه ها با تعداد معکوس کمی. وارونگی معیاری است که نشان می دهد یک آرایه چقدر مرتب نشده است و به عنوان تعداد جفت آیتم هایی که در ترتیب اشتباه هستند تعریف می شود. مرتب‌سازی shell نسبت به برخی از الگوریتم‌های دیگر مانند مرتب‌سازی حبابی یا مرتب‌سازی insertion هنگام مرتب‌سازی آرایه‌ها با تعداد معکوس‌های کم کارآمدتر است.

مرتب سازی در لوکال مرتب‌سازی shell برای مرتب‌سازی ورودی به حافظه اضافی نیاز ندارد، و آن را به یک رقیب برای مرتب‌سازی در لوکال تبدیل می‌کند. این باعث می شود آن را در شرایطی که حافظه محدود است یا زمانی که استفاده از حافظه اضافی نامطلوب است مفید باشد.

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

نحوه اجرای مرتب سازی shell

لیستی از آیتم ها را بر اساس برخی معیارها به "سطل" تقسیم کنید
هر سطل را جداگانه مرتب کنید
سطل های مرتب شده را با هم ترکیب کنید

اجرای مرتب سازی shell در پایتون:

def shell_sort(items):
    sublistcount = len(items)//2
    while sublistcount > 0:
        for start in range(sublistcount):
            gap_insertion_sort(items, start, sublistcount)
        sublistcount = sublistcount // 2
    return items

def gap_insertion_sort(items, start, gap):
    for i in range(start+gap, len(items), gap):
        currentvalue = items[i]
        position = i
        while position >= gap and items[position-gap] > currentvalue:
            items[position] = items[position-gap]
            position = position-gap
        items[position] = currentvalue

items = [6,20,8,19,56,23,87,41,49,53]
print(shell_sort(items))

اجرای مرتب سازی shell در جاوا اسکریپت:

function shellSort(items) {
  let sublistcount = Math.floor(items.length / 2);
  while (sublistcount > 0) {
    for (let start = 0; start < sublistcount; start++) {
      gapInsertionSort(items, start, sublistcount);
    }
    sublistcount = Math.floor(sublistcount / 2);
  }
  return items;
}

function gapInsertionSort(items, start, gap) {
  for (let i = start + gap; i < items.length; i += gap) {
    let currentValue = items[i];
    let position = i;
    while (position >= gap && items[position - gap] > currentValue) {
      items[position] = items[position - gap];
      position = position - gap;
    }
    items[position] = currentValue;
  }
}

let items = [6, 20, 8, 19, 56, 23, 87, 41, 49, 53];
console.log(shellSort(items));

مرتب سازی ادغام

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

مزایای مرتب سازی ادغام

مرتب‌سازی ادغام دارای پیچیدگی زمانی $O(n \log n)$ در بدترین سناریو است که آن را نسبت به سایر الگوریتم‌های مرتب‌سازی محبوب مانند مرتب‌سازی حبابی، مرتب‌سازی insertion یا مرتب‌سازی انتخابی کارآمدتر می‌کند.

مرتب سازی ادغام نیز یک الگوریتم است، به این معنی که نظم نسبی آیتم های برابر را حفظ می کند.

معایب مرتب سازب ادغام

در مورد استفاده از حافظه، مرتب سازی ادغام دارای معایبی است. الگوریتم به حافظه اضافی برای ذخیره دو نیمه لیست در مرحله تقسیم و همچنین حافظه اضافی برای ذخیره لیست مرتب شده نهایی در مرحله ادغام نیاز دارد. این می تواند در هنگام مرتب سازی لیست های بسیار بزرگ نگران کننده باشد.

تاریخچه ادغام مرتب سازی

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

در چه مواردی از برای مرتب سازی ادغام استفاده کنید

مرتب‌سازی ادغام یک الگوریتم مرتب‌سازی همه منظوره است که می‌تواند برای مرتب‌سازی مجموعه‌های داده بزرگ و در مرتب‌سازی خارجی (مرتب‌سازی سریع و مرتب‌سازی bucket) موازی‌سازی شود و همچنین معمولاً به‌عنوان بلوک ساختمانی برای الگوریتم‌های پیچیده‌تر (مانند مرتب‌سازی حبابی و insertion) استفاده می‌شود. مرتب سازی).

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

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

نحوه اجرای مرتب سازی ادغام

از بازگشت برای تقسیم یک لیست به لیست های فرعی کوچکتر و مرتب شده استفاده کنید
لیست‌های فرعی را دوباره با هم ادغام کنید، موارد را با یکدیگر مقایسه و مرتب کنید

پیاده سازی مرتب سازی ادغام در پایتون:

def merge_sort(items):
    if len(items) <= 1:
        return items

    mid = len(items) // 2
    left = items[:mid]
    right = items[mid:]

    left = merge_sort(left)
    right = merge_sort(right)

    return merge(left, right)

def merge(left, right):
    merged = []
    left_index = 0
    right_index = 0

    while left_index < len(left) and right_index < len(right):
        if left[left_index] > right[right_index]:
            merged.append(right[right_index])
            right_index += 1
        else:
            merged.append(left[left_index])
            left_index += 1

    merged += left[left_index:]
    merged += right[right_index:]

    return merged

items = [6,20,8,19,56,23,87,41,49,53]
print(merge_sort(items))

پیاده سازی مرتب سازی ادغام در جاوا اسکریپت:

function mergeSort(items) {
  if (items.length <= 1) {
    return items;
  }
  let mid = Math.floor(items.length / 2);
  let left = items.slice(0, mid);
  let right = items.slice(mid);
  return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right) {
  let merged = [];
  let leftIndex = 0;
  let rightIndex = 0;
  while (leftIndex < left.length && rightIndex < right.length) {
    if (left[leftIndex] > right[rightIndex]) {
      merged.push(right[rightIndex]);
      rightIndex++;
    } else {
      merged.push(left[leftIndex]);
      leftIndex++;
    }
  }
  return merged.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));
}

let items = [6, 20, 8, 19, 56, 23, 87, 41, 49, 53];
console.log(mergeSort(items));

مرتب سازی انتخابی

مرتب‌سازی انتخابی به‌طور مکرر کوچک‌ترین آیتم را از یک بخش مرتب‌نشده لیست انتخاب می‌کند و آن را با اولین آیتم از بخش مرتب‌نشده عوض می‌کند. این روند تا مرتب شدن کل لیست ادامه می یابد.

تاریخچه مرتب سازی انتخاب

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

این یکی از اولین الگوریتم‌های مرتب‌سازی بود که توسعه یافت و همچنان یک الگوریتم محبوب برای اهداف آموزشی و کارهای مرتب‌سازی ساده است.

مزایای مرتب سازی انتخاب

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

اشکالات مرتب سازی انتخاب

با وجود سادگی، مرتب‌سازی انتخابی در مقایسه با سایر الگوریتم‌های مرتب‌سازی مانند ادغام مرتب‌سازی یا مرتب‌سازی سریع کارآمد نیست. این پیچیدگی زمانی در بدترین حالت $O(n^2)$ دارد و مرتب کردن لیست‌های بزرگ ممکن است زمان زیادی ببرد.

مرتب‌سازی انتخابی نیز یک الگوریتم مرتب‌سازی پایدار نیست، به این معنی که ممکن است ترتیب آیتم های برابر را حفظ نکند.

در چه مواردی از برای مرتب سازی انتخاب استفاده کنید

مرتب‌سازی انتخابی مشابه مرتب‌سازی حبابی و مرتب‌سازی insertion است که می‌توان از آن برای مرتب‌سازی مجموعه‌های داده کوچک استفاده کرد و همچنین سادگی آن را به ابزاری مفید برای آموزش و یادگیری در مورد الگوریتم‌های مرتب‌سازی تبدیل می‌کند. کاربردهای دیگر عبارتند از:

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

نحوه اجرای مرتب سازی انتخاب

در لیست تکرار کنید، پایین ترین مورد را انتخاب کنید
پایین ترین مورد را با مورد در موقعیت فعلی تعویض کنید
این روند را برای بقیه لیست تکرار کنید

اجرای مرتب سازی انتخاب در پایتون:

def selection_sort(items):
    for i in range(len(items)):
        min_idx = i
        for j in range(i+1, len(items)):
            if items[min_idx] > items[j]:
                min_idx = j
        items[i], items[min_idx] = items[min_idx], items[i]
    return items

items = [6,20,8,19,56,23,87,41,49,53]
print(selection_sort(items))

اجرای مرتب سازی انتخاب در جاوا اسکریپت:

function selectionSort(items) {
  let minIdx;

  for (let i = 0; i < items.length; i++) {
    minIdx = i;
    for (let j = i + 1; j < items.length; j++) {
      if (items[j] < items[minIdx]) {
        minIdx = j;
      }
    }
    let temp = items[i];
    items[i] = items[minIdx];
    items[minIdx] = temp;
  }
  return items;
}

let items = [6, 20, 8, 19, 56, 23, 87, 41, 49, 53];
console.log(selectionSort(items));

مرتب سازی رادیکس

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

بدترین عملکرد آن ${O(w\cdot n)}$ است که $n$ تعداد کلیدها و $w$ طول کلید است.

تاریخچه مرتب سازی رادیکس

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

بعدها توسط چندین محقق در اواسط قرن بیستم اقتباس و رایج شد تا داده‌های باینری را با گروه‌بندی داده‌ها بر اساس هر بیت در نمایش باینری مرتب کنند. اما برای مرتب‌سازی داده‌های رشته‌ای نیز استفاده می‌شود، جایی که هر کاراکتر به عنوان یک رقم در مرتب‌سازی در نظر گرفته می‌شود.

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

مزایای مرتب سازی رادیکس

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

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

مرتب‌سازی رادیکس نیز یک الگوریتم مرتب‌سازی پایدار است، به این معنی که ترتیب نسبی آیتم های برابر را حفظ می‌کند.

در چه مواردی از برای مرتب سازی ریشه استفاده کنید

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

پردازش موازی. مرتب‌سازی رادیکس اغلب برای مرتب‌سازی مجموعه‌های داده بزرگ (به جای مرتب‌سازی ادغامی، مرتب‌سازی سریع و مرتب‌سازی bucket) ترجیح داده می‌شود. و مانند مرتب‌سازی bucket، radix می‌تواند داده‌های رشته‌ای را به طور موثر مرتب کند، که آن را برای برنامه‌های پردازش زبان طبیعی مناسب می‌کند.
مرتب سازی داده ها با کلیدهای با طول ثابت مرتب‌سازی رادیکس به‌ویژه هنگام مرتب‌سازی داده‌ها با کلیدهای با طول ثابت کارآمد است، زیرا می‌تواند مرتب‌سازی را با بررسی هر کلید یک رقمی در یک زمان انجام دهد.

نحوه پیاده سازی مرتب سازی رادیکس

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

پیاده سازی مرتب سازی رادیکس در پایتون:

def radix_sort(items):
    max_length = False
    tmp, placement = -1, 1

    while not max_length:
        max_length = True
        buckets = [list() for _ in range(10)]

        for i in items:
            tmp = i // placement
            buckets[tmp % 10].append(i)
            if max_length and tmp > 0:
                max_length = False

        a = 0
        for b in range(10):
            buck = buckets[b]
            for i in buck:
                items[a] = i
                a += 1

        placement *= 10
    return items

items = [6,20,8,19,56,23,87,41,49,53]
print(radix_sort(items))

پیاده سازی مرتب سازی رادیکس در جاوا اسکریپت:

function radixSort(items) {
  let maxLength = false;
  let tmp = -1;
  let placement = 1;

  while (!maxLength) {
    maxLength = true;
    let buckets = Array.from({ length: 10 }, () => []);

    for (let i = 0; i < items.length; i++) {
      tmp = Math.floor(items[i] / placement);
      buckets[tmp % 10].push(items[i]);
      if (maxLength && tmp > 0) {
        maxLength = false;
      }
    }

    let a = 0;
    for (let b = 0; b < 10; b++) {
      let buck = buckets[b];
      for (let j = 0; j < buck.length; j++) {
        items[a] = buck[j];
        a++;
      }
    }

    placement *= 10;
  }
  return items;
}

let items = [6, 20, 8, 19, 56, 23, 87, 41, 49, 53];
console.log(radixSort(items));

مرتب سازی شانه ای

مرتب‌سازی شانه‌ای جفت‌هایی از آیتم های را با فاصله مشخصی از هم مقایسه می‌کند و در صورت نامرتب بودن، آن‌ها را تعویض می‌کند. فاصله بین جفت ها در ابتدا به اندازه لیست در حال مرتب سازی تنظیم می شود و سپس با یک ضریب (به نام "ضریب کوچک شدن") با هر پاس کاهش می یابد تا به حداقل مقدار $1$ برسد. این فرآیند تا مرتب شدن کامل لیست تکرار می شود.

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

تاریخچه مرتب سازی شانه

الگوریتم مرتب سازی شانه ای یک الگوریتم مرتب سازی نسبتاً جدید است که اولین بار در سال 1980 توسط Włodzimierz Dobosiewicz و Artur Borowy معرفی شد. این الگوریتم از ایده استفاده از شانه برای صاف کردن موهای درهم الهام گرفته شده است و از فرآیند مشابهی برای صاف کردن لیستی از مقادیر مرتب نشده استفاده می کند.

مزایای مرتب سازی شانه ای

مرتب‌سازی شانه‌ای در بدترین حالت پیچیدگی زمانی $O(n^2)$ دارد، اما در عمل اغلب سریع‌تر از سایر الگوریتم‌های مرتب‌سازی $O(n^2)$ مانند مرتب‌سازی حبابی است، زیرا از ضریب کوچک شدن استفاده می‌کند. . ضریب انقباض به الگوریتم اجازه می دهد تا به سرعت مقادیر بزرگ را به سمت موقعیت صحیح خود حرکت دهد و تعداد پاس های مورد نیاز برای مرتب سازی کامل لیست را کاهش دهد.

در چه مواردی از برای مرتب سازی شانه استفاده کنید

مرتب‌سازی شانه‌ای یک الگوریتم مرتب‌سازی نسبتا ساده و کارآمد است که موارد استفاده متعددی در کاربردهای مختلف دارد.

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

نحوه اجرای مرتب سازی شانه ای

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

اجرای مرتب سازی شانه ای در پایتون:

def comb_sort(items):
    gap = len(items)
    shrink = 1.3
    sorted = False
    while not sorted:
        gap //= shrink
        if gap <= 1:
            sorted = True
        else:
            for i in range(len(items)-gap):
                if items[i] > items[i+gap]:
                    items[i],items[i+gap] = items[i+gap],items[i]
    return bubble_sort(items)

def bubble_sort(items):
    for i in range(len(items)):
        for j in range(len(items)-1-i):
            if items[j] > items[j+1]:
                items[j], items[j+1] = items[j+1], items[j]
    return items

items = [6,20,8,19,56,23,87,41,49,53]
print(comb_sort(items))

اجرای مرتب سازی شانه ای در جاوا اسکریپت:

function combSort(items) {
  let gap = items.length;
  let shrink = 1.3;
  let sorted = false;
  while (!sorted) {
    gap = Math.floor(gap / shrink);
    if (gap <= 1) {
      sorted = true;
    } else {
      for (let i = 0; i < items.length - gap; i++) {
        if (items[i] > items[i + gap]) {
          let temp = items[i];
          items[i] = items[i + gap];
          items[i + gap] = temp;
        }
      }
    }
  }
  return bubbleSort(items);
}

function bubbleSort(items) {
  let swapped;
  do {
    swapped = false;
    for (let i = 0; i < items.length - 1; i++) {
      if (items[i] > items[i + 1]) {
        let temp = items[i];
        items[i] = items[i + 1];
        items[i + 1] = temp;
        swapped = true;
      }
    }
  } while (swapped);
  return items;
}

let items = [6, 20, 8, 19, 56, 23, 87, 41, 49, 53];
console.log(combSort(items));

مرتب سازی تیمسورت

الگوریتم Timsort با تقسیم داده های ورودی به زیر آرایه های کوچکتر و سپس استفاده از مرتب سازی insertion برای مرتب سازی این زیر آرایه ها کار می کند. سپس این زیر آرایه های مرتب شده با استفاده از مرتب سازی ادغام شده ترکیب می شوند تا یک آرایه کاملا مرتب شده تولید شود.

Timsort دارای پیچیدگی زمانی در بدترین حالت $O(n \log n)$ است که آن را برای مرتب‌سازی مجموعه‌های داده بزرگ کارآمد می‌کند. همچنین یک الگوریتم مرتب‌سازی پایدار است، به این معنی که نظم نسبی آیتم های برابر را حفظ می‌کند.

مزایای تیمسورت

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

یکی دیگر از ویژگی های مهم Timsort توانایی آن در مدیریت داده هایی است که تا حدی مرتب شده اند. در این حالت، Timsort می‌تواند مناطق جزئی مرتب‌شده را شناسایی کند و از مرتب‌سازی insertion برای مرتب‌سازی سریع آنها استفاده کند و زمان لازم برای مرتب‌سازی کامل داده‌ها را کاهش دهد.

تاریخچه تیمسورت

Timsort توسط تیم پیترز در سال 2002 برای استفاده در زبان برنامه نویسی پایتون توسعه یافت. این یک الگوریتم مرتب‌سازی ترکیبی است که از ترکیبی از تکنیک‌های مرتب‌سازی insertion و مرتب‌سازی ادغام استفاده می‌کند و برای مرتب‌سازی کارآمد انواع مختلف داده‌ها طراحی شده است.

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

در چه مواردی از برای تیمسورت استفاده کنید

به عنوان یک الگوریتم پیشرفته، Timsort می تواند هنگام مرتب سازی داده ها در سیستم های دارای محدودیت حافظه استفاده شود.

مرتب سازی در زبان های برنامه نویسی Timsort اغلب به عنوان الگوریتم مرتب‌سازی پیش‌فرض در این زبان‌ها استفاده می‌شود، زیرا کارایی و توانایی آن در مدیریت انواع مختلف داده‌ها دارد.
مرتب سازی داده های دنیای واقعی Timsort به ویژه هنگام مرتب‌سازی داده‌های دنیای واقعی که ممکن است تا حدی مرتب شده باشند یا حاوی آرایه‌های فرعی مرتب‌شده باشند، کارآمد است، زیرا می‌تواند این اجراها را شناسایی کند و از مرتب‌سازی insertion برای مرتب‌سازی سریع آنها استفاده کند و زمان لازم برای مرتب‌سازی کامل داده‌ها را کاهش دهد.
مرتب سازی داده ها با انواع مختلف برای مدیریت کارآمد انواع مختلف داده ها، از جمله اعداد، رشته ها و اشیاء سفارشی طراحی شده است. می‌تواند اجرای داده‌هایی با همان نوع را شناسایی کرده و با استفاده از مرتب‌سازی ادغام، آنها را به طور موثر ترکیب کند و تعداد مقایسه‌ها و مبادله‌های مورد نیاز را کاهش دهد.

نحوه اجرای تیمسورت

یک لیست مرتب نشده بردارید و آن را به لیست های فرعی کوچکتر و مرتب شده تقسیم کنید.
لیست های فرعی را با هم ادغام کنید تا یک لیست مرتب و بزرگتر تشکیل شود.
این روند را تکرار کنید تا کل لیست مرتب شود.

پیاده سازی Timsort در پایتون:

def insertion_sort(arr, left=0, right=None):
    if right is None:
        right = len(arr) - 1

    for i in range(left + 1, right + 1):
        key_item = arr[i]
        j = i - 1
        while j >= left and arr[j] > key_item:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key_item

    return arr

def merge(left, right):
    if not left:
        return right

    if not right:
        return left

    if left[0] < right[0]:
        return [left[0]] + merge(left[1:], right)

    return [right[0]] + merge(left, right[1:])

def timsort(arr):
    min_run = 32
    n = len(arr)

    for i in range(0, n, min_run):
        insertion_sort(arr, i, min((i + min_run - 1), n - 1))

    size = min_run
    while size < n:
        for start in range(0, n, size * 2):
            midpoint = start + size - 1
            end = min((start + size * 2 - 1), (n-1))
            merged_array = merge(
                left=arr[start:midpoint + 1],
                right=arr[midpoint + 1:end + 1]
            )
            arr[start:start + len(merged_array)] = merged_array

        size *= 2

    return arr

items = [6,20,8,19,56,23,87,41,49,53]
print(timsort(items))

پیاده سازی Timsort در جاوا اسکریپت:

function insertionSort(arr, left = 0, right = arr.length - 1) {
  for (let i = left + 1; i <= right; i++) {
    const keyItem = arr[i];
    let j = i - 1;
    while (j >= left && arr[j] > keyItem) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = keyItem;
  }
  return arr;
}

function merge(left, right) {
  let i = 0;
  let j = 0;
  const merged = [];

  while (i < left.length && j < right.length) {
    if (left[i] < right[j]) {
      merged.push(left[i]);
      i++;
    } else {
      merged.push(right[j]);
      j++;
    }
  }

  return merged.concat(left.slice(i)).concat(right.slice(j));
}

function timsort(arr) {
  const minRun = 32;
  const n = arr.length;

  for (let i = 0; i < n; i += minRun) {
    insertionSort(arr, i, Math.min(i + minRun - 1, n - 1));
  }

  let size = minRun;
  while (size < n) {
    for (let start = 0; start < n; start += size * 2) {
      const midpoint = start + size - 1;
      const end = Math.min(start + size * 2 - 1, n - 1);
      const merged = merge(
        arr.slice(start, midpoint + 1),
        arr.slice(midpoint + 1, end + 1)
      );
      arr.splice(start, merged.length, ...merged);
    }
    size *= 2;
  }

  return arr;
}

let items = [6, 20, 8, 19, 56, 23, 87, 41, 49, 53];
console.log(timsort(items));

رایج ترین الگوریتم مرتب سازی چیست؟

متداول ترین الگوریتم مرتب سازی احتمالاً مرتب سازی سریع است. این به طور گسترده در بسیاری از زبان های برنامه نویسی از جمله C، C++، جاوا و پایتون و همچنین در بسیاری از برنامه های کاربردی نرم افزاری و کتابخانه ها استفاده می شود. Quicksort به دلیل کارایی و تطبیق پذیری آن در مدیریت انواع مختلف داده ها مورد علاقه است و اغلب به عنوان الگوریتم مرتب سازی پیش فرض در زبان های برنامه نویسی و چارچوب های نرم افزار استفاده می شود.

با این حال، سایر الگوریتم‌های مرتب‌سازی مانند merge sort و Timsort نیز به دلیل کارایی و ویژگی‌های منحصربه‌فرد، معمولاً در برنامه‌های مختلف استفاده می‌شوند.

نتجیه

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

بهترین انتخاب الگوریتم مرتب سازی به عوامل مختلفی از جمله اندازه داده های ورودی، توزیع داده ها، حافظه موجود و پیچیدگی زمانی مورد نظر بستگی دارد.

الگوریتم‌های مرتب‌سازی را می‌توان بر اساس پیچیدگی زمانی، پیچیدگی فضایی، مرتب‌سازی در لوکال، مرتب‌سازی پایدار و مرتب‌سازی تطبیقی دسته‌بندی کرد. درک ویژگی‌ها و مبادلات الگوریتم‌های مرتب‌سازی مختلف برای انتخاب مناسب‌ترین الگوریتم برای یک مورد استفاده خاص، مهم است.

نظر شما در مورد این الگورتیم ها چیست؟ و از کدام الگوریتم مرتب سازی به چه دلیلی استفاده کردید؟ در قسمت نظرات با آنوفل به اشتراک بگذارید.

بهترین الگوریتم های مرتب سازی در پایتون و جاوا اسکریپت

Mohammad Abdorrahmani