الگوریتم مرتب‌سازی حبابی + کد پایتون + کد سی + کد سی شارپ + کد سی پلاس پلاس

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

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

1. در یک دور پیمایش جابجایی صورت نگیرد.یعنی در آن دور عددی پیدا نشود که از عدد بعدی خود بزرگتر(یا بصورت نزولی کوچکتر) باشد و جایش با عدد بعدی عوض نشود.
2. روش دوم که روش من درآوردی است(خودم ساختمش!) این است که یک تابع جدا بنویسید که یکبار مجموعه را از اول تا آخر پیمایش کند و اگر عددی پیدا نشد که از عدد بعدیش بزرگتر باشد پس فهرست‌ما مرتب است.

روش پیشنهاد شده روش اول است.

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

5 3 2

3 2 5

2 3 5

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

حال یک مجموعه چهار عضوی را مرتب میکنیم:

54 8 41 8

8 41 8 54

8 8 41 54

باز مجموعه در سه مرحله مرتب شد! اما این به این معنی نیست که همیشه در سه مرحله یک مجموعه مرتب میشود:

456 12 84 4 4 2

12 84 4 4 2 456

12 4 4 2 84 456

4 4 2 12 84 456

4 2 4 12 84 456

2 4 4 12 84 456

تصویر زیر میتواند به شما در درک سریع تر و بهتر این الگوریتم کمک کند(تصویر متحرک است)

 

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

سی:

//Bubble Sort Algorithm
#include <stdio.h>

void swap(int *a,int *b){
    int temp = *a;
    *a = *b;
    *b = temp;
}

int issorted(int arr[]){
    for(int i = 0;i < 10;i++){
        if(!(arr[i] <= arr[i+1]))
            return 0;
    }
    return 1;
}

int main(){
    int arr[10];
    //filling the array
    for (int i = 0;i < 10;i++){
        printf("\nEnter Element %i: ",i);
        scanf("%i",&arr[i]);
    }
    //showing the array
    for (int i = 0;i < 10;i++){
        printf("Element #%i is #%i\n",i,arr[i]);
    }
    printf("Starting sorting...\n");
    //sorting the array
    while(issorted(arr) == 0){//Until issorted returned 0 that means false
        for (int i = 0;i < 10;i++){
            if(arr[i] > arr[i+1])
                swap(&arr[i],&arr[i+1]);
        }
    }

در کد بالا تابع swap مقدار دو متغیر عدد صحیح را باهم جابجا میکند و تابع issorted نیز همانطور که از نامش پیداست چک میکند که آرایه مرتب شده است یا خیر.

سی‌شارپ:

//Bubble Sort in CSharp
//Author: Farooq Karimi Zadeh
using System;

class Program{
    static void Main(){
        int[10] ary;
        for (int i = 0;i<10;i++){
            Console.Write("Enter elemnt #"+i.ToString()+": ");
            ary[i] = (int)Console.ReadLine();
        }
        ary = sort(ary);
    }
    static void swap(ref int a,ref int b){
        int tmp = a;
        a = b;
        b = tmp;
    }
    static int[] sort(int[] ary){
        bool change = true;
        while( change){
        change = false;
            for (int i=0;i<10;i++){
                if (i!=9){
                    if (ary[i]>ary[i+1]){
                        swap(ref ary[i],ary[i+1]);
                        change = true;
                    }
                }
            }
        }
        return ary;
    }
    static void print(int[] ary){
        foreach (int i in ary){
            Console.Write(i.ToString() + ",");
        }
    }
}

سی‌پلاس‌پلاس(من تجربه‌ی زیادی با این زبان ندارم پس شاید بخواهید کد بهتری روی اینترنت پیدا کنید):

#include<iostream>
using namespace std;

void swap(int *a,int *b);
int[] sort(int arr[]);
void print(int arr[]);

int main(){
    int arr[10];
    for (int i=1;i<10;i++){
        cout << "Enter element #" << i << ": " << endl;
        cin >> arr[i];
    }
    print(arr);
    arr = sort(arr);
    cout << "Sorted: "; 
    print(arr);
}
int[] sort(int arr[]) {
      bool swapped = true;
      int j = 0;
      int tmp;
      while (swapped) {
            swapped = false;
            j++;
            for (int i = 0; i < n - j; i++) {
                  if (arr[i] > arr[i + 1]) {
                        swap(&arr[i],&arr[i+1]);
                        swapped = true;
                  }
            }
      }
      return arr;
}
void print(int arr[]){
    for(int i = 0;i<10;i++){
        cout << arr[i] << ",";
    }
    cout << endl;
}
void swap(int *a,int *b){
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

پایتون:

def bubbleSort(alist):
    for passnum in range(len(alist)-1, 0, -1):
        for i in range(passnum):
            if alist[i] > alist[i+1]:
                alist[i+1], alist[i] = alist[i], alist[i+1]   

alist = [54, 26, 93, 17, 77, 31, 44, 55, 20]
bubbleSort(alist)
print(alist)

یک نسخه‌ی دیگر از این الگوریتم در پایتون(که من با حدود یک سال تجربه بیشتر نوشتمش):

def bubblesort(alist):
    swapped = True
    while swapped:
        swapped = False
        for i, v in enumerate(alist):
            if i == len(alist)-1:
                continue
            if v > alist[i+1]:
                alist[i], alist[i+1] = alist[i+1], alist[i]
                swapped = True
    return alist

L = eval(input("Enter a List: "))
print(bubblesort(L))