Java-da birleşdir

Her bir programmist ilki bilen geljekki işleriň shemasy / meýilnamasy / arhitekturasy barada pikirlenmeli, ýogsam hemmesi bulaşyklyga, doly anarhiýa bilen gutarýar. Islendik ýazgyda bolşy ýaly, başda meýilnama gerek, başlalyň.

• 1) Geliň, täze başlanlar üçin “Merge sort” mowzugyny alalyň.
• 2) Arhitektura we mundan beýläkki işler üçin meýilnama dörederis.
• 3) Meýilnamanyň ähli bölümlerini öwreneris we suratlandyrarys.
• 4) Geliň öndürijiligini we hilini barlalyň.

• 2.1) Birleşmek tertibi näme.
• 2.2) Mümkin bolan gollaryň beýany.
• 2.3) Mysal beriň.
• 2.4) Mysal ulanyp, Java-da ýerine ýetirilişini aýdyp beriň.
• 2.5) Goşmaça zat.

Birleşmek - Java-da görnüşi birleşdirmek

“Bölmek we basyp almak” ýörelgesini göz öňünde tutýar. Pikir we manysy näme?

1. Sortirlemek.

   Toplumy 1 elemente deň bolýança böleklere bölýäris. Her 1 element tertiplenýär.

2. Birleşmek.

   Saýlanan elementleri birleşdirmek.
   Iki gat kartoçka ýörelgesine esaslanýar. Stoluň üstünde 2 sany kartoçka goýýarys, iň pes kartoçka bolsa kartoçkalaryň üçünji üýşmesine ýerleşdirilýär. Netijede, belli bir otagda kartoçkalarymyz gutarsa, olary birin-birin emele gelen paluba geçirýäris. Netijede iki sany tertipli massiw, biri täze, tertipli massiw birleşdiriler.

Geçirilen wagt O (n log2 n). Sortirlemek gaty çalt hasaplanýar. Algoritmiki çylşyrymlylyk barada gysgaça, kimdir biri zerur bolsa, köplenç aşakdaky ýaly funksiýalary görüp bilersiňiz.

Sort(A, p, q);
Merge(A, p, q, r);

Bu diňe bir indeksler bilen baglanyşykly bir zat hakda. Ondaky üýtgeýjiler:

A = Array = Массив
p, q, r = индексы для массива
p - начало первого массива
q - конец первого массива
q + 1 - начало второго массива
r - конец второго массива

Bu üýtgeýjiler düşündirilmese, şeýle funksiýa etmegi haýyş edeniň özi näme isleýändigini bilenok. Munuň nämedigini bilmek üçin Google-ny gözlemeli bolarsyňyz, belki taparsyňyz. Geliň, sortlamagymyza mysal getireliň. Bir massiw bar {6, 1, 3, 5, 2, 4, 7, 8}, uzynlygy 1-den uly bolsa, ony 2 bölege bölýäris we çep bölegini {6, 1, 3, 5}we sag bölegini alýarys {2, 4, 7, 8}. Uzynlygy 1-den uly bolýança 2 bölege bölmek hereketini dowam etdirýäris. Netijede, 1 elementiň uzynlygy bolan bir topar massiw alarys {6} {1} {3} {5} {2} {4} {7} {8}: Java-da durmuşa geçirmek şuňa meňzeş bir zat:

public int [] sortArray(int[] arrayA){ // sorting Массива который передается в функцию
        // проверяем не нулевой ли он?
        if (arrayA == null) {
            return null;
        }
        // проверяем не 1 ли элемент в массиве?
        if (arrayA.length < 2) {
            return arrayA; // возврат в рекурсию в строки ниже см комменты.
        }
        // копируем левую часть от начала до середины
        int [] arrayB = new int[arrayA.length / 2];
        System.arraycopy(arrayA, 0, arrayB, 0, arrayA.length / 2);

        // копируем правую часть от середины до конца массива, вычитаем из длины первую часть
        int [] arrayC = new int[arrayA.length - arrayA.length / 2];
        System.arraycopy(arrayA, arrayA.length / 2, arrayC, 0, arrayA.length - arrayA.length / 2);

        // рекурсией закидываем поделенные обе части обратно в наш метод, он будет крутится до тех пор,
        // пока не дойдет до 1 element в массиве, после чего вернется в строку и будет искать второй такой же,
        // точнее правую часть от него и опять вернет его назад
        arrayB = sortArray(arrayB); // левая часть возврат из рекурсии строкой return arrayA;
        arrayC = sortArray(arrayC); // правая часть возврат из рекурсии строкой return arrayA;

        // далее опять рекурсия возврата слияния двух отсортированных массивов
        return mergeArray(arrayB, arrayC);
    }

Ondan soň bu massiwleri 1. birleşdirmeli. Bu nähili edilýär? Her massiwden birnäçe gezek geçmezlik üçin, her massiw üçin pozisiýa görkezijilerini girizeliň. Soňra bu iki massiwiň jeminiň uzynlygyna deň bolan bir gezek aýlawdan geçeris. Birinji massiw we ikinji massiw alyň we birinji elementi alyň, birinji massiwdäki 1-nji elementi we ikinji massiwdäki 1-nji elementi deňeşdiriň ? Has kiçi görnüşi bolsa, massiwde ýerleşdirilýär. Bu ýerde möhümdir, eger birinji massiwden bir element alsak, aýlaw geçende, birinji massiwiň 2-nji elementine we ikinji massiwiň 1-nji elementine salgylanmalydyr. Munuň üçin ikinji massiwiň indeksini +1 köpeltmeli we barlanyňyzda ony birinji massiw üçin edil aýlaw belgisinden aýyrmaly. Muny näme üçin etmelidigi düşnüklimi? Ora-da asla düşnükli zat ýokmy? :-) Mysal üçin, 2 massiw bar: {1}{4}{8}we {3}{6}{7} aýlaw bar:

for (int i = 0; i < arrayA.length + arrayB.length; i++) {
	if (arrayA[i] < arrayB[i]) {
	arrayC[i] = arrayA[i];
	} else {
	arrayC[i] = arrayB[i];
	}
}

Aýlawyň birinji geçelgesinde şeýle bolýar arrayC[1] = {1}: bu elementi birinji massiwden aldyk. Soňra, ikinji aýlawdan geçenimizde, eýýäm elementi deňeşdirmeli {4}we {3}muny amala aşyrmak üçin ýagdaý görkezijilerini we iki massiwiň ofsetini göz öňünde tutmalydyrys, munuň üçin olara girýäris.

int positionA = 0, positionB = 0;
for (int i = 0; i < arrayA.length + arrayB.length; i++) {
	if (arrayA[i - positionA] < arrayB[i - positionB]) {
	arrayC[i] = arrayA[i - positionA];
	positionB++;
	} else {
	arrayC[i] = arrayB[i - positionB];
	positionA++;
	}
}

Thatöne bularyň hemmesi däl, käbir massiwleriň has ir gutaryp biljekdigini göz öňünde tutmaly. Mysal üçin, 3 massiw bar: {1}{3}{5}we {6}{7}{9} birinji massiw ikinjisi gelmänkä gutarar, munuň üçin çek girizmeli we prinsipde birleşdirmek funksiýasy taýýar.

public int [] mergeArray(int [] arrayА, int [] arrayB) {

int [] arrayC = int[arrayA.length + arrayB.length];
int positionA = 0, positionB = 0;

for (int i = 0; i < arrayC.length; i++) {
	if (positionA == arrayA.length){
	arrayC[i] = arrayB[i - positionB];
	positionB++;
	} else if (positionB == arrayB.length) {
	arrayC[i] = arrayA[i - positionA];
	positionA++;
	} else if (arrayA[i - positionA] < arrayB[i - positionB]) {
	arrayC[i] = arrayA[i - positionA];
	positionB++;
	} else {
	arrayC[i] = arrayB[i - positionB];
	positionA++;
	}
}
return arrayC;

Bu sortlaşdyrmagyň iň kyn zady, gaýtalanma ýörelgesidir. Bular. çep tarapy 2-ä bölünýänçä gaýtalaýarys, soň bolsa ony açarys, söz bilen aýdylanda gaty çylşyrymly we bulaşyk, ýöne göz öňüne getirjek bolanyňyzda, entek düşnüksiz bolsa, bu doly bulaşyklyk. Geliň, massiw alalyň : {2}{1}{4}{3}. Ilkinji tertipleşdiriş gaýtalanmagy ony 2 bölege bölüp, funksiýany ýene 2-1 elementleri bilen işleder , soň bolsa 2 we 1 elementleri bilen işleder, öz gezeginde yzyna gaýtaryp berer, şonuň üçin ilki birleşmek funksiýasyna girer we 1-2 geler çyksa , gaýtalanma gaýdyp geler we birleşmä 4-3 zyňar , soň 4 we 3 , şondan soň birleşme 3-4 gaýdyp geler we diňe şondan soň gaýtalanma ýene aýlanar we 1-2 we 3-4 birleşmäge goşular we tertiplenen massiw 1-2-3-4 yzyna gaýtarylar . Dogrusy, tertiplemek iki funksiýadan ybarat.

sortArray(array); 			// кладем массив который нужно отсортировать
mergeArray(arrayA, arrayB); 	// кладем 2 массива которые нужно слить в один

Haýsydyr bir esasy ýazsaňyz, şuňa meňzeş bir zat alarsyňyz:

public static void main(String[] args) {
        Merge testMerge = new Merge();
        int [] result = testMerge.sortArray(new int[]{2,3,1,4});

        for (int i = 0; i < result.length ; i++) {
            System.out.print(result[i] + " ");
        }
    }

Meniň üçin bu tertipleşdirmek düýbünden şowsuz boldy, million sorag bardy, ýöne jogap ýok, tutuş interneti gazdym, täzeden okadym, bir topar wideo gördüm, ýöne hemişe bolşy ýaly, jogaplary diňe özüm tapdym. Diňe hemme ýerde ýalpyldawuk çözgütden düýpgöter üýtgeşik bir çözgüt ýazyp başlanymda) theöne ahyrynda beýlekiler ýaly boldy))) Sortirlemek aslynda iň ýönekeý, esasy zat ony interaktiw ýagdaýda görkezmek we hemme zat ýerbe-ýer bolýar, eger wideo düşürilse, wideo taýýarlaryn)))) Şu wagta çenli meniň üçin ýeterlik zat: Merge sort Merge-sort Birleşdirmek Iň möhüm zat hemişe meýilnama düzmekdir başlangyç. Birazajyk garaşyp, hiç zat etmezden ozal pikirlenmek has gowudyr. Has köp wagt gerek bolup biler, ýöne düşünmek we çözgüt bir-iki gezek täzeden ýazmaly däl-de, taýak tapmaly däl. Wagtyňyz, üstünlik we keýpiňiz üçin hemmäňize sag bolsun aýdýaryn. ) PS: Tankyt, gowy we erbet, şeýle hem soraglar gaty gowy garşylanýar. ))))