Java тілінде көпіршікті сұрыптауды енгізу

Сұрыптау алгоритмдерінің өте көп саны бар, олардың көпшілігі өте нақты және есептердің тар шеңберін шешуге және деректердің нақты түрлерімен жұмыс істеуге арналған. Бірақ осы әртүрліліктің ішінде ең қарапайым алгоритм кез келген бағдарламалау тілінде жүзеге асырылуы мүмкін көпіршікті сұрыптау болып табылады. Қарапайымдылығына қарамастан, ол көптеген күрделі алгоритмдердің негізінде жатыр. Тағы бір маңызды артықшылығы - оның қарапайымдылығы, сондықтан оны сіздің алдыңызда қосымша әдебиеттерсіз есте сақтауға және бірден енгізуге болады.

Кіріспе

Бүкіл заманауи Интернет деректер қорларында жиналған деректер құрылымдарының көптеген түрлерінен тұрады. Олар пайдаланушылардың жеке деректерінен бастап жоғары интеллектуалды автоматтандырылған жүйелердің семантикалық өзегіне дейін ақпараттың барлық түрлерін сақтайды. Айта кету керек, деректерді сұрыптау құрылымдық ақпараттың осы үлкен көлемінде өте маңызды рөл атқарады. Мәліметтер қорынан кез келген ақпаратты іздеу алдында сұрыптау міндетті қадам болуы мүмкін, ал сұрыптау алгоритмдерін білу бағдарламалауда өте маңызды рөл атқарады.

Машинаның көзі және адам көзі арқылы сұрыптау

Әртүрлі биіктіктегі 5 бағанды ​​өсу ретімен сұрыптау керек деп елестетіп көрейік. Бұл бағандар ақпараттың кез келген түрін білдіруі мүмкін (акция бағалары, байланыс арнасының өткізу қабілеті және т.б.); оны нақтырақ ету үшін осы тапсырманың кейбір жеке нұсқаларын ұсынуға болады. Мысал ретінде біз Кек алушыларды биіктігі бойынша сұрыптаймыз: Компьютерлік бағдарламадан айырмашылығы, сұрыптау сізге қиын болмайды, өйткені сіз бүкіл суретті көре аласыз және биіктігі бойынша сұрыптау сәтті аяқталуы үшін қай кейіпкерді қайда жылжыту керектігін бірден анықтай аласыз. Сіз бұл деректер құрылымын өсу ретімен сұрыптау үшін Hulk пен Iron Man орындарын ауыстырыңыз деп болжаған шығарсыз:

Дайын!

Және бұл сұрыптауды сәтті аяқтайды. Дегенмен, компьютер, сізден айырмашылығы, біршама ақымақ және бүкіл деректер құрылымын тұтастай көрмейді. Оның басқару бағдарламасы бір уақытта тек екі мәнді салыстыра алады. Бұл мәселені шешу үшін ол өзінің жадында екі санды орналастырып, олармен салыстыру операциясын орындауы керек, содан кейін барлық деректер талданғанша басқа сандар жұбына көшу керек. Сондықтан кез келген сұрыптау алгоритмін үш қадам түрінде өте жеңілдетуге болады:

• Екі элементті салыстыру;
• Олардың біреуін ауыстырыңыз немесе көшіріңіз;
• Келесі элементке өту;

Әртүрлі алгоритмдер бұл әрекеттерді әртүрлі тәсілдермен орындай алады, бірақ біз көпіршікті сұрыптау қалай жұмыс істейтінін қарастыруға көшеміз.

Көпіршікті сұрыптау алгоритмі

Көпіршікті сұрыптау ең қарапайым болып саналады, бірақ бұл алгоритмді сипаттамас бұрын, егер сіз машина сияқты бір уақыт аралығында тек екі кейіпкерді бір-бірімен салыстыра алсаңыз, Кек алушыларды биіктігі бойынша қалай сұрыптайтыныңызды елестетіп көрейік. Сірә, сіз (ең оңтайлы) келесі жолды жасайсыз:

• Сіз массивіміздің нөлдік элементіне ауысасыз (Қара жесір);
• Нөлдік элементті (Қара жесір) біріншімен (Халк) салыстырыңыз;
• Нөлдік позициядағы элемент жоғарырақ болса, оларды ауыстырасыз;
• Әйтпесе, нөл позициясындағы элемент кішірек болса, оларды орындарында қалдырасыз;
• Оң жаққа жылжытыңыз және салыстыруды қайталаңыз (Халкты капитанмен салыстырыңыз)

Бүкіл тізімді осындай алгоритммен бір өтуде өткеннен кейін сұрыптау толығымен аяқталмайды. Бірақ екінші жағынан, тізімдегі ең үлкен элемент ең оң жаққа жылжытылады. Бұл әрқашан болады, өйткені сіз ең үлкен элементті тапқан бойда оны аяғына дейін жылжытқанша орындарды үнемі ауыстырып отырасыз. Яғни, бағдарлама массивтен Халкты «тапқанда» оны тізімнің соңына қарай жылжытады: Сондықтан бұл алгоритм көпіршікті сұрыптау деп аталады, өйткені оның жұмысының нәтижесінде тізімдегі ең үлкен элемент массивтің ең жоғарғы жағында болады, ал барлық кішірек элементтер бір позиция солға жылжиды: Сұрыптауды аяқтау үшін массивтің басына оралып, жоғарыда сипатталған бес қадамды қайтадан қайталаңыз, қайтадан солдан оңға қарай жылжытыңыз, қажетінше элементтерді салыстырыңыз және жылжытыңыз. Бірақ бұл жолы алгоритмді массивтің соңына бір элемент қалғанда тоқтату керек, өйткені біз ең үлкен элементтің (Хулк) ең оң жақта екенін білеміз: Сондықтан бағдарламада екі цикл болуы керек. Көбірек түсінікті болу үшін, бағдарлама codeын қарап шығуды бастамас бұрын, көпіршікті сұрыптау қалай жұмыс істейтінін визуализациялау үшін мына сілтемені пайдалана аласыз: Көпіршікті сұрыптау қалай жұмыс істейтінін визуализациялау

Java тілінде көпіршікті сұрыптауды енгізу

Java тілінде сұрыптау қалай жұмыс істейтінін көрсету үшін мына бағдарлама codeы берілген:

• 5 элементтен тұратын массив жасайды;
• оған кек алушылардың көтерілуін жүктейді;
• массивтің мазмұнын көрсетеді;
• көпіршікті сұрыптауды жүзеге асырады;
• сұрыпталған массивді қайта көрсетеді.

Төмендегі codeты көруге және тіпті оны сүйікті 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+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!