Java тілінде біріктіру-сұрыптау

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

• 1) Жаңадан бастағандар үшін біріктіру сұрыптау тақырыбын алайық.
• 2) Архитектура мен алдағы жұмыстардың жоспарын жасаймыз.
• 3) Біз жоспардың барлық бөліктерімен жұмыс жасаймыз және сипаттаймыз.
• 4) Өнімділік пен сапаны тексерейік.

• 2.1) Біріктіру сұрыптау дегеніміз не.
• 2.2) Ықтимал қолдардың сипаттамасы.
• 2.3) Мысал келтіріңіз.
• 2.4) Java тіліндегі іске асыруды мысал арқылы сипаттаңыз.
• 2.5) Кез келген қосымша.

Біріктіру - Java тілінде сұрыптауды біріктіру

«Бөл және билей бер» қағидасын білдіреді. Идея және оның мәні неде?

1. Сұрыптау.

   Массивті 1 элементке тең болғанша бөліктерге бөлеміз. Әрбір 1 элемент сұрыпталады.

2. Біріктіру.

   Сұрыпталған элементтерді біріктіру.
   Карточкалардың екі палубасы принципіне негізделген. Біз үстелге 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: Сын, жақсы мен жаман, сондай-ақ сұрақтар өте құпталады. )))