Panduan untuk Algoritma Penyortiran Di Tempat Bekerja dengan Implementasi Java

1. Perkenalan

Dalam tutorial ini, kami akan menjelaskan cara kerja algoritma pengurutan di tempat.

2. Algoritma Di Tempat

Algoritme di tempat adalah algoritme yang tidak memerlukan struktur data tambahan apa pun untuk mengubah data masukan. Pada dasarnya, ini berarti algoritme tidak menggunakan ruang ekstra untuk manipulasi input. Ini secara praktis mengganti input dengan output.

Namun, pada kenyataannya, algoritme sebenarnya mungkin memerlukan ruang tambahan kecil dan tidak konstan untuk variabel tambahan. Kompleksitas ruang ini dalam banyak kasus adalah O (log n) , meskipun terkadang sesuatu yang kurang dari linier diperbolehkan.

3. Kode-pseudo

Sekarang mari kita lihat beberapa pseudocode dan bandingkan algoritme di tempat dengan yang di luar tempat.

Kami akan berasumsi bahwa kami ingin membalikkan larik n angka.

3.1. Algoritma Di Tempat

Jika kita memikirkan masalahnya, kita akan melihat bahwa kita memiliki array input dan array terbalik sebagai outputnya. Pada akhirnya, kita sebenarnya tidak membutuhkan larik asli kita, hanya larik terbalik saja.

Lalu, mengapa kita tidak menimpa input daripada memindahkan nilainya ke array yang benar-benar baru, karena mungkin terlihat seperti metode yang paling jelas? Untuk melakukan itu, kita hanya membutuhkan satu variabel tambahan untuk menyimpan sementara nilai yang sedang kita kerjakan:

reversInPlace(array A[n]) for i from 0 to n/2 temp = A[i] A[i] = A[n - 1 - i] A[n - 1 - i] = temp

Patut dicatat bahwa tidak peduli seberapa besar lariknya, ruang ekstra yang kita butuhkan akan selalu O (1) dalam kasus ini.

Ilustrasi menunjukkan bahwa kita membutuhkan lebih sedikit langkah dari pada kasus sebelumnya:

3.2. Algoritma Di Luar Tempat

Di sisi lain, kita juga dapat melakukannya dengan cara yang cukup sederhana dan lebih jelas. Kita dapat membuat array baru dengan ukuran yang sama, menyalin nilai dari yang asli dengan urutan yang sesuai dan kemudian menghapus array asli:

reverseOutOfPlace(array A[n]) create new array B[n] for i from 0 to n - 1 B[i] = A[i] delete A return B

Meskipun ini akan melakukan apa yang kita inginkan, itu tidak cukup efisien. Kami memiliki O (n) ruang ekstra yang diperlukan karena kami memiliki dua array untuk dimanipulasi . Selain itu, membuat dan menghapus array baru biasanya merupakan operasi yang lambat.

Mari kita lihat ilustrasi prosesnya:

4. Implementasi Java

Sekarang mari kita lihat bagaimana kita dapat mengimplementasikan di Java apa yang telah kita pelajari di bagian sebelumnya.

Pertama, kami akan menerapkan algoritme di tempat:

public static int[] reverseInPlace(int A[]) { int n = A.length; for (int i = 0; i < n / 2; i++) { int temp = A[i]; A[i] = A[n - 1 - i]; A[n - 1 - i] = temp; } return A; }

Kami dapat menguji dengan mudah bahwa ini berfungsi seperti yang diharapkan:

@Test public void givenArray_whenInPlaceSort_thenReversed() { int[] input = {1, 2, 3, 4, 5, 6, 7}; int[] expected = {7, 6, 5, 4, 3, 2, 1}; assertArrayEquals("the two arrays are not equal", expected, InOutSort.reverseInPlace(input)); }

Kedua, mari kita lihat implementasi algoritma di luar tempat:

public static int[] reverseOutOfPlace(int A[]) { int n = A.length; int[] B = new int[n]; for (int i = 0; i < n; i++) { B[n - i - 1] = A[i]; } return B; }

Tesnya cukup mudah:

@Test public void givenArray_whenOutOfPlaceSort_thenReversed() { int[] input = {1, 2, 3, 4, 5, 6, 7}; int[] expected = {7, 6, 5, 4, 3, 2, 1}; assertArrayEquals("the two arrays are not equal", expected, InOutSort.reverseOutOfPlace(input)); }

5. Contoh

Ada banyak algoritma pengurutan yang menggunakan pendekatan di tempat. Beberapa di antaranya adalah jenis penyisipan, jenis gelembung, jenis heap, quicksort, dan jenis shell dan Anda dapat mempelajari lebih lanjut tentang mereka dan melihat implementasi Java-nya.

Juga, kita perlu menyebutkan comb sort dan heapsort. Semua ini memiliki kompleksitas ruang O (log n) .

Mungkin berguna juga untuk mempelajari lebih lanjut tentang Teori Notasi Big-O, serta untuk melihat beberapa Contoh Java Praktis tentang kompleksitas algoritme.

6. Kesimpulan

Dalam artikel ini, kami menjelaskan apa yang disebut algoritme di tempat, mengilustrasikan cara kerjanya menggunakan kodesemu dan beberapa contoh, mencantumkan beberapa algoritme yang bekerja berdasarkan prinsip ini, dan akhirnya menerapkan contoh dasar di Java.

Seperti biasa, seluruh kode dapat ditemukan di GitHub.