الگوریتم‌های مرتب‌سازی یا Sorting Algorithm

الگوریتم‌ها ستون فقرات دنیای برنامه‌نویسی هستن و درک اون‌ها به شما کمک می‌کنه که برنامه‌های کارآمدتر و بهینه‌تری بنویسید. اینکه کدوم الگوریتم‌ها “پُراستفاده‌تر” هستند، بستگی به زمینه‌ی کاری شما داره (مثلاً وب، داده‌کاوی، هوش مصنوعی، بازی‌سازی و …) اما می‌تونیم به دسته‌های کلی و پرکاربرد اشاره کنیم که توی این بخش قراره درمورد الگوریتم‌های مرتب‌سازی بخونیم :

برای هر الگوریتم با دو زبان javascript و python کدش رو میبینیم :)

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

در این بخش الگوریتم های زیر رو یادمیگیریم:

1) Bubble Sort

2) Insertion Sort

3) Merge Sort

4) Quick Sort

5) Counting Sort

6) Bucket Sort

مرتب‌سازی حبابی (Bubble Sort):

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

این کارو تا زمانی تکرار می‌کنه که لیست کاملاً مرتب بشه.

پیچیدگی زمانی: O(n²) → یعنی برای داده های زیاد مناسب نیست و کند عمل میکنه

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

python


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

print(bubble_sort([5, 3, 8, 4, 2]))

javascript


function bubbleSort(arr) {
    for (let i = 0; i < arr.length; i++) {
        for (let j = 0; j < arr.length - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                [arr[j], arr[j+1]] = [arr[j+1], arr[j]];
            }
        }
    }
    return arr;
}

console.log(bubbleSort([5, 3, 8, 4, 2]));

مرتب‌سازی درجی (Insertion Sort):

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

یک بخش مرتب داریم و عنصر جدید را به مکان درست در آن وارد می‌کنیم.

• پیچیدگی: O(n²) این هم مثل Bubble Sort کند هستش و برای لیست های کوچک مناسب تر هستش

برای لیست هایی که تقریبا مرتب هستن خیلی خوب کار میکنه

python


def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1

        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1

        arr[j + 1] = key

    return arr

print(insertion_sort([9, 5, 1, 3, 7]))

javascript


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

console.log(insertionSort([9, 5, 1, 3, 7]));

مرتب‌سازی ادغامی (Merge Sort):

کارآمد، پایدار و مناسب برای مجموعه داده‌های بزرگ.

الگوریتم Merge Sort از روش تقسیم و حل (Divide and Conquer) استفاده می‌کند:

یعنی چی؟

1. لیست را نصف می‌کند

2. دو نیمه را مرتب می‌کند

3. دو نیمه مرتب شده را ادغام می‌کند

پیچیدگی : O(n log n) → بسیار سریع هست و برای لیست های بزرگ مناسب هستش

Merge Sort پایدار هستش و مناسب برای داده‌های زیاد اما نیاز به حافظه اضافی دارد :)

python
def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    
    result = []
    i = j = 0
    
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1

    result.extend(left[i:])
    result.extend(right[j:])
    return result

print(merge_sort([8, 3, 5, 9, 1]))

javascript
function mergeSort(arr) {
    if (arr.length <= 1) return arr;

    const mid = Math.floor(arr.length / 2);
    const left = mergeSort(arr.slice(0, mid));
    const right = mergeSort(arr.slice(mid));

    let result = [];
    let i = 0, j = 0;

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

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

console.log(mergeSort([8, 3, 5, 9, 1]));

مرتب‌سازی سریع (Quick Sort):🏃🏻‍♀️

اکثر توضیحاتی که درمورد Quick Sort میخونم میبینم که خیلی پیچیدش کردن درحالی که خیلی سادست :)

Quick Sort از همون روش تقسیم و حل (Divide and Conquer) استفاده می‌کنه دقیقا مثل Merge Sort؛ یعنی مسئله‌ی بزرگ را به چند مسئله‌ی کوچک‌تر تقسیم می‌کند و هر قسمت را جداگانه مرتب میکند تا در نهایت کل مجموعه به‌صورت منظم در بیاید.

فرایند کار Quick Sort به زبان ساده اینطوری میشه :

1. یک محور انتخاب میکنیم (Pivot):

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

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

2. تقسیم داده‌ها:

   تمام عناصر لیست را با محور مقایسه می‌کنیم.

   • آن‌هایی که کوچکتر از محور هستند در سمت چپ قرار می‌گیرند،

   • و آن‌هایی که بزرگتر از محور هستند در سمت راست.

3. اجرای بازگشتی (Recursive):

   سپس همین کار را برای دو بخشِ چپ و راست تکرار می‌کنیم تا هر بخش خودش کاملاً مرتب شود.

   در پایان، وقتی هیچ بخش دیگه ای برای تقسیم باقی نموند، همه‌ی داده‌هارو به‌ صورت منظم از کوچک به بزرگ (یا برعکس، بسته به نوع مرتب‌سازی) پشت سر هم قرار می‌گیرند.

سرعت بالا در عمل (میانگین زمان اجرا: O(n log n))

Quick Sort در حالت معمول پیچیدگی زمانی ثابتی نداره و بدترین حالتش ( O(n²) ) وقتی اتفاق میفته که لیست از قبل مرتب باشه :/ !

استفاده‌ی هوشمند از حافظه

مناسب برای داده‌های بزرگ

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

اگه دیدین جایی نوشته سریع ترین الگوریتم در عمل منظورشون اینه در دنیای واقعی و هنگام اجرا، خیلی کم پیش میاد الگوریتم سریع‌تری از این پیدا بشه :)

python


def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    
    pivot = arr[len(arr)//2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    
    return quick_sort(left) + middle + quick_sort(right)

print(quick_sort([6, 3, 8, 1, 7, 2]))

javascript


function quickSort(arr) {
    if (arr.length <= 1) return arr;

    const pivot = arr[Math.floor(arr.length / 2)];
    const left = arr.filter(x => x < pivot);
    const middle = arr.filter(x => x === pivot);
    const right = arr.filter(x => x > pivot);

    return [...quickSort(left), ...middle, ...quickSort(right)];
}

console.log(quickSort([6, 3, 8, 1, 7, 2]));

مرتب‌سازی شمارشی (Counting Sort): 🔢

Counting Sort یک الگوریتم مرتب‌سازی غیر مقایسه‌ای هستش. این یعنی برخلاف الگوریتم‌هایی مثل Quick Sort یا Bubble Sort که عناصر را با هم مقایسه می‌کنند، Counting Sort از روش دیگه ای استفاده می‌کند، شمارش تعداد تکرار هر عنصر.

الگوریتم Counting Sort زمانی مناسب هستش که دسته بندی های مشخصی وجود داشته باشه
مثلا 3 رنگ سیب ، 7 مدل مبل ، 4 مدل تخت

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

۱. یک سبد برای سیب‌های قرمز، یک سبد برای زرد و یک سبد برای سبز برمیداریم.

۲. هر سیبی را که برمی‌داریم، در سبد رنگ خودش می‌اندازیم.

۳. در آخر، ابتدا همه‌ی سیب‌های سبد اول (مثلاً قرمز)، بعد همه‌ی سیب‌های سبد دوم (مثلاً زرد) و سپس سبد سوم (مثلاً سبز) را برمی‌داریم. به همین سادگی مرتب شدند!

فرایند کار Counting Sort به زبان ساده اینطوری میشه :

1. پیدا کردن بزرگترین عدد:

ابتدا بزرگترین عدد در مجموعه‌ی ورودی را پیدا می‌کنیم. این کار به ما کمک می‌کند تا اندازه‌ی آرایه کمکی مورد نیاز را تعیین کنیم.

2. ایجاد آرایه شمارنده:

یک آرایه جدید (آرایه شمارنده) به اندازه‌ی «بزرگترین عدد + ۱» می‌سازیم و همه‌ی خانه‌های آن را با صفر پر می‌کنیم. این آرایه قرار است تعداد تکرار هر عدد را نگه دارد.

3. شمارش تکرارها:

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

4. توزیع عناصر مرتب شده:

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

در پایان، مجموعه‌ی خروجی شامل تمام اعداد ورودی خواهد بود که به ترتیب مرتب شده‌اند.

Counting Sort بسیار سریع وقتی محدوده‌ی اعداد کوچک است (زمان اجرا: O(n + k) که n تعداد عناصر و k محدوده‌ی اعداد است).

غیر مقایسه‌ای است.

برای مرتب‌سازی رشته‌ها (با حروف الفبا) یا داده‌هایی با محدوده‌ی مشخص نیز قابل استفاده است.

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

python


def counting_sort(arr):
    max_val = max(arr)
    count = [0] * (max_val + 1)

    for num in arr:
        count[num] += 1

    result = []
    for num, c in enumerate(count):
        result.extend([num] * c)

    return result

print(counting_sort([4, 2, 2, 8, 3, 3, 1]))

javascript


function countingSort(arr) {
    const max = Math.max(...arr);
    const count = Array(max + 1).fill(0);

    for (let num of arr) count[num]++;

    const result = [];
    for (let i = 0; i < count.length; i++) {
        while (count[i]--) result.push(i);
    }

    return result;
}

console.log(countingSort([4, 2, 2, 8, 3, 3, 1]));

مرتب‌سازی سطلی (Bucket Sort)🪣🚮

تصور کن کلی توپ داری که اعداد مختلفی روشون نوشته شده و می‌خوای اون‌ها رو مرتب کنی. مرتب‌سازی سطلی شبیه اینه که:

1. چند تا سطل (Bucket) آماده می‌کنی. تعداد سطل‌ها معمولاً به تعداد داده‌ها یا کمی بیشتر از اونه.

2. هر توپ رو برمی‌داری و بر اساس عددی که روش نوشته شده، می‌ندازی توی سطل مناسب. مثلاً اگه سطل‌ها برای بازه‌های ۰-۹، ۱۰-۱۹، ۲۰-۲۹ و… باشن، توپ با عدد ۲۳ رو می‌ندازی توی سطل ۲۰-۲۹.

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

4. در نهایت، توپ‌های مرتب شده‌ی داخل سطل‌ها رو به همون ترتیب سطل‌ها، پشت سر هم می‌ریزی :)

یا ساده تر :)

داده‌ها در سطل‌ها (bucket) قرار میگیرن

هر سطل با الگوریتمی مثل insertion sort مرتب میشه

همه سطل‌ها کنار هم قرار می‌گیرن

• کارآمد برای توزیع یکنواخت: وقتی اعداد در بازه‌های مشخصی پخش شده باشند (مثلاً 0 تا 1).

• نیاز به مرتب‌سازی داخلی: برای مرتب کردن سطل‌ها از الگوریتم دیگری (مثل Insertion Sort) استفاده می‌کند.

python

def bucket_sort(arr):
    buckets = [[] for _ in range(10)]

    for num in arr:
        index = int(num * 10)
        buckets[index].append(num)

    for i in range(10):
        buckets[i].sort()

    result = []
    for bucket in buckets:
        result.extend(bucket)

    return result

print(bucket_sort([0.42, 0.32, 0.23, 0.52, 0.25]))

javascript


function bucketSort(arr) {
    const buckets = Array.from({ length: 10 }, () => []);

    for (let num of arr) {
        const index = Math.floor(num * 10);
        buckets[index].push(num);
    }

    buckets.forEach(b => b.sort());

    return buckets.flat();
}

console.log(bucketSort([0.42, 0.32, 0.23, 0.52, 0.25]));

امیدوارم که مطالب رو واضح و ساده بیان کرده باشم :)

برام بنویسید که بیشتر ترجیح میدین پست های طولانی مثل این رو بزارم یا نکته های کوچیک برنامه نویسی رو توی هر پست توضیح بدم

اگر سوالی داشتین یا پیشنهادی برای بهتر کردن مطالب داشتین توی کامنت ها باهام به اشتراک بزارید، حتما لحاظشون میکنم :)💕