Artikel
Miwiti
Mulai sinau
JavaRush /Blog Jawa /Random-JV /Gabung-urut ing Jawa
vinsler
tingkat

Gabung-urut ing Jawa

Diterbitake ing grup
Saben programer kudu mikir babagan skema / rencana / arsitektur karya ing mangsa ngarep, yen ora, kabeh bakal dadi kacau, kanthi anarki lengkap. Kaya kiriman apa wae, sampeyan butuh rencana, ayo miwiti.
  • 1) Ayo njupuk topik Gabung Urut kanggo pamula.
  • 2) Kita bakal nggawe arsitektur lan rencana kanggo karya luwih.
  • 3) Kita bakal nggarap lan njlèntrèhaké kabèh bagéan saka rencana.
  • 4) Ayo mriksa kinerja lan kualitas.
  • 2.1) Apa Ngurutake Gabung.
  • 2.2) Katrangan saka tandha bisa.
  • 2.3) Wenehana tuladha.
  • 2.4) Njlentrehake implementasine ing basa Jawa nganggo tuladha.
  • 2.5) Apa-apa tambahan.
Gabung Urut Gabung - 1

Gabung - gabung urut ing Jawa

Nindakake prinsip "dibagi lan digdaya". Apa ide lan maknane?

  1. Ngurutake.

    Kita dibagi array dadi bagean nganti padha karo 1 unsur. Saben 1 unsur diurutake.

  2. Panggabungan.

    Nggabungake unsur sing diurutake.
    Adhedhasar prinsip loro geladhak kertu. Kita nyelehake 2 dek kertu ing meja kanthi nilai munggah, lan kertu sing paling murah diselehake ing tumpukan kertu asil katelu. Wekasanipun, yen kita kehabisan kertu ing kelompok tartamtu, kita pindhah siji-siji menyang kelompok asil. Asil bakal dadi gabungan saka rong larik sing diurutake, siji sing anyar, sing diurutake.

Wektu sing ditindakake yaiku O(n log2 n). Ngurutake dianggep cukup cepet. Sedhela babagan kerumitan algoritmik, yen ana sing mbutuhake. Sampeyan kerep bisa ndeleng fungsi kaya: 
Sort(A, p, q);
Merge(A, p, q, r);
Iki bab sing padha, mung disambung menyang indeks. Variabel kasebut yaiku: 
A = Array = Массив
p, q, r = индексы для массива
p - начало первого массива
q - конец первого массива
q + 1 - начало второго массива
r - конец второго массива
Yen variabel kasebut ora diterangake, mula sing njaluk nggawe fungsi kasebut dhewe ora ngerti apa sing dikarepake. Lan sampeyan kudu nggoleki Google kanggo ngerteni apa iku, sampeyan bakal nemokake, bisa uga. Ayo menehi conto ngurutake kita. Ana array {6, 1, 3, 5, 2, 4, 7, 8}, yen dawane luwih saka 1, banjur dibagi dadi 2 bagean lan entuk sisih kiwa {6, 1, 3, 5}lan sisih tengen {2, 4, 7, 8}. Kita nerusake tumindak dibagi dadi 2 bagean nganti dawane luwih saka 1. Akibate, kita entuk akeh array kanthi dawa 1 unsur, yaiku: {6} {1} {3} {5} {2} {4} {7} {8}. Implementasine ing Jawa kaya mangkene:
Java-университет 
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);
    }
Sabanjure sampeyan kudu nggabungake array kasebut dadi 1. Kepiye carane iki rampung? Supaya ora ngliwati saben larik kaping pirang-pirang, ayo ketik indeks posisi kanggo saben larik. Banjur kita bakal ngliwati daur ulang sapisan, padha karo dawa jumlah rong susunan kasebut. Njupuk array pisanan lan array kapindho, lan njupuk unsur pisanan, mbandhingaké nomer unsur 1 ing array pisanan lan nomer unsur 1 ing array kapindho ? Sing luwih cilik diselehake ing array sing diasilake. Penting ing kene yen kita njupuk unsur saka array pisanan, banjur nalika daur ulang liwat, iku kudu ngrujuk menyang unsur 2nd saka array pisanan lan kanggo unsur 1st saka array kapindho. Kanggo nindakake iki, sampeyan kudu nambah indeks array kapindho kanthi +1 lan, nalika mriksa, nyuda saka nomer siklus, uga kanggo array pisanan. Apa jelas kenapa kudu nindakake iki? Utawa ora ana sing jelas? :-) Contone, ana 2 array: {1}{4}{8}lan {3}{6}{7} ana loop: 
for (int i = 0; i < arrayA.length + arrayB.length; i++) {
	if (arrayA[i] < arrayB[i]) {
	arrayC[i] = arrayA[i];
	} else {
	arrayC[i] = arrayB[i];
	}
}
Ing pass pisanan daur ulang, ternyata arrayC[1] = {1}: kita njupuk unsur iki saka array pisanan. Banjur, nalika liwat daur ulang kapindho, kita kudu wis mbandhingaké unsur {4}lan {3}, nanging kanggo nindakake iki, kita kudu njupuk menyang akun indeks posisi lan ngimbangi loro array, kanggo iki kita ketik mau. 
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++;
	}
}
Nanging iku ora kabeh, sampeyan kudu njupuk menyang akun sing sawetara Uploaded bisa mungkasi sadurungé. Contone, ana 3 array: {1}{3}{5}lan {6}{7}{9} Array pisanan bakal rampung sadurunge sing kapindho teka, kanggo iki sampeyan kudu ngetik mriksa lan, ing asas, fungsi gabungan wis siyap. 
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;
Bab sing paling angel babagan ngurutake iki yaiku prinsip transisi rekursi. Sing. kita uncalan sisih kiwa menyang recursion nganti bisa dibagi dening 2, lan banjur unwind maneh, ing tembung iku banget rumit lan bingung, nanging nalika nyoba kanggo mbayangno, yen durung cetha, banjur kekacoan lengkap. Ayo njupuk array: {2}{1}{4}{3}. Rekursi ngurutake pisanan bakal dibagi dadi 2 bagean lan mbukak fungsi maneh karo unsur 2-1 , banjur maneh karo unsur 2 lan 1 , bali menyang siji, supaya padha mlebu menyang fungsi gabungan pisanan, lan 1-2 bakal teka. metu , banjur rekursi bakal bali maneh lan uncalan 4-3 menyang gabungan , banjur 4 lan 3 , sawise kang gabungan bakal bali 3-4 , lan mung banjur recursion bakal unwind maneh lan 1-2 lan 3-4 bakal. kalebu ing gabungan , lan Uploaded diurutake bakal bali 1-2-3-4 . Inggih, iku kabeh, ngurutake kasusun saka rong fungsi. 
sortArray(array); 			// кладем массив который нужно отсортировать
mergeArray(arrayA, arrayB); 	// кладем 2 массива которые нужно слить в один
Yen sampeyan nulis sawetara jinis utama, sampeyan bakal entuk kaya: 
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] + " ");
        }
    }
Kanggo kula, ngurutake iki gagal lengkap, ana sejuta pitakonan, nanging ora ana jawaban, aku ndudhuk kabeh Internet, maca maneh, nonton akeh video, nanging kaya biasane, aku mung nemokake jawaban dhewe. Lan mung nalika aku miwiti nulis solusi sing beda banget karo sing kelip-kelip ing endi wae) Nanging ing pungkasane katon padha karo kabeh liyane))) Ngurutake pancen paling gampang, sing utama yaiku nampilake kanthi interaktif ing tumindak, lan kabeh tumiba ing Panggonan yen njaluk nggantung saka iku, Aku bakal nggawe video)))) Nganti saiki, sing kabeh aku wis cukup kanggo: Gabung Urut Gabung-urut Sing paling penting iku tansah nggawe rencana saka awal. Luwih becik ngenteni sethithik lan mikir sadurunge miwiti nindakake apa wae. Perlu wektu luwih akeh, nanging pemahaman lan solusi bakal muncul tinimbang kudu nulis ulang kaping pirang-pirang lan nggawe crutches. Matur nuwun kabeh kanggo wektu, apik luck lan swasana ati apik. ) PS: Kritik, apik lan ala, uga pitakonan banget ditampa. )))
Komentar
TO VIEW ALL COMMENTS OR TO MAKE A COMMENT,
GO TO FULL VERSION