Gabungkan-sortir di Java

Setiap programmer pada awalnya harus memikirkan skema/rencana/arsitektur pekerjaan di masa depan, jika tidak semuanya akan berakhir berantakan, dengan anarki total. Seperti halnya postingan lainnya, pada awalnya Anda memerlukan rencana, mari kita mulai.

• 1) Mari kita ambil topik Merge sort untuk pemula.
• 2) Kami akan membuat arsitektur dan rencana untuk pekerjaan selanjutnya.
• 3) Kami akan mengerjakan dan menjelaskan seluruh bagian rencana.
• 4) Mari kita periksa kinerja dan kualitasnya.

• 2.1) Apa itu penyortiran gabungan.
• 2.2) Deskripsi kemungkinan tanda tangan.
• 2.3) Berikan sebuah contoh.
• 2.4) Jelaskan implementasi di Java menggunakan sebuah contoh.
• 2.5) Tambahan apa pun.

Gabung - gabungkan pengurutan di Java

Menyiratkan prinsip “memecah belah dan menaklukkan”. Apa ide dan maknanya?

1. Penyortiran.

   Kami membagi array menjadi beberapa bagian hingga sama dengan 1 elemen. Setiap 1 elemen diurutkan.

2. Penggabungan.

   Menggabungkan elemen yang diurutkan.
   Berdasarkan prinsip dua tumpukan kartu. Kami menempatkan 2 tumpukan kartu di atas meja dengan nilainya naik, dan kartu yang terendah ditempatkan di tumpukan kartu ketiga yang dihasilkan. Pada akhirnya, jika kita kehabisan kartu di tumpukan tertentu, kita memindahkannya satu per satu ke tumpukan yang dihasilkan. Hasilnya adalah gabungan dua array yang diurutkan, satu array baru yang diurutkan.

Waktu yang dihabiskan adalah O(n log2 n). Penyortiran dinilai cukup cepat. Secara singkat tentang kompleksitas algoritmik, jika ada yang membutuhkannya, Anda sering dapat melihat fungsi seperti:

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

Ini hampir sama, hanya ditautkan ke indeks. Variabel yang ada di dalamnya adalah:

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

Jika variabel-variabel ini tidak dijelaskan, maka orang yang meminta untuk membuat fungsi tersebut sendiri tidak mengetahui apa yang diinginkannya. Dan Anda harus menjelajahi Google untuk mencari tahu apa itu, Anda mungkin akan menemukannya, mungkin. Mari kita beri contoh penyortiran kita. Ada array {6, 1, 3, 5, 2, 4, 7, 8}, jika panjangnya lebih dari 1, maka kita bagi menjadi 2 bagian dan dapatkan bagian kiri {6, 1, 3, 5}dan kanan {2, 4, 7, 8}. Kita lanjutkan tindakan membagi menjadi 2 bagian hingga panjangnya lebih dari 1. Hasilnya, kita mendapatkan sekumpulan array dengan panjang 1 elemen, yaitu: {6} {1} {3} {5} {2} {4} {7} {8}. Implementasinya di Java kira-kira seperti ini:

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

Selanjutnya Anda perlu menggabungkan array ini menjadi 1. Bagaimana caranya? Untuk menghindari melewati setiap larik berkali-kali, mari masukkan indeks posisi untuk setiap larik. Kemudian kita akan melewati satu loop satu kali, sama dengan panjang jumlah kedua array ini. Ambil array pertama dan array kedua, dan ambil elemen pertama, bandingkan elemen nomor 1 di array pertama dan elemen nomor 1 di array kedua ? Yang lebih kecil ditempatkan di array yang dihasilkan. Penting di sini bahwa jika kita mengambil elemen dari array pertama, maka ketika loop lewat, elemen tersebut harus merujuk ke elemen ke-2 dari array pertama dan ke elemen ke-1 dari array kedua. Untuk melakukan ini, Anda perlu menambah indeks array kedua sebesar +1 dan, saat memeriksa, kurangi dari nomor siklus, demikian pula untuk array pertama. Apakah sudah jelas mengapa melakukan ini? Atau tidak ada yang jelas sama sekali? :-) Misalnya ada 2 array: {1}{4}{8}dan {3}{6}{7} Dan ada 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];
	}
}

Pada loop pertama, ternyata arrayC[1] = {1}: kita mengambil elemen ini dari array pertama. Kemudian, ketika melewati loop kedua, kita harus sudah membandingkan elemen {4}dan {3}, tetapi untuk melakukan ini kita perlu memperhitungkan indeks posisi dan offset kedua array, untuk ini kita memasukkannya.

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

Tapi bukan itu saja, Anda perlu memperhitungkan bahwa beberapa array mungkin berakhir lebih awal. Misalnya, ada 3 array: {1}{3}{5}dan {6}{7}{9} Array pertama akan berakhir sebelum array kedua tiba, untuk ini Anda perlu memasukkan tanda centang dan, pada prinsipnya, fungsi penggabungan sudah siap.

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;

Hal tersulit dalam penyortiran ini adalah prinsip transisi rekursi. Itu. ruas kirinya kita masukkan ke dalam rekursi sampai habis dibagi 2, lalu diunwind kembali, dengan kata lain sangat rumit dan membingungkan, tapi kalau coba bayangkan, kalau belum jelas, maka berantakan total. Mari kita ambil arraynya: {2}{1}{4}{3}. Rekursi pengurutan pertama akan membaginya menjadi 2 bagian dan menjalankan fungsi lagi dengan elemen 2-1 , kemudian lagi dengan elemen 2 dan 1 , mengembalikannya secara bergantian, sehingga mereka akan masuk ke fungsi penggabungan terlebih dahulu, dan 1-2 akan datang keluar , maka rekursi akan kembali dan melemparkan 4-3 ke dalam penggabungan , lalu 4 dan 3 , setelah itu penggabungan akan kembali 3-4 , dan baru kemudian rekursi akan berputar kembali dan 1-2 dan 3-4 akan disertakan dalam penggabungan , dan array yang diurutkan akan dikembalikan 1-2-3-4 . Nah itu saja, pengurutan terdiri dari dua fungsi.

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

Jika Anda menuliskan beberapa hal utama, Anda akan mendapatkan sesuatu seperti:

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

Bagi saya, penyortiran ini gagal total, ada sejuta pertanyaan, tetapi tidak ada jawaban, saya menggali seluruh Internet, membaca ulang, menonton banyak video, tetapi seperti biasa, saya hanya menemukan jawabannya sendiri. Dan hanya ketika saya mulai menulis solusi yang sama sekali berbeda dari yang muncul di mana-mana) Tapi pada akhirnya ternyata mirip dengan yang lain))) Penyortiran sebenarnya yang paling sederhana, yang utama adalah menyajikannya secara interaktif dalam tindakan, dan semuanya beres jika Anda sudah menguasainya, saya akan membuat video)))) Sejauh ini, hanya itu yang sudah cukup untuk saya: Merge sort Merge-sort Yang paling penting adalah selalu membuat rencana dari awal mula. Lebih baik menunggu sebentar dan berpikir sebelum mulai melakukan apa pun. Ini mungkin memakan waktu lebih lama, tetapi pemahaman dan solusi akan muncul daripada harus menulis ulang beberapa kali dan muncul dengan tongkat penopang. Terima kasih atas waktunya, semoga sukses dan suasana hati yang baik. ) PS: Kritik, baik dan buruk, serta pertanyaan sangat kami harapkan. )))