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

آموزش الگوریتم مرتب سازی حبابی (Bubble Sort) از 0 تا 100

این صفحه مرتب سازی حبابی (Bubble Sort) را بصورت 0 تا 100 آموزش داده و کدهای مرتب سازی حبابی در C++، پایتون و جاوا آورده شده است شده

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

مرتب‌ سازی حبابی چیست؟

همان‌طور که اشاره شد، مرتب‌ سازی حبابی در ساختمان داده یک مرتب‌سازی از نوع مقایسه‌ای است که هر عنصر را با عناصر مجاورش مقایسه می‌کند و درصورتی که از عنصر مجاورش، بزرگ‌تر باشد، مکان این دو عنصر عوض می‌شود. در این روش، آرایه n عنصری، n-1 بار پیمایش می‌شود و در هر بار پیمایش، عنصر ماکزیمم (Maximum) به آخرین خانه از آرایه منتقل می‌شود و سپس یک خانه از آرایه کم می‌شود.

در صورتیکه به این مقاله علاقه‌مند هستید، ممکن است صفحات زیر نیز برای شما جذاب باشد:

  1. آموزش جامع مرتب سازی سریع
  2. آموزش جامع مرتب سازی درجی
  3. آموزش جامع مرتب سازی ادغامی

الگوریتم مرتب سازی حبابی

حال باید الگوریتم مرتب سازی حبابی یا الگوریتم Bubble Sort را بررسی کنیم. همان‌طور که اشاره شد، یک آرایه n عنصری، n-1 بار پیمایش می‌شود تا آرایه به‌طور کامل مرتب شود. برای اینکه این الگوریتم را بررسی کنیم، درابتدا یک مثالی را بررسی می‌کنیم تا با نحوه‌ی پیاده سازی مرتب سازی حبابی آشنا شویم.

فرض کنید آرایه از عناصر به شکل زیر داریم :

3 2 1 0
1 10 40 20

بر اساس الگوریتمی که بیان شد، n-1 بار آرایه را پیمایش می‌کنیم و در هر پیمایش، عنصر ماکزیمم را به انتهای آرایه می‌رسانیم :

A[0], A[1]  =>  20  40  10  1

A[1], A[2]  =>  20  10  40  1

A[2], A[3]  =>  20  10  1  40

حال در توضیح پیمایش اول، در ابتدا خانه‌ی صفر و یک آرایه را باهم مقایسه می‌کنیم. اگر خانه‌ی صفرم از خانه‌ی یکم بزرگ‌تر بود، این دو خانه را تعویض می‌کنیم و در غیر این‌ صورت تعویض صورت نمی‌گیرد. ما A[0] را با A[1] مقایسه کردیم و چون A[0] از A[1] بزرگ‌تر نیست، درنتیجه تعویضی صورت نمی‌گیرد و آرایه در همان حالت باقی می‌ماند.

سپس خانه یکم و دوم آرایه را مقایسه کردیم و A[1]>A[2] پس مکان این دو خانه تعویض می‌شود. این روند را تا جایی ادامه می‌دهیم که عنصر ماکزیمم به اخرین خانه‌ی آرایه منتقل شود که در این جا عدد 40 است.

حال یک خانه از آرایه کم می‌شود و به‌سراغ مرتب کردن آرایه جدید که به شکل زیر است می‌رویم :

40 1 10 20

 در پیمایش دوم، از عدد 40 صرف نظر می‌کنیم و به سراغ اعداد 10, 1, 20 می‌رویم :

A[0], A[1]  =>  1  20  10

A[1], A[2]  =>  10  1  20

حال عدد ماکزیمم مجدد به خانه‌ی 2 آرایه منتقل شد و آرایه به شکل زیر است :

40 20 1 10

در پیمایش سوم، از اعداد 40, 20 را صرف نظر می‌کنیم و به سراغ اعداد 1, 10 می‌رویم :

A[0], A[1]  =>  1  10

حال آرایه ما بطور کامل مرتب شد و به شکل زیر است :

40 20 10 1

همانطور که مشاهده شد، در یک آرایه 4 عضوی، 3=1-4 پیمایش انجام شد تا آرایه به‌طور کامل مرتب شد.

حال الگوریتم این بخش را به این شکل می‌نویسیم :

  1. شروع
  2. i=0، j=0، آرایه را دریافت کن و بریز در A[n]
  3. اگر i <= n-1 بود برو به مرحله 4 و درغیراینصورت برو به 8
  4. اگر j <= n-i-2 بود برو به 5 و در غیراینصورت برو به 7
  5. اگر A[j]>A[j+1] بود، جای A[i] و A[j] را عوض کن.
  6. j = j+1، برو به 4
  7. j = 0، i = i+1، برو به 3
  8. پایان

تحلیل الگوریتم مرتب سازی حبابی

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

  • حلقه اول مربوط به متغیر i است که تا n-1 بار اجرا می‌شود. این همان n-1 پیمایشی است که در توضیح مرتب سازی حبابی به آن اشاره کردیم.
  • حلقه دوم مربوط به متغیر j است که n-i-2 بار اجرا می‌شود و درون حلقه اصلی قرار می‌گیرد. دلیل اینکه از n-i-2 استفاده کردیم، این است که بعد از هربار اجرای این حلقه، یک خانه از آرایه را کم کنیم. این همان مفهومی که در قبل به آن اشاره کردیم و گفتیم که بعد از هرپیمایش، یک خانه از آرایه کم می‌شود.

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

شبه کد مرتب سازی حبابی

توسط شبه کد مرتب سازی حبابی می‌توانیم دید بهتر در یادگیری این الگوریتم داشته باشیم. این شبه کد به زبان خاصی نوشته نشده است و در هر زبان ممکن است دارای سینتکس (Syntax) متفاوتی باشد. شبه کد الگوریتم مرتب سازی حبابی به شکل زیر است :

function bubbleSort (A[n]) {
   for(i = 0; i <= n-1; i++) {
      for(j = 0; j <= (n-i-2); j++) {
         if (A[j] < A[j+1])
            swap(A[i], A[i+1])
      }
   }
}

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

پیچیدگی زمانی مرتب سازی حبابی

درهر الگوریتم، مهم‌ترین پارامتر برای بررسی کارا بودن آن الگوریتم، بررسی پیچیدگی زمانی آن است. حال قصد داریم پیچیدگی زمانی الگوریتم مرتب سازی حبابی را بررسی کنیم. این بررسی دارای 2 قسمت است :

  1. تعداد مقایسات چقدر است؟ همان‌طور که اشاره شد، به ازای یک آرایه n عنصری، n-1 بار عمل بدست آوردن ماکزیمم انجام می‌شود و درهربار یک خانه از آرایه کم می‌شود. پس تعداد مقایسات از فرمول زیر بدست می‌آیند.
  2. تعداد مقایسات = n-1  +  n-2  + … + 1

    در بار اول یافتن ماکزیمم، n-1 بار مقایسه انجام می‌دهیم. در بار دوم، به‌ دلیل کم شدن یک خانه از آرایه، n-2 بار مقایسه انجام می‌دهیم تا جایی که تعداد مقایسات به 1 برسد.

    حال دنباله‌ی فوق که یک تصاعد حسابی است، از رابطه زیر حساب می‌شود :

    \[\frac{n-1\ \ \times \ \ \ (n-1\ \ +\ \ 1)}{2}\ \ =\ \ \frac{n\ (n-1)}{2}\]

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

    $S = n-1  +  n-2  +  {\dots}  +  1$

    $S =   1   +    2    + {\dots}.   +  n-1$

    حال کافی است دو معادله‌ی فوق را باهم جمع کنیم :

    \[2S\ =\ n\ +\ n\ +\ \dots \ +\ n\ \ \ \ \ =>\ \ \ S\ =\ \frac{n\ (n-1)}{2}\]

    تعداد nها در جمله‌ی بالا، n-1 تاست، بنابراین n-1 تا n داریم که می‌شود n(n-1) و برای اینکه S را بدست آوریم، تقسیم بر 2 می‌شود.

    حال اگر مرتبه‌ی زمانی را براساس تعداد مقایسات بررسی کنیم و نام آن‌را T(n) بگذاریم :

    (n2)T(n) = $\frac{n\ (n-1)}{2}$ = ϵ ϴ

  3. تعداد جابه‌جایی‌ها چقدر است؟ اگر عنصری از عنصر مجاورش بزرگ‌تر باشد، مکان آن‌ دوعنصر تعویض می‌شود. حال اگر ما یک آرایه صعودی داشته باشیم، هیچ عمل تعویضی انجام نمی‌شود و بنابراین حداقل تعداد تعویض زمانی است که آرایه صعودی باشد. حداکثر عمل تعویض، زمانی است که آرایه ما نزولی باشد که در نتیجه مرتبه ما همانند قبل از (n2)ϴ خواهد شد.
  4. حداقل تعداد تعویض : 0 حداکثر تعداد تعویض :$\frac{n\ (n-1)}{2}$

    حال که دو پارامتر بالا را بررسی کردیم، پیچیدگی زمانی مرتب سازی ادغامی از چه مرتبه‌ای است؟

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

در ادامه سورس کد مرتب سازی حبابی در ++C، جاوا و ... را بررسی می‌کنیم.

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

تا اینجای کار، مباحث پایه و تحلیلی از مرتب سازی حبابی را بررسی کردیم. حال قصد داریم به‌ صورت عملی و با کد، این مرتب سازی را پیاده کنیم. در ابتدا به مرتب سازی حبابی در جاوا می‌پردازیم. برای اجرای کدهای زیر، می‌توانید از کامپایلرهای آنلاین (با جستجوی java online compiler) و یا IDEهای معروف مانند Intelij استفاده کنید. کد مرتب سازی حبابی در جاوا به شکل زیر است :

public class Main {

    public static void main(String[] args) {

        int[] array = {20, 8, 1, 40, 14, 10, 2, 11};
        bubbleSort(array);
        printArrayParameter(array);
    }

    public static void bubbleSort(int[] array) {
        for (int i = 0; i < array.length; i++) {
            for (int j = 0; j <= (array.length - i - 2); j++) {
                if (array[j] >= array[j + 1]) swapArray(array, j, j + 1);
            }
        }
    }

    public static void swapArray(int[] array, int i1, int i2) {
        array[i1] = array[i1] + array[i2];
        array[i2] = array[i1] - array[i2];
        array[i1] = array[i1] - array[i2];
    }

    public static void printArrayParameter(int[] array) {
        for (int i : array) {
            System.out.print(i + "\t");
        }
    }
  • تابع buubleSort عمل مرتب سازی حبابی را انجام می‌دهد که کد آن بسیار شبیه به شبه کد مرتب سازی حبابی است.
  • تابع swapArray عمل تعویض دو خانه از آرایه را انجام می‌دهد.
  • تابع printArrayParameter درانتها مقادیر آرایه را به ترتیب چاپ می‌کند.
  • تابع main از توابع اصلی جاواست که در ابتدای هرپروژه ساخته می‌شود.

خروجی کد بالا به شکل زیر است :

1 2 8 10 11 14 20 40

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

در این بخش به پیاده‌سازی الگوریتم مرتب سازی حبابی در پایتون می‌پردازیم. برای اجرای کدهای زیر می‌توانید از کامپایلرهای آنلاین مانند repl.it و یا IDEهای معروف مانند PyCharm استفاده کنید. کد مرتب سازی حبابی در پایتون به شکل زیر است :

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


array = [20, 8, 1, 40, 14, 10, 2, 11]
bubbleSort(array)
print(array)
  

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

مرتب سازی حبابی در ++C

در این بخش به پیاده‌سازی الگوریتم مرتب سازی حبابی در ++C می‌پردازیم. برای اجرای کدهای زیر می‌توانید از کامپایلرهای آنلاین و یا IDEهای معروف مانند Visual studio استفاده کنید. کد مرتب سازی حبابی در ++C به شکل زیر است :

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

void bubbleSort(int arr[], int n)
{
	int i, j;
	for (i = 0; i < n - 1; i++)
		for (j = 0; j < n - i - 1; j++)
			if (arr[j] > arr[j + 1])
				swap(arr[j], arr[j + 1]);
}

void printArray(int arr[], int size)
{
	int i;
	for (i = 0; i < size; i++)
		cout << arr[i] << " ";
	cout << endl;
}

int main()
{
	int arr[] = {20, 8, 1, 40, 14, 10, 2, 11};
	int N = sizeof(arr) / sizeof(arr[0]);
	bubbleSort(arr, N);
	cout << "Sorted array: \n";
	printArray(arr, N);
	return 0;
{      

کد مرتب سازی حبابی در ++C نیز بسیار شبیه به جاواست و کد بالا همان الگوریتم مرتب سازی حبابی در ++C است.

مرتب سازی حبابی در #C (سی شارپ) 

در این بخش به پیاده‌سازی الگوریتم مرتب سازی حبابی در #C می‌پردازیم. برای اجرای کدهای زیر می‌توانید از کامپایلرهای آنلاین و یا IDEهای معروف مانند VSCode استفاده کنید. کد مرتب سازی حبابی در سی شارپ به شکل زیر است :

using System;
class Sorting {
	static void bubbleSort(int[] arr)
	{
		int n = arr.Length;
		for (int i = 0; i < n - 1; i++)
			for (int j = 0; j < n - i - 1; j++)
				if (arr[j] > arr[j + 1]) {
					int t = arr[j];
					arr[j] = arr[j + 1];
					arr[j + 1] = t;
				}
	}

	static void printArray(int[] arr)
	{
		int n = arr.Length;
		for (int i = 0; i < n; ++i)
			Console.Write(arr[i] + "\t");
		Console.WriteLine();
	}

	public static void Main()
	{
		int[] arr = {20, 8, 1, 40, 14, 10, 2, 11};
		bubbleSort(arr);
		Console.WriteLine("Sorted array");
		printArray(arr);
	}
}  

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

 

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

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

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

def bubbleSort(array):
    n = len(array)
    for i in range(0, len(array)):
        flag = False
        for j in range(0, n - i - 1):
            if array[j] >= array[j + 1]:
                array[j], array[j + 1] = array[j + 1], array[j]
                flag = True
        if not flag:
            break

array = [10, 9, 8, 7, 1, 2, 3, 4]
bubbleSort(array)
print(array)     

از یک متغیر با نام flag استفاده کردیم که یک متغیر از نوع Boolean است. متغیر از نوع Boolean یک متغیر منطقی است که فقط دوحالت دارد. True یا False (1 یا 0).

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

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

  • بدترین زمان : زمانی که آرایه نزولی باشد و پیچیدگی زمانی مرتب سازی حبابی دقیقا مانند قبل خواهد بود یعنی :
  • T(n) = $\frac{n\ (n-1)}{2}$ =ϵ ϴ(n2)

  • بهترین زمان : بهترین زمان وقتی است که آرایه از همان ابتدا صعودی باشد و در این صورت حلقه ما فقط یک بار اجرا می‌شود که مرتبه‌ی زمانی آن برابر با ϴ(n) خواهد شد.

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

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

یکی دیگر از مزایای آن که بسیاری از الگوریتم‌های مرتب‌سازی آن‌را شامل می‌باشند، مرتبه حافظه O(1) است، زیرا این مرتب‌سازی درجاست و از حافظه‌ی اضافی استفاده نمی‌کند.

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

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

روش مرتب‌سازیبهترین حالتحالت متوسطبدترین حالتتوضیحات
انتخابی (selection sort) O(n2) O(n2) O(n2) غیرمنعادل - درجا
حبابی O(n2) O(n2) O(n2) متعادل - درجا
حبابی بهینه O(n) O(n2) O(n2) متعادل - درجا
ادغامی (Merge sort) O (n log n) O (n log n) O (n log n) متعادل- غیردرجا
درجی O(n) O(n2) O(n2) متعادل - درجا
سریع O (n log n) O (n log n) O(n2) غیرمتعادل - درجا

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

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

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

مثال 1 : بدترین، متوسط و بهترین پیچیدگی زمانی الگوریتم مرتب سازی حبابی به روش عادی کدام است؟

  1. بدترین : O(n2)          متوسط : O(n)          بهترین : O(n)
  2. بدترین : O(n2)          متوسط : O(n logn)          بهترین : O(n)
  3. بدترین : O(n2)          متوسط : O(n)          بهترین : O(n)
  4. بدترین : O(n2)          متوسط : O(n2)          بهترین : O(n2

پاسخ ) براساس موارد گفته شده، گزینه 4، گزینه‌ی صحیح است.

مثال 2 : بدترین، متوسط و بهترین پیچیدگی زمانی الگوریتم مرتب سازی حبابی بهینه کدام است؟

  1. بدترین : O(n2)          متوسط : O(n)          بهترین : O(n)
  2. بدترین : O(n2)          متوسط : O(n logn)          بهترین : O(n)
  3. بدترین : O(n2)          متوسط : O(n2)          بهترین : O(n)
  4. بدترین : O(n2)          متوسط : O(n2)          بهترین : O(n2)

پاسخ) مرتب سازی حبابی بهینه نیز دربهترین حالت دارای مرتبه زمانی n است و بنابراین گزینه 3 صحیح است.

مثال 3 : الگوریتم مرتب سازی حبابی بهینه را برروی آرایه‌ی زیر اعمال می‌کنیم. چند مقایسه نیاز است تا آرایه به‌طور کامل مرتب شود؟

20 5 3 2 4 10
  1. 12
  2. 10
  3. 11
  4. 9

پاسخ)

  • عدد 10، با 5 مقایسه به خانه‌ی 5 آرایه منتقل می‌شود.
  • عدد 4، با 4 مقایسه به خانه‌ی 4 آرایه منتقل می‌شود.
  • عدد 2، 3 مقایسه انجام می‌دهد و چون آرایه به‌طور کامل مرتب شده، پس flag برابر با True نمی‌شود و از حلقه خارج خواهد شد.

بنابراین تعداد مقایسات برابر با 12=3+4+5 خواهد بود و گزینه a، پاسخ صحیح است.

جمع بندی

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

کاربرد مرتب سازی حبابی در کجاست؟

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

مرتبه زمانی و مرتبه حافظه مرتب سازی حبابی چه میزان است؟

همان‌طور که اشاره شد، مرتب سازی حبابی دارای دو حالت بهینه و غیربهینه است، در حالت بهینه مرتبه زمانی آن در بهترین حالت O(n)، در متوسط و بدترین حالت نیز از O(n2) است و در حالت غیربهینه، در تمام حالاتش از ϴ(n2) است. مرتبه حافظه‌ی آن به‌دلیل عدم استفاده از حافظه‌ی اضافی جهت ذخیره آرایه از O(1) است.

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

آی دی تلگرام تیم پشتیبانی:     konkurcomputer_admin@

تماس با پشتیبانی:   09378555200

امتیازدهی5 1 1 1 1 1 1 1 1 1 15.00 امتیاز (3 رای)
بارگذاری نظرات