Java-da pufakchali tartiblashni amalga oshirish

Saralash algoritmlarining juda ko'p soni mavjud, ularning aksariyati juda aniq va tor doiradagi muammolarni hal qilish va ma'lum turdagi ma'lumotlar bilan ishlash uchun ishlab chiqilgan. Ammo bu xilma-xillik orasida eng oddiy algoritm har qanday dasturlash tilida amalga oshirilishi mumkin bo'lgan pufakchali tartibdir. Oddiyligiga qaramay, u juda ko'p murakkab algoritmlarga asoslanadi. Yana bir muhim afzallik - bu uning soddaligi va shuning uchun uni sizning oldingizda qo'shimcha adabiyotlarsiz darhol eslab qolish va amalga oshirish mumkin.

Kirish

Butun zamonaviy Internet ma'lumotlar bazalarida to'plangan juda ko'p turli xil ma'lumotlar tuzilmalaridan iborat. Ular foydalanuvchilarning shaxsiy ma'lumotlaridan tortib yuqori intellektual avtomatlashtirilgan tizimlarning semantik yadrosigacha bo'lgan barcha turdagi ma'lumotlarni saqlaydi. Aytish kerakki, ma'lumotlarni saralash ushbu katta hajmdagi tuzilgan ma'lumotlarda juda muhim rol o'ynaydi. Saralash ma'lumotlar bazasida har qanday ma'lumotni qidirishdan oldin majburiy qadam bo'lishi mumkin va tartiblash algoritmlarini bilish dasturlashda juda muhim rol o'ynaydi.

Mashina ko'zlari va inson ko'zlari orqali saralash

Tasavvur qilaylik, siz har xil balandlikdagi 5 ta ustunni o'sish tartibida saralashingiz kerak. Ushbu ustunlar har qanday ma'lumotni anglatishi mumkin (aksiya narxlari, aloqa kanalining o'tkazish qobiliyati va boshqalar); buni yanada aniqroq qilish uchun siz ushbu vazifaning ba'zi versiyalarini taqdim etishingiz mumkin. Masalan, biz Qasoskorlarni balandligi bo'yicha saralaymiz: Kompyuter dasturidan farqli o'laroq, saralash siz uchun qiyin bo'lmaydi, chunki siz butun rasmni ko'ra olasiz va balandlik bo'yicha saralash muvaffaqiyatli yakunlanishi uchun qaysi qahramonni qayerga ko'chirish kerakligini darhol aniqlay olasiz. Ehtimol, siz ushbu ma'lumotlar tuzilmasini o'sish tartibida saralash uchun Hulk va Iron Man joylarini almashtirishni taxmin qilgan bo'lsangiz kerak:

Bajarildi!

Va bu saralashni muvaffaqiyatli yakunlaydi. Biroq, kompyuter, sizdan farqli o'laroq, biroz ahmoq va butun ma'lumotlar strukturasini bir butun sifatida ko'rmaydi. Uning boshqaruv dasturi bir vaqtning o'zida faqat ikkita qiymatni solishtirishi mumkin. Bu muammoni hal qilish uchun u o'z xotirasiga ikkita raqamni qo'yishi va ular ustida taqqoslash operatsiyasini bajarishi kerak, so'ngra boshqa raqamlar juftligiga o'tishi va barcha ma'lumotlar tahlil qilinmaguncha davom etishi kerak. Shunday qilib, har qanday tartiblash algoritmi uch bosqichda juda soddalashtirilishi mumkin:

• Ikki elementni solishtiring;
• Ulardan birini almashtirish yoki nusxalash;
• Keyingi elementga o'ting;

Turli xil algoritmlar bu operatsiyalarni turli yo'llar bilan bajarishi mumkin, ammo biz pufakchani tartiblash qanday ishlashini ko'rib chiqishga o'tamiz.

Pufakchani saralash algoritmi

Pufakchani saralash eng oddiy deb hisoblanadi, ammo bu algoritmni tavsiflashdan oldin, keling, agar siz mashina kabi bir vaqtning o'zida faqat ikkita qahramonni bir-biri bilan solishtirsangiz, Qasoskorlarni balandligi bo'yicha qanday saralaganingizni tasavvur qilaylik. Katta ehtimol bilan siz quyidagilarni bajarasiz (eng maqbul):

• Siz massivimizning nol elementiga o'tasiz (Black Widow);
• Nol elementni (Qora beva) birinchi (Hulk) bilan solishtiring;
• Agar nol pozitsiyasidagi element yuqoriroq bo'lsa, siz ularni almashtirasiz;
• Aks holda, agar nol pozitsiyasidagi element kichikroq bo'lsa, siz ularni o'z joylarida qoldirasiz;
• O'ng tomonga o'ting va taqqoslashni takrorlang (Xalkni kapitan bilan solishtiring)

Bunday algoritm bilan butun ro'yxatni bitta o'tishda ko'rib chiqqaningizdan so'ng, saralash to'liq bajarilmaydi. Ammo boshqa tomondan, ro'yxatdagi eng katta element eng o'ng tomonga o'tkaziladi. Bu har doim sodir bo'ladi, chunki siz eng katta elementni topishingiz bilan siz uni oxirigacha ko'chirmaguningizcha doimiy ravishda joylarni o'zgartirasiz. Ya'ni, dastur massivda Hulkni "topishi" bilanoq, uni ro'yxatning eng oxiriga olib boradi: Shuning uchun bu algoritm pufakchali tartiblash deb ataladi, chunki uning ishlashi natijasida ro'yxatdagi eng katta element massivning eng yuqori qismida bo'ladi va barcha kichikroq elementlar bir pozitsiya chapga siljiydi: Saralashni yakunlash uchun siz massivning boshiga qaytishingiz va yuqorida tavsiflangan besh bosqichni yana takrorlashingiz kerak, yana chapdan o'ngga siljiting, kerak bo'lganda elementlarni solishtiring va siljiting. Ammo bu safar siz algoritmni massiv oxirigacha bir elementdan oldin to'xtatishingiz kerak, chunki biz allaqachon bilamizki, eng katta element (Hulk) mutlaqo eng o'ng holatda: Shunday qilib, dasturda ikkita tsikl bo'lishi kerak. Aniqroq boʻlishi uchun dastur kodini koʻrib chiqishga oʻtishdan oldin, qabariqni saralash qanday ishlashini koʻrish uchun ushbu havoladan foydalanishingiz mumkin .

Java-da pufakchali tartiblashni amalga oshirish

Java-da tartiblash qanday ishlashini ko'rsatish uchun bu erda dastur kodi:

• 5 ta elementdan iborat massiv hosil qiladi;
• qasoskorlarning yuksalishini unga yuklaydi;
• massiv tarkibini ko'rsatadi;
• pufakchani saralashni amalga oshiradi;
• tartiblangan massivni qayta ko'rsatadi.

Siz quyidagi kodni ko'rishingiz va hatto uni sevimli IntelliJ IDE-ga yuklab olishingiz mumkin. U quyida tahlil qilinadi:

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

Koddagi batafsil izohlarga qaramay, biz dasturda taqdim etilgan ba'zi usullarning tavsifini beramiz. Dasturdagi asosiy ishlarni bajaruvchi asosiy usullar ArrayBubble sinfida yozilgan. Sinfda konstruktor va bir nechta usullar mavjud:

• into– massivga elementlarni kiritish usuli;
• printer– massiv tarkibini satr bo‘yicha ko‘rsatadi;

• toSwap- agar kerak bo'lsa, elementlarni qayta tartibga soladi. Buning uchun vaqtinchalik o'zgaruvchidan foydalaniladi dummy, unga birinchi raqamning qiymati yoziladi va birinchi raqam o'rniga ikkinchi raqamning qiymati yoziladi. Vaqtinchalik o'zgaruvchining mazmuni keyin ikkinchi raqamga yoziladi. Bu ikkita elementni almashtirish uchun standart texnikadir;

  va nihoyat asosiy usul:

• bubbleSorter- asosiy ishni bajaradigan va massivda saqlangan ma'lumotlarni saralaydi, biz uni yana alohida taqdim etamiz:

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

Bu erda siz ikkita hisoblagichga e'tibor berishingiz kerak: tashqi outva ichki in. Tashqi hisoblagichout massiv oxiridan boshlab qiymatlarni sanashni boshlaydi va har bir yangi o'tishda asta-sekin bittaga kamayadi. outHar bir yangi o'tishda, massivning o'ng tomonida tartiblangan qiymatlarga ta'sir qilmaslik uchun o'zgaruvchi chapga siljiydi. Ichki hisoblagichin massivning boshidan boshlab qiymatlarni sanashni boshlaydi va har bir yangi o'tishda asta-sekin bittaga ortadi. O'sish inu yetguncha sodir bo'ladi out(joriy o'tishdagi oxirgi tahlil qilingan element). Ichki pastadir ikkita qo'shni hujayra va ni insolishtiradi . Agar dan kattaroq raqam saqlangan bo'lsa , u holda bu ikki raqamning joylarini almashtiradigan usul chaqiriladi .inin+1inin+1toSwap

Xulosa

Pufakchani tartiblash algoritmi eng sekin algoritmlardan biridir. Agar massiv N elementdan iborat bo'lsa, u holda birinchi o'tishda N-1, ikkinchisida N-2, keyin N-3 va boshqalar bilan taqqoslash amalga oshiriladi. Ya'ni, o'tishlarning umumiy soni amalga oshiriladi: (N-1) + (N-2) + (N-3) + … + 1 = N x (N-1)/2 Shunday qilib, tartiblashda algoritm. taxminan 0,5x(N ^2) solishtirishni amalga oshiradi. N = 5 uchun taqqoslashlar soni taxminan 10 ga teng bo'ladi, N = 10 uchun taqqoslashlar soni 45 ga ko'tariladi. Shunday qilib, elementlar soni ortishi bilan saralashning murakkabligi sezilarli darajada oshadi: Algoritm tezligiga nafaqat o'tishlar soni, balki amalga oshirilishi kerak bo'lgan almashtirishlar soni ham ta'sir qiladi. Tasodifiy ma'lumotlar uchun almashtirishlar soni o'rtacha (N ^ 2) / 4 ni tashkil qiladi, bu o'tishlar sonining yarmiga teng. Biroq, eng yomon holatda, almashtirishlar soni ham N ^ 2 / 2 bo'lishi mumkin - bu ma'lumotlar dastlab teskari tartibda tartiblangan bo'lsa. Bu juda sekin tartiblash algoritmi bo'lishiga qaramay, uning qanday ishlashini bilish va tushunish juda muhim va yuqorida aytib o'tilganidek, u yanada murakkab algoritmlar uchun asosdir. Jgd!