Java-da qabarcıq çeşidləmənin tətbiqi

Kifayət qədər çox sayda çeşidləmə alqoritmi var, onların bir çoxu çox spesifikdir və dar bir sıra problemləri həll etmək və xüsusi məlumat növləri ilə işləmək üçün hazırlanmışdır. Lakin bütün bu müxtəliflik arasında ən sadə alqoritm layiqli şəkildə istənilən proqramlaşdırma dilində həyata keçirilə bilən qabarcıq çeşididir. Sadəliyinə baxmayaraq, çox mürəkkəb alqoritmlərin əsasını təşkil edir. Digər eyni dərəcədə vacib bir üstünlük onun sadəliyidir və buna görə də qarşınızda heç bir əlavə ədəbiyyat olmadan dərhal yadda saxlanıla və həyata keçirilə bilər.

Giriş

Bütün müasir İnternet verilənlər bazalarında toplanmış çoxlu sayda müxtəlif növ məlumat strukturlarından ibarətdir. Onlar istifadəçilərin şəxsi məlumatlarından tutmuş yüksək intellektli avtomatlaşdırılmış sistemlərin semantik nüvəsinə qədər hər cür məlumatı saxlayırlar. Sözsüz ki, məlumatların çeşidlənməsi bu böyük həcmdə strukturlaşdırılmış məlumatda son dərəcə mühüm rol oynayır. Çeşidləmə verilənlər bazasında hər hansı məlumatı axtarmazdan əvvəl məcburi addım ola bilər və çeşidləmə alqoritmləri haqqında bilik proqramlaşdırmada çox mühüm rol oynayır.

Maşın gözləri və insan gözü ilə çeşidləmə

Təsəvvür edək ki, müxtəlif hündürlükdə olan 5 sütunu artan qaydada çeşidləmək lazımdır. Bu sütunlar istənilən növ məlumatı (səhm qiymətləri, rabitə kanalının genişliyi və s.) ifadə edə bilər; siz bunu daha aydın etmək üçün bu tapşırığın bəzi öz versiyalarınızı təqdim edə bilərsiniz. Yaxşı, nümunə olaraq, Avengers-i hündürlüyə görə sıralayacağıq: Kompüter proqramından fərqli olaraq, çeşidləmə sizin üçün çətin olmayacaq, çünki siz bütün mənzərəni görə bilirsiniz və hündürlüyə görə çeşidləmənin uğurla başa çatması üçün hansı qəhrəmanın hara köçürülməsi lazım olduğunu dərhal anlaya bilərsiniz. Yəqin ki, bu məlumat strukturunu artan qaydada çeşidləmək üçün Hulk və Dəmir Adamın yerlərini dəyişmək kifayətdir:

Bitdi!

Və bu çeşidləməni uğurla başa çatdıracaq. Bununla belə, kompüter, sizdən fərqli olaraq, bir qədər axmaqdır və bütün məlumat strukturunu bütövlükdə görmür. Onun nəzarət proqramı bir anda yalnız iki dəyəri müqayisə edə bilər. Bu problemi həll etmək üçün o, yaddaşına iki ədəd yerləşdirməli və onlar üzərində müqayisə əməliyyatı etməli, sonra isə başqa bir cüt rəqəmə keçməli və bütün məlumatlar təhlil olunana qədər davam etməlidir. Beləliklə, hər hansı bir çeşidləmə alqoritmi üç addım şəklində çox sadələşdirilə bilər:

• İki elementi müqayisə edin;
• Onlardan birini dəyişdirin və ya kopyalayın;
• Növbəti elementə keçin;

Fərqli alqoritmlər bu əməliyyatları müxtəlif üsullarla yerinə yetirə bilər, lakin biz qabarcıq çeşidləmənin necə işlədiyini nəzərdən keçirəcəyik.

Bubble Sort Alqoritmi

Bubble çeşidləmə ən sadə hesab olunur, lakin bu alqoritmi təsvir etməzdən əvvəl, bir maşın kimi bir müddət ərzində yalnız iki qəhrəmanı bir-biri ilə müqayisə edə bilsəydiniz, Avengers-i hündürlüyə görə necə sıralayacağınızı təsəvvür edək. Çox güman ki, aşağıdakıları edərdiniz (ən optimal şəkildə):

• Siz bizim massivimizin sıfır elementinə keçirsiniz (Qara Dul);
• Sıfır elementi (Qara Dul) birinci (Hulk) ilə müqayisə edin;
• Sıfır mövqedəki element daha yüksəkdirsə, onları dəyişdirirsiniz;
• Əks halda, sıfır mövqedəki element daha kiçikdirsə, onları öz yerlərində qoyursunuz;
• Sağdakı mövqeyə keçin və müqayisəni təkrarlayın (Hulku Kapitanla müqayisə edin)

Belə bir alqoritmlə bütün siyahını bir keçiddə keçdikdən sonra çeşidləmə tam başa çatmayacaq. Ancaq digər tərəfdən, siyahıdakı ən böyük element ən sağdakı mövqeyə köçürüləcək. Bu, həmişə baş verəcək, çünki ən böyük elementi tapan kimi, onu sonuna qədər köçürənə qədər yerləri daim dəyişəcəksiniz. Yəni, proqram massivdə Hulk "tapdıqda" onu siyahının ən sonuna qədər irəli aparacaq: Buna görə də bu alqoritm qabarcıq çeşidləmə adlanır, çünki onun işləməsi nəticəsində siyahının ən böyük elementi massivin ən yuxarı hissəsində olacaq və bütün kiçik elementlər bir mövqe sola sürüşəcək: Çeşidləməni başa çatdırmaq üçün siz massivin əvvəlinə qayıtmalı və yuxarıda təsvir olunan beş addımı yenidən təkrarlamaq, yenidən soldan sağa keçmək, lazım olduqda elementləri müqayisə etmək və köçürmək lazımdır. Ancaq bu dəfə alqoritmi massivin sonuna bir element qalmış dayandırmalısınız, çünki biz artıq bilirik ki, ən böyük element (Hulk) mütləq ən sağ mövqedədir: Beləliklə, proqramda iki döngə olmalıdır. Daha aydınlıq üçün, proqram kodunu nəzərdən keçirməyə keçməzdən əvvəl, bu linkdə qabarcıq çeşidləmənin necə işlədiyinin vizuallaşdırılmasına baxa bilərsiniz: Bubble çeşidləmənin necə işlədiyinin vizuallaşdırılması

Java-da qabarcıq çeşidləmənin tətbiqi

Java-da çeşidləmənin necə işlədiyini nümayiş etdirmək üçün proqram kodunu təqdim edirik:

• 5 elementdən ibarət massiv yaradır;
• qisasçıların yüksəlişini ona yükləyir;
• massivin məzmununu göstərir;
• bubble sort həyata keçirir;
• çeşidlənmiş massivi yenidən göstərir.

Aşağıdakı koda baxa və hətta onu sevimli IntelliJ IDE -yə endirə bilərsiniz . Aşağıda təhlil ediləcək:

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
    }
}

Koddakı ətraflı şərhlərə baxmayaraq, proqramda təqdim olunan bəzi üsulların təsvirini təqdim edirik. Proqramda əsas işi yerinə yetirən əsas metodlar ArrayBubble sinfində yazılmışdır. Sinifdə konstruktor və bir neçə metod var:

• into– massivə elementlərin daxil edilməsi üsulu;
• printer– massivin məzmununu sətir-sətir göstərir;

• toSwap– zəruri hallarda elementləri yenidən təşkil edir. Bunun üçün müvəqqəti dəyişən istifadə olunur dummyki, ona birinci ədədin qiyməti yazılır, birinci ədədin yerinə isə ikinci nömrənin dəyəri yazılır. Müvəqqəti dəyişənin məzmunu daha sonra ikinci nömrəyə yazılır. Bu, iki elementin dəyişdirilməsi üçün standart bir texnikadır;

  və nəhayət əsas üsul:

• bubbleSorter– əsas işi görən və massivdə saxlanan məlumatları çeşidləyən, biz onu yenidən ayrıca təqdim edəcəyik:

  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
          }
      }
  }

Burada iki sayğaca diqqət yetirməlisiniz: xarici outvə daxili in. Xarici sayğacout massivin sonundan etibarən dəyərləri sadalamağa başlayır və hər yeni keçidlə tədricən bir azalır. outHər yeni keçidlə, massivin sağ tərəfində artıq çeşidlənmiş dəyərlərə təsir etməmək üçün dəyişən daha sola sürüşdürülür. Daxili sayğacin massivin əvvəlindən dəyərləri sadalamağa başlayır və hər yeni keçiddə tədricən bir artır. Artım inçatana qədər baş verir out(cari keçiddə sonuncu təhlil edilən element). Daxili döngə iniki bitişik xananı müqayisə edir invə in+1. in-dən daha böyük rəqəm saxlanılırsa , bu iki ədədin yerini dəyişdirən in+1üsul adlanır .toSwap

Nəticə

Bubble çeşidləmə alqoritmi ən yavaşlardan biridir. Əgər massiv N elementdən ibarətdirsə, onda birinci keçiddə N-1, ikinci keçiddə N-2, sonra N-3 və s. müqayisələr aparılacaq. Yəni, keçidlərin ümumi sayı həyata keçiriləcək: (N-1) + (N-2) + (N-3) + … + 1 = N x (N-1)/2 Beləliklə, çeşidləmə zamanı alqoritm təxminən 0,5x(N ^2) müqayisə aparır. N = 5 üçün müqayisələrin sayı təxminən 10 olacaq, N = 10 üçün müqayisələrin sayı 45-ə qədər artacaq. Beləliklə, elementlərin sayı artdıqca çeşidləmənin mürəkkəbliyi əhəmiyyətli dərəcədə artır: Alqoritmin sürətinə yalnız keçidlərin sayı deyil, həm də edilməli olan permutasiyaların sayı təsir edir. Təsadüfi məlumatlar üçün permütasyonların sayı orta hesabla (N^2) / 4 təşkil edir ki, bu da keçidlərin sayının təxminən yarısı qədərdir. Bununla belə, ən pis halda, dəyişdirmələrin sayı da N ^ 2 / 2 ola bilər - məlumat əvvəlcə tərs qaydada sıralanırsa, bu belədir. Bunun kifayət qədər yavaş çeşidləmə alqoritmi olmasına baxmayaraq, onun necə işlədiyini bilmək və başa düşmək olduqca vacibdir və əvvəllər qeyd edildiyi kimi, daha mürəkkəb alqoritmlər üçün əsasdır. Jgd!