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

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

معرفی

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

مرتب سازی از طریق چشم ماشین و چشم انسان

بیایید تصور کنیم که باید 5 ستون با ارتفاع های مختلف را به ترتیب صعودی مرتب کنید. این ستون‌ها می‌توانند به معنای هر نوع اطلاعاتی باشند (قیمت سهام، پهنای باند کانال ارتباطی و غیره)؛ شما می‌توانید برخی از نسخه‌های خود را از این کار ارائه دهید تا واضح‌تر شود. خوب، به عنوان مثال، ما Avengers را بر اساس ارتفاع مرتب می کنیم: بر خلاف یک برنامه کامپیوتری، مرتب سازی برای شما دشوار نخواهد بود، زیرا می توانید کل تصویر را ببینید و بلافاصله می توانید بفهمید که کدام قهرمان باید به کجا منتقل شود تا مرتب سازی بر اساس ارتفاع با موفقیت انجام شود. احتمالاً قبلاً حدس زده اید که برای مرتب کردن این ساختار داده به ترتیب صعودی، فقط جای هالک و مرد آهنی را عوض کنید:

انجام شده!

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

• مقایسه دو عنصر؛
• یکی از آنها را تعویض یا کپی کنید.
• رفتن به عنصر بعدی؛

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

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

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

• شما به عنصر صفر آرایه ما (Black Widow) منتقل می شوید.
• عنصر صفر (Black Widow) را با عنصر اول (Hulk) مقایسه کنید.
• اگر عنصر در موقعیت صفر بالاتر باشد، آنها را تعویض می کنید.
• در غیر این صورت، اگر عنصر در موقعیت صفر کوچکتر باشد، آنها را در جای خود رها می کنید.
• به سمت راست حرکت کنید و مقایسه را تکرار کنید (هالک را با کاپیتان مقایسه کنید)

پس از اینکه کل لیست را در یک گذر با چنین الگوریتمی مرور کردید، مرتب سازی به طور کامل تکمیل نخواهد شد. اما از سوی دیگر، بزرگترین عنصر در لیست به سمت راست منتهی می شود. این همیشه اتفاق می افتد، زیرا به محض اینکه بزرگترین عنصر را پیدا کنید، دائماً مکان را تغییر می دهید تا زمانی که آن را به انتها منتقل کنید. یعنی به محض اینکه برنامه هالک را در آرایه "پیدا کرد" او را به انتهای لیست منتقل می کند: به همین دلیل است که این الگوریتم مرتب‌سازی حبابی نامیده می‌شود، زیرا در نتیجه عملکرد آن، بزرگترین عنصر لیست در بالای آرایه قرار می‌گیرد و همه عناصر کوچک‌تر یک موقعیت به سمت چپ منتقل می‌شوند: برای تکمیل مرتب سازی، باید به ابتدای آرایه برگردید و پنج مرحله توضیح داده شده در بالا را دوباره تکرار کنید، دوباره از چپ به راست حرکت کنید، عناصر را مقایسه و در صورت لزوم حرکت دهید. اما این بار باید الگوریتم را یک عنصر قبل از پایان آرایه متوقف کنید، زیرا از قبل می دانیم که بزرگترین عنصر (Hulk) کاملاً در سمت راست ترین موقعیت قرار دارد: بنابراین برنامه باید دو حلقه داشته باشد. برای وضوح بیشتر، قبل از اینکه به بررسی کد برنامه بپردازیم، می توانید تصویری از نحوه کار مرتب سازی حبابی را در این لینک مشاهده کنید: تجسم نحوه کار مرتب سازی حبابی

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

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

• آرایه ای از 5 عنصر ایجاد می کند.
• ظهور انتقام جویان را در آن آپلود می کند.
• محتویات آرایه را نمایش می دهد.
• مرتب سازی حبابی را اجرا می کند.
• آرایه مرتب شده را دوباره نمایش می دهد.

می توانید کد زیر را مشاهده کرده و حتی آن را در IntelliJ IDE مورد علاقه خود دانلود کنید. در زیر تحلیل خواهد شد:

class ArrayBubble{
    private long[] a;   // array reference
    private int elems;  //number of elements in the array

    public ArrayBubble(int max){    //class constructor
        a = new long[max];          //create an array with size max
        elems = 0;                  //when created, the array contains 0 elements
    }

    public void into(long value){   // method for inserting an element into an array
        a[elems] = value;           //insert value into array a
        elems++;                    //array size increases
    }

    public void printer(){          // method for outputting an array to the console
        for (int i = 0; i < elems; i++){    //for each element in the array
            System.out.print(a[i] + " ");   // output to console
            System.out.println("");         //a new line
        }
        System.out.println("----End array output----");
    }

    private void toSwap(int first, int second){ //method swaps a pair of array numbers
        long dummy = a[first];      // put the first element into a temporary variable
        a[first] = a[second];       // put the second element in place of the first
        a[second] = dummy;          //instead of the second element, write the first from temporary memory
    }

    public void bubbleSorter(){     //МЕТОД ПУЗЫРЬКОВОЙ СОРТИРОВКИ
        for (int out = elems - 1; out >= 1; out--){  //Outer loop
            for (int in = 0; in < out; in++){       //Inner loop
                if(a[in] > a[in + 1])               //If the order of the elements is wrong
                    toSwap(in, in + 1);             // call the swapping method
            }
        }
    }
}

public class Main {
    public static void main(String[] args) {
        ArrayBubble array = new ArrayBubble(5); //Create array array with 5 elements

        array.into(163);       //fill the array
        array.into(300);
        array.into(184);
        array.into(191);
        array.into(174);

        array.printer();            //display elements before sorting
        array.bubbleSorter();       //ИСПОЛЬЗУЕМ ПУЗЫРЬКОВУЮ СОРТИРОВКУ
        array.printer();            // print the sorted list again
    }
}

با وجود نظرات دقیق در کد، ما توضیحی در مورد برخی از روش های ارائه شده در برنامه ارائه می دهیم. متدهای کلیدی که کار اصلی را در برنامه انجام می دهند در کلاس ArrayBubble نوشته شده اند. کلاس شامل یک سازنده و چندین متد است:

• into- روش درج عناصر در یک آرایه؛
• printer- محتویات آرایه را خط به خط نمایش می دهد.

• toSwap- در صورت لزوم عناصر را مجدداً مرتب می کند. برای این کار از یک متغیر موقت استفاده می شود dummyکه مقدار عدد اول در آن نوشته می شود و به جای عدد اول مقدار عدد دوم نوشته می شود. سپس محتویات متغیر موقت در عدد دوم نوشته می شود. این یک تکنیک استاندارد برای مبادله دو عنصر است.

  و در نهایت روش اصلی:

• bubbleSorter– که کار اصلی را انجام می دهد و داده های ذخیره شده در آرایه را مرتب می کند، دوباره آن را جداگانه ارائه می دهیم:

  public void bubbleSorter(){     //МЕТОД ПУЗЫРЬКОВОЙ СОРТИРОВКИ
      for (int out = elems - 1; out >= 1; out--){  //Outer loop
          for (int in = 0; in < out; in++){       //Inner loop
              if(a[in] > a[in + 1])               //If the order of the elements is wrong
                  toSwap(in, in + 1);             // call the swapping method
          }
      }
  }

در اینجا باید به دو شمارنده توجه کنید: خارجی outو داخلی in. شمارنده خارجیout از انتهای آرایه شروع به شمارش مقادیر می کند و با هر پاس جدید به تدریج یک عدد کاهش می یابد. outبا هر پاس جدید، متغیر بیشتر به سمت چپ منتقل می شود تا بر مقادیری که قبلاً در سمت راست آرایه مرتب شده اند تأثیر نگذارد. شمارنده داخلیin از ابتدای آرایه شروع به شمارش مقادیر می کند و در هر پاس جدید به تدریج یک عدد افزایش می یابد. افزایش inتا رسیدن به out(آخرین عنصر تحلیل شده در گذر فعلی) رخ می دهد. حلقه داخلی inدو سلول مجاور را با هم مقایسه می کند inو in+1. اگر در inاستورها عددی بزرگتر از in باشد in+1، متدی فراخوانی می شود toSwapکه جای این دو عدد را عوض می کند.

نتیجه

الگوریتم مرتب‌سازی حبابی یکی از کندترین الگوریتم‌ها است. اگر آرایه از N عنصر تشکیل شده باشد، مقایسه N-1 در پاس اول، N-2 در دوم، سپس N-3 و غیره انجام می شود. یعنی تعداد کل پاس‌ها ساخته می‌شود: (N-1) + (N-2) + (N-3) + … + 1 = N x (N-1)/2 بنابراین، هنگام مرتب‌سازی، الگوریتم حدود 0.5x (N ^2) مقایسه را انجام می دهد. برای N = 5، تعداد مقایسه ها تقریبا 10 خواهد بود، برای N = 10 تعداد مقایسه ها به 45 افزایش می یابد. بنابراین، با افزایش تعداد عناصر، پیچیدگی مرتب سازی به طور قابل توجهی افزایش می یابد: سرعت الگوریتم نه تنها تحت تأثیر تعداد پاس‌ها، بلکه تحت تأثیر تعداد جایگشت‌هایی است که باید انجام شوند. برای داده های تصادفی، تعداد جایگشت ها به طور میانگین (N^2) / 4 است که تقریباً نصف تعداد پاس ها است. با این حال، در بدترین حالت، تعداد جایگشت ها نیز می تواند N^2 / 2 باشد - این در صورتی است که داده ها در ابتدا به ترتیب معکوس مرتب شوند. علیرغم این واقعیت که این یک الگوریتم مرتب‌سازی نسبتاً کند است، دانستن و درک نحوه عملکرد آن بسیار مهم است، و همانطور که قبلاً ذکر شد، اساس الگوریتم‌های پیچیده‌تر است. Jgd!