Якҷоякунӣ дар Java

Ҳар як барномасоз бояд дар аввал нақша/нақша/меъмории кори ояндаро андеша кунад, вагарна ҳамааш дар бесарусомонӣ ва анархияи комил анҷом меёбад. Мисли ҳама гуна паём, ба шумо дар аввал нақша лозим аст, биёед оғоз кунем.

1) Биёед мавзӯи "Merge sort" -ро барои шурӯъкунандагон гирем.
2) Мо меъморӣ ва нақшаи кори минбаъдаро таҳия мекунем.
3) Мо ҳама қисмҳои нақшаро кор карда, тавсиф мекунем.
4) Биёед иҷро ва сифатро тафтиш кунем.

2.1) Ҷудобандии якҷоякунӣ чист.

2.2) Тавсифи имзоҳои эҳтимолӣ.

2.3) Мисол оред.

2.4) Бо истифода аз мисол татбиқи Java-ро тавсиф кунед.

2.5) Ҳама чизи иловагӣ.

Якҷоя кардани навъ Якҷоя-навъ - 1

Якҷоя - якҷоя кардани навъ дар Java

Принсипи «тақсим кун ва забт кун»-ро дар назар дорад. Идея ва маънои он чист?

Мураттабсозӣ.

Мо массивро ба қисмҳо тақсим мекунем, то ба 1 элемент баробар шавад. Ҳар 1 элемент мураттаб карда мешавад.
Муттаҳидшавӣ.

Якҷоя кардани унсурҳои ҷудошуда.
Дар асоси принсипи ду саҳни кортҳои. Мо 2 саҳни кортро дар болои миз бо арзишашон боло мегузорем ва корте, ки аз ҳама пасттар аст, дар паллаи сеюми кортҳо ҷойгир карда мешавад. Дар ниҳоят, агар мо кортҳоро дар саҳни муайян тамом кунем, мо онҳоро як ба як ба саҳни натиҷа интиқол медиҳем. Дар натиҷа як массиви мураттабшуда, як массиви нав ва мураттабшуда якҷоя карда мешавад.

Вақти сарфшуда O(n log2 n) аст. Ҷудокунӣ хеле зуд ҳисобида мешавад. Дар бораи мураккабии алгоритмӣ, агар касе ба он ниёз дошта бошад .

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

Ин тақрибан ҳамон чизест, ки танҳо ба индексҳо алоқаманд аст. Тағйирёбандаҳо дар онҳо инҳоянд:

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

Агар ин тағирёбандаҳо тавсиф нашуда бошанд, пас шахсе, ки худаш чунин функсияро талаб мекунад, намедонад, ки чӣ мехоҳад. Ва шумо бояд Google-ро ҷустуҷӯ кунед, то бидонед, ки ин чист, шумо эҳтимол онро пайдо мекунед, шояд. Ба навъбандии худ мисол меорем. Массив мавҷуд аст , агар дарозии он аз 1 зиёд бошад, пас онро ба 2 қисм тақсим мекунем ва қисми чап ва қисми ростро {6, 1, 3, 5, 2, 4, 7, 8}мегирем . Амали ба 2 кисм таксимкуниро то он даме, ки дарозии он аз 1 зиёд бошад идома медихем. Дар натича як даста массивхои дарозиашон 1 элемент ба даст меорем, яъне: . Татбиқ дар Java чунин аст: {6, 1, 3, 5}{2, 4, 7, 8}{6} {1} {3} {5} {2} {4} {7} {8}

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

Минбаъд шумо бояд ин массивҳоро ба 1 якҷоя кунед. Ин чӣ гуна сурат мегирад? Барои он ки ҳар як массивро чанд маротиба нагузаронем, биёед индексҳои мавқеъро барои ҳар як массив ворид кунем. Он гоҳ мо як давраро як маротиба мегузарем, ки ба дарозии ҷамъи ин ду массив баробар аст. Массиви якум ва массиви дуюмро гиред ва элементи якумро гиред, элементи рақами 1-ро дар массиви якум ва элементи рақами 1-ро дар массиви дуюм муқоиса кунед ? Дар массиви натиҷавӣ хурдтар ҷойгир карда мешавад. Дар ин ҷо муҳим аст, ки агар мо элементеро аз массиви якум гирифта бошем, пас ҳангоми гузаштани давр он бояд ба элементи 2-юми массиви якум ва ба элементи 1-уми массиви дуюм муроҷиат кунад. Барои ин ба шумо лозим аст, ки индекси массиви дуюмро ба +1 зиёд кунед ва ҳангоми тафтиш онро аз рақами давра, ба монанди массиви якум тарҳ кунед. Оё равшан аст, ки чаро ин корро кардан лозим аст? Ё умуман чизе равшан нест? :-) Масалан, 2 массив вуҷуд дорад: {1}{4}{8}ва {3}{6}{7} як давра вуҷуд дорад:

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

Дар гузариши якуми давр маълум мешавад, ки arrayC[1] = {1}: мо ин элементро аз массиви якум гирифтем. Пас, ҳангоми гузаштан аз ҳалқаи дуюм, мо бояд аллакай элемент {4}ва -ро муқоиса кунем {3}, аммо барои ин мо бояд индексҳои мавқеъ ва ҷуброни ҳарду массивро ба назар гирем, барои ин мо онҳоро ворид мекунем.

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

Аммо ин ҳама нест, шумо бояд ба назар гиред, ки баъзе массив пештар ба охир мерасад. Масалан, 3 массив вуҷуд дорад: {1}{3}{5}ва {6}{7}{9} массиви якум то омадани массиви дуюм ба охир мерасад, барои ин шумо бояд чекро ворид кунед ва дар асл, функсияи якҷоякунӣ омода аст.

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;

Чизи душвортарин дар ин навъбандӣ принсипи гузариши рекурсия мебошад. Онхое. мо тарафи чапро ба рекурсия мепартоем, то он даме, ки он ба 2 таќсим шавад ва сипас онро баргардонем, ба ибораи дигар, ин хеле печида ва печида аст, аммо ваќте ки шумо тасаввур карданї мешавед, агар он њанўз маълум набошад, пас ин як бесарусомонии комил аст. Биёед массивро гирем: {2}{1}{4}{3}. Рекурсияи аввалини мураттабсозӣ онро ба 2 қисм тақсим мекунад ва функсияро дубора бо унсурҳои 2-1 иҷро мекунад , баъд аз нав бо унсурҳои 2 ва 1 , онҳоро бо навбат бармегардонад, то онҳо аввал ба функсияи якҷоякунӣ дохил шаванд ва 1-2 меояд. берун , он гоҳ рекурсия бармегардад ва 4-3 ба якҷоякунӣ мепартояд , баъд 4 ва 3 , пас аз он якҷояшавӣ 3-4 бармегардад ва танҳо пас аз он рекурсия боз кушода мешавад ва 1-2 ва 3-4 ба якҷоякунӣ дохил карда мешавад ва массиви мураттабшуда 1-2-3-4 баргардонида мешавад . Хуб, ин ҳама аст, навъбандӣ аз ду функсия иборат аст.

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

Агар шумо як навъи асосӣ нависед, шумо чизе ба монанди:

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] + " ");
        }
    }

Барои ман ин навъбандӣ нокомии комил буд, миллионҳо саволҳо буданд, аммо ҷавоб надоштанд, ман тамоми Интернетро кофтам, дубора хондам, як қатор видеоҳоро тамошо кардам, аммо мисли ҳамеша, ман танҳо худам ҷавобҳоро ёфтам. Ва танҳо вақте ки ман ба навиштани ҳалли комилан фарқ аз он чизе, ки дар ҳама ҷо медурахшад, оғоз кардам) Аммо дар ниҳоят он ба ҳама чизҳои дигар монанд шуд))) Мураттабсозӣ воқеан соддатарин аст, чизи асосӣ ин аст, ки онро интерактивӣ дар амал муаррифӣ кунед ва ҳама чиз ба ҷои худ меафтад, агар шумо онро ба даст оред, ман як видео месозам)))) То ҳол, ин ҳама чизест, ки ман барои он кифоя кардам: Якҷоя кардани навъ Якҷоя-навъсозӣ Муҳимтар аз ҳама ин аст, ки ҳамеша нақша тартиб диҳед ибтидо. Беҳтар аст, ки каме интизор шавед ва пеш аз оғози коре фикр кунед. Ин метавонад вақти бештарро талаб кунад, аммо фаҳмиш ва ҳалли он пайдо мешавад, ба ҷои он ки якчанд маротиба онро дубора навиштан ва асобағол пайдо кардан лозим аст. Ташаккур ба ҳама барои вақтатон, барори кор ва кайфияти хуб. ) PS: Танқид, хубу бад, инчунин саволҳо хеле хушҳоланд. )))

Шарҳҳо

TO VIEW ALL COMMENTS OR TO MAKE A COMMENT,
GO TO FULL VERSION