Sortir Penyisipan di Jawa

Menyortir array adalah salah satu operasi paling umum yang harus diketahui oleh seorang pemula Java. Meskipun array tidak selalu merupakan cara yang paling nyaman untuk mengatur data dan ini berlaku sebagian besar untuk bilangan kecil, konsep di balik penyortiran array memiliki banyak aplikasi dalam perangkat lunak dan ilmu data yang kompleks. Dalam posting ini, kita akan melihat lebih dekat apa itu insertion sort. Kami menyertakan beberapa contoh dan soal latihan untuk membantu Anda memahami konsep ini sepenuhnya.

Apa Itu Jenis Penyisipan?

Pada dasarnya, insertion sort adalah pengembang algoritma yang digunakan untuk mengatur string angka kecil. Ini membagi semua nilai menjadi dua tumpukan - yang diurutkan dan yang tidak disortir. Satu per satu, angka-angka dalam tumpukan “tidak disortir” dipilih dan disusun dalam urutan yang benar. Sortir Penyisipan di Jawa - 1

Mari kita lihat lebih dekat input dan output dari insertion sort:

Input: array A dengan elemen numerik yang tidak disortir: A[0,1, n, n-2...].
Keluaran: larik yang berisi angka yang sama tetapi diurutkan sepenuhnya. Yang ini biasanya disebut sebagai B: B[0]B[1]...B[n-1].

Ada beberapa cara untuk menggunakan pengurutan penyisipan - inilah yang paling populer:

Penyortiran numerik (urutan meningkat): [1, 2, 3, 4, 5]
Penyortiran numerik (urutan menurun): [5, 4, 3, 2, 1]
Penyortiran berdasarkan abjad: [a, b, c, d]

Catatan: jika Anda memiliki array kosong atau singleton, ini dianggap diurutkan secara default.

Memahami Teori Insertion Sort

Sebelum mempelajari kode di balik insertion sort, mari kita pecahkan algoritme menggunakan bahasa non-teknis. Karena kami akan menunjukkan kode untuk menyortir dalam urutan menaik, masuk akal untuk menjelaskan algoritme langkah demi langkah di pos ini. Langkah 1. Iterasi antara arr[1]dan arr[n]di mana nnilai numerik biasanya kurang dari 10. Langkah 2. Bandingkan elemen yang Anda pilih (dikenal sebagai key) dengan angka sebelumnya dalam urutan menggunakan sort()metode. Langkah 3. Jika semua elemen lebih kecil dari penerusnya, ulangi perbandingan hingga Anda menemukan nilai yang lebih besar. Langkah 4. Tukar nilai yang lebih besar satu posisi di luar yang lebih kecil untuk membuat urutan yang teratur. Langkah 5. Ulangi proses ini sampai Anda mendapatkan rangkaian karakter yang diurutkan

Menyortir array primitif

Karena algoritme adalah salah satu operasi Java yang paling mudah, bahkan pemula yang lengkap pun tidak akan kesulitan mengimplementasikannya. Berikut panduan langkah demi langkah untuk mengurutkan array

1. Deklarasikan array untuk penyortiran

Untuk memulainya, mari buat string nilai yang nantinya akan kita tampilkan menggunakan Java. Untuk menggunakan insertion sort, Anda perlu membuat sebuah array. Untuk itu, gunakanint[]


int[] arrayA = {10, 14, 20, 30};

2. Gunakan sort_arr untuk mengimplementasikan algoritme

Metode sort_arr adalah salah satu cara paling umum untuk mengimplementasikan insertion sort. Dalam praktiknya, ini terlihat seperti ini:


for(int i=0; i< sort_arr.length; ++i){
        int j = i;

3. Buat loop dan iterator

Dengan menggunakan loop dalam algoritma pengurutan penyisipan, pengembang tidak perlu mengulang logika untuk setiap elemen. Meskipun membuat loop tampak rumit, ini cukup sederhana - inilah contohnya:


for(int i=0; i< sort_arr.length; ++i){

Sekarang setelah Anda memiliki loop yang berfungsi, saatnya membuat iterator yang akan mengurutkan semua elemen dalam urutan yang diinginkan. Mulai sekarang, kita akan menyebut iterator sebagai " j".

        int j = i;

4. Membuat "loop sementara"

Dalam hal pengurutan penyisipan, pengulangan "sementara" sangat penting untuk array baru yang diurutkan. Untuk menyiapkannya untuk urutan penyisipan naik, pengembang harus mematuhi dua ketentuan:

Nilai yang diberikan ke j harus lebih besar dari 0
Nilai yang ditetapkan j-1harus lebih besar dari jindeks

Segera setelah kedua kondisi dalam while loop benar, nilai kunci array akan sama dengan indeks j.

5. Menyortir array

Setelah Anda mengatur perulangan while, nilai jdan j-1akan ditukar hingga salah satu atau kedua kondisi dalam perulangan while gagal. Demikian pula, pengurutan akan diulangi untuk setiap nilai dalam perulangan for hingga kondisi for-loop juga gagal. Inilah cara kerja insertion sort dalam praktiknya:


int key = sort_arr[j];
          sort_arr[j] = sort_arr[j-1];
          sort_arr[j-1] = key;
          j = j-1;

Menyortir ArrayList

Meskipun memahami matematika di balik jenis penyisipan itu penting, ketika menyangkut pengembangan perangkat lunak kehidupan nyata, Anda akan lebih banyak menyortir ArrayLists daripada urutan dalam array primitif. Berikut panduan langkah demi langkah untuk mengurutkan ArrayList:

Buat kelas baru Elementuntuk item yang termasuk dalam koleksi.


public class Element {
    private int id;

    public Element(int id) {
        this.id = id;
    }

Di dalam sebuah koleksi, ada sebuah compareTo()metode - kita akan menggunakan ini untuk membandingkan id dari dua elemen.


    public int compareTo(Element element) {
        int res = 0;
        if (this.id < element.getId()) {
            res = -1;
        }
        if (this.id > element.getId()) {
            res = 1;
        }
        return res;
    }
}

Terapkan algoritme dan buat beberapa putaran untuk mengurutkan objek ArrayListalih-alih membandingkannya.


public static void insertionSortArrayList(List<element> list) {
    for (int j = 1; j < list.size(); j++) {
        Element current = list.get(j);
        int i = j-1;
        while ((i > -1) && ((list.get(i).compareTo(current)) == 1)) {
            list.set(i+1, list.get(i));
            i--;
        }
        list.set(i+1, current);
    }
}

Anda juga dapat menambahkan lebih banyak elemen ArrayList, seperti yang ditunjukkan di bawah ini:


List<element> list = new ArrayList<>();

// Create elements w/ IDs 0-24
for (int i = 0; i < 25; i++) {
    list.add(new Element(i));
}

// To use insertion sort, shuffle the values
Collections.shuffle(list);

Sekarang saatnya menyortir:


// This helps print values before sorting
list.forEach(e -> System.out.print(e.getId() + ", "));

// Sort the list
insertionSortArrayList(list);

System.out.println();

// Display a sorted array 
list.forEach(e -> System.out.print(e.getId() + ", "));

Sekarang mari kita bandingkan masukan dan keluaran untuk memastikan kita tidak membuat kesalahan. Berikut adalah perbandingan string yang kami gunakan sebagai contoh.
```
4, 2, 6, 7, 0, 5, 9, 1, 8, 3,
0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
```

Soal Latihan Sortir Penyisipan

Sekarang setelah Anda memahami algoritme pengurutan ini, saatnya untuk menguji keterampilan teoretis dan praktis Anda. Kuis teori #1 Anda diberi larik [1, 4, 6, 8] dan menambahkan elemen baru n = 7 ke dalamnya. Berapa jumlah perbandingan yang perlu Anda buat untuk mendapatkan urutan angka yang diurutkan? Tunjukkan nilai akhir indeks n dalam larik. Kuis teori #2 Pada wawancara kerja, pimpinan tim meminta Anda untuk membuktikan bahwa penyisipan sortir adalah metode yang tidak efisien. Diberi string angka [0, 3, 6, 8, 9], bagaimana urutan urutan input Anda untuk memaksimalkan waktu berjalan yang diperlukan untuk penyortiran? Soal latihan Urutkan larik [0, 1, 4, 5, 2, 3, 7, 9, 8] dalam urutan menaiknya menggunakan insertion sort untuk Java.

Kesimpulan

Tantangan terbesar dalam memahami insertion sort adalah memahami bagaimana prosesnya bekerja. Setelah Anda memahaminya, mengubah template menjadi kode sangatlah mudah. Selama Anda berlatih dan meninjau kembali soal latihan yang relevan dari waktu ke waktu, Anda akan dengan cepat meningkatkan kecepatan pengurutan penyisipan Anda.