Cara Mengurutkan Array di Java

Penyortiran adalah salah satu operasi yang paling umum dan diperlukan dalam pemrograman. Ini mewakili pengurutan beberapa kumpulan elemen dalam urutan tertentu. Artikel ini membahas tentang metode standar untuk mengurutkan array di Java.

Secara singkat tentang penyortiran

Jadi, pengurutan adalah pengurutan sekumpulan data. Dalam kasus kami, array. Tujuan pengurutan array atau struktur data lainnya adalah untuk memudahkan pencarian, manipulasi, atau penguraian data dalam kumpulan. Pemrogram sangat sering membutuhkan pengurutan sehingga bahasa pemrograman apa pun menyertakan metode bawaan untuk mengurutkan array, daftar, dan struktur data terurut lainnya. Untuk menggunakan metode tersebut, hubungi mereka. Pengoperasiannya disederhanakan semaksimal mungkin. Biasanya, metode bawaan dioptimalkan secara maksimal; dalam banyak kasus, menggunakannya untuk pekerjaan atau proyek Anda adalah ide yang bagus. Namun, hampir setiap programmer, selama studinya, perlu mengimplementasikan algoritma pengurutan sendiri. Oleh karena itu, latihan sempurna ini mengajarkan Anda untuk memahami esensi pemrograman. Selain itu, terkadang Anda memerlukan metode penyortiran non-standar dalam pekerjaan. Ada banyak algoritma pengurutan. Mereka memiliki kekuatan dan kelemahan tergantung pada jenis atau ukuran kumpulan data. Algoritme pengurutan standar mencakup pengurutan gelembung, pengurutan pilihan, pengurutan penyisipan, pengurutan gabungan, dan pengurutan cepat.

Metode bawaan untuk mengurutkan array di Java: Arrays.sort

Mari kita mulai dengan yang paling sederhana. Seseorang telah menulis metode untuk mengurutkan array di Java untuk kita. Metode ini ada di kelas Arrays , lebih khusus lagi java.util.Arrays . Kelas ini berisi berbagai metode untuk bekerja dengan array, seperti pengurutan dan pencarian. Metode Arrays.sort menyediakan cara mudah untuk mengurutkan array di Java, baik berisi string, integer, atau elemen lainnya. Ada beberapa variasi metode Arrays.sort di Java. Berikut adalah beberapa metode pengurutan yang umum digunakan dari kelas Arrays :

• Arrays.sort(Array) : menggunakannya untuk mengurutkan array tipe primitif atau objek dalam urutan menaik. Ia menggunakan susunan alami dari unsur-unsurnya.
• Arrays.sort(Array, fromIndex, toIndex) : Metode pengurutan yang kelebihan beban ini memungkinkan Anda mengurutkan hanya sebagian dari Array yang ditentukan oleh parameter fromIndex dan toIndex.
• Arrays.sort(Array, comparator) : yang ini untuk mengurutkan array objek menggunakan komparator khusus. Komparator mendefinisikan urutan elemen.
• Arrays.parallelSort(Array) : Versi metode ini mengurutkan Array secara paralel, memanfaatkan banyak thread untuk meningkatkan kinerja. Ini bermanfaat untuk menyortir array besar.
• Arrays.parallelSort(Array, fromIndex, toIndex) : Versi metode parallelSort yang kelebihan beban ini memungkinkan pengurutan rentang elemen tertentu dalam Array .

Mereka memungkinkan Anda dengan cepat mengatur elemen berdasarkan tatanan alaminya atau menggunakan pembanding khusus. Mari kita jelajahi metode ini dengan dua contoh, satu melibatkan string.

Contoh 1: Menyortir String

Misalkan kita memiliki serangkaian alat musik petik: "biola", "viola", "cello", dan "double bass". Kita dapat menggunakan metode Array.sort untuk menyusunnya berdasarkan abjad.

import java.util.Arrays;
//Arrays.sort example
public class StringSortExample {
    public static void main(String[] args) {
        String[] instruments = {"violin", "viola", "cello", "double bass"};

        Arrays.sort(instruments);

        System.out.println("Sorted Instruments:");
        for (String instrument : instruments) {
            System.out.println(instrument);
        }
    }
}

Outputnya ada di sini: Dalam program ini, pertama-tama kita mengimpor kelas java.util.Arrays untuk mendapatkan akses ke metode Array.sort . Kemudian kita membuat array string yang disebut instrumen yang berisi nama alat musik. Setelah itu, kami memanggil Arrays.sort(instruments) . Jadi metode ini mendapatkan array, mengurutkan elemen dalam urutan menaik berdasarkan urutan alaminya (menurut abjad). Terakhir, kita mengulang Array yang telah diurutkan dan mencetak setiap instrumen.

Contoh 2: Mengurutkan Bilangan Bulat

Mari kita perhatikan contoh lain di mana kita mengurutkan array bilangan bulat dalam urutan menaik.

import java.util.Arrays;

public class IntegerSortExample {
    public static void main(String[] args) {
        int[] numbers = {8, 2, 7, 3, 1, 5};
//sort an array using Arrays.sort
        Arrays.sort(numbers);

        System.out.println("Sorted Numbers:");
        for (int number : numbers) {
            System.out.println(number);
        }
    }
}

Keluaran: Di sini kita membuat array bilangan bulat yang disebut angka dengan beberapa elemen yang tidak diurutkan. Selanjutnya, kita memanggil Arrays.sort(numbers) untuk mengurutkan array dalam urutan menaik. Perhatikan bahwa metode Array.sort memodifikasi array asli di tempatnya. Jadi untuk menjaga Array yang asli , buatlah salinannya sebelum menyortir.

Contoh 3: urutan menurun

Bagaimana dengan urutan menurun? Ini juga mudah dengan Arrays.sort . Cukup gunakan pembanding khusus. Berikut ini contohnya:

import java.util.Arrays;
import java.util.Comparator;
//Arrays.sort with custom comparator example
public class DescendingSortExample {
    public static void main(String[] args) {
        Integer[] numbers = {8, 2, 7, 3, 1, 5};
        //sort an Array using Arrays.sort
        Arrays.sort(numbers, Comparator.reverseOrder());

        System.out.println("Sorted Numbers (Descending):");
        for (int number : numbers) {
            System.out.println(number);
        }
    }
}

Outputnya berikutnya: Di sini kita punya array bilangan bulat bernama angka. Dengan meneruskan Comparator.reverseOrder() sebagai argumen kedua ke metode Arrays.sort , kita menentukan komparator khusus yang mengurutkan elemen dalam urutan menurun. Metode Comparator.reverseOrder() mengembalikan komparator yang membalik urutan alami elemen. Perhatikan bahwa di sini, kita menggunakan kelas wrapper Integer alih-alih tipe int primitif karena metode Comparator.reverseOrder() memerlukan objek. Jika Anda memiliki array nilai int primitif, Anda juga perlu mengonversinya menjadi objek Integer sebelum menggunakan pendekatan ini. Dengan menggunakan pembanding khusus, Anda dapat dengan mudah mengurutkan array dalam urutan menurun menggunakan metode Arrays.sort di Java.

Algoritma pengurutan klasik yang ditulis sendiri di Java

Anda telah melihat tugas pengurutan array jika Anda mempelajari Ilmu Komputer secara mandiri atau di universitas. Ada banyak algoritma pengurutan yang berbeda, dan kami akan menerapkan beberapa di antaranya di artikel ini. Secara umum, semakin mudah suatu algoritma diimplementasikan, semakin kurang efisien algoritma tersebut. Pemrogram mengukur efisiensi algoritma diukur dengan waktu operasinya dan memori yang dihabiskan untuk sumber daya. Itu bukan topik artikel kami, tapi kami menyebutkan bahwa Arrays.sort di Java adalah algoritma yang efektif.

Sortir Gelembung

Mari kita mulai dengan algoritma yang paling populer di kalangan pelajar: Bubble sort. Caranya mudah: algoritme membandingkan dua elemen lalu menukarnya jika urutannya salah, dan seterusnya hingga akhir array. Ternyata elemen yang lebih kecil "mengambang" ke akhir Array , seperti gelembung soda yang muncul ke atas.

public class BubbleSort {

       public static void bubbleSort(int[] myArray) {
           int n = myArray.length;
           for (int i = 0; i < n - 1; i++) {
               for (int j = 0; j < n - i - 1; j++) {
                   if (myArray[j] > myArray[j + 1]) {
                       // Swap myArray[j] and myArray[j+1]
                       int temp = myArray[j];
                       myArray[j] = myArray[j + 1];
                       myArray[j + 1] = temp;
                   }
               }
           }
       }

       public static void main(String[] args) {
           int[] arr = {18, 28, 2, 7, 90, 45};

           System.out.println("Array before sorting:");
           for (int num : arr) {
               System.out.print(num + " ");
           }

           bubbleSort(arr);

           System.out.println("\nArray after sorting:");
           for (int num : arr) {
               System.out.print(num + " ");
           }
       }
}

Di sini metode ini mengambil array bilangan bulat sebagai masukan. Loop luar beralih dari 0 ke n-1. Di sini n adalah ukuran array. Loop bagian dalam membandingkan elemen yang berdekatan. Jika urutannya salah, metode menukarnya. Prosedur ini diulangi hingga seluruh array telah diurutkan. Berikut adalah output dari program kami:

Sortir Seleksi

Algoritma seleksi mengurutkan array dengan berulang kali mencari elemen terkecil dari bagian yang tidak disortir dan menempatkannya di awal. Mari kita menulisnya di Java:

public class SelectionSort {
   public static void selectionSort(int[] myArray) {
       int n = myArray.length;

       for (int i = 0; i < n - 1; i++) {
           int minIndex = i;

           // Find the index of the minimum element in the unsorted part of the array
           for (int j = i + 1; j < n; j++) {
               if (myArray[j] < myArray[minIndex]) {
                   minIndex = j;
               }
           }

           // Swap the minimum element with the first element of the unsorted part
           int temp = myArray[minIndex];
           myArray[minIndex] = myArray[i];
           myArray[i] = temp;
       }
   }

   public static void main(String[] args) {
       int[] arr = {18, 28, 45, 2, 90, 7};

       System.out.println("Array before sorting:");
       for (int num : arr) {
           System.out.print(num + " ");
       }

       selectionSort(arr);

       System.out.println("\nArray after sorting:");
       for (int num : arr) {
           System.out.print(num + " ");
       }
   }
}

Berikut adalah keluaran programnya: Mari kita jelaskan langkah demi langkah. Loop luar melakukan iterasi dari awal Array ke elemen kedua hingga terakhir (hingga n-1). Perulangan ini memilih setiap elemen satu per satu sebagai titik awal dari bagian Array yang tidak disortir . Di dalam loop luar, kami menginisialisasi minIndex ke indeks i saat ini , dengan asumsi itu adalah indeks item terkecil di bagian Array yang tidak disortir . Loop bagian dalam dimulai dari i+1 dan naik ke elemen terakhir Array . Ia mencari indeks item terkecil di bagian Array yang tidak diurutkan dengan membandingkan setiap elemen dengan elemen minimum saat ini ( arr[minIndex] ). Jika kami menemukan elemen yang lebih kecil dari elemen minimum saat ini, kami memperbarui minIndex ke indeks elemen minimum baru. Setelah loop dalam selesai, kami menemukan indeks elemen minimum di bagian Array yang tidak disortir . Kami kemudian menukar elemen minimum dengan elemen pertama dari bagian yang tidak disortir dengan menggunakan variabel sementara temp. Perulangan luar berlanjut hingga semua elemen diurutkan, secara bertahap memperluas bagian Array yang diurutkan . Terakhir, Array yang diurutkan dicetak dalam metode utama sebelum dan sesudah memanggil metode seleksiSort .

Gabungkan Sortir

Merge Sort adalah algoritma bagi-dan-taklukkan yang secara rekursif membagi Array menjadi sub-array yang lebih kecil, mengurutkannya, dan kemudian menggabungkannya untuk mendapatkan array yang terurut. Pengurutan Penggabungan stabil dan digunakan secara luas, terutama ketika stabilitas dan jaminan kompleksitas waktu dalam kasus terburuk diperlukan.

public class MergeSort {

      //Merge Sort array
      public static void mergeSort(int[] myArray) {
        if (myArray.length <= 1) {
            return;
        }

        int mid = myArray.length / 2;
        int[] left = new int[mid];
        int[] right = new int[myArray.length - mid];

        System.arraycopy(myArray, 0, left, 0, mid);
        System.arraycopy(myArray, mid, right, 0, myArray.length - mid);

        mergeSort(left);
        mergeSort(right);

        merge(myArray, left, right);
    }

    public static void merge(int[] arr, int[] left, int[] right) {
        int i = 0; // index for left subarray
        int j = 0; // index for right subarray
        int k = 0; // index for merged array

        while (i < left.length && j < right.length) {
            if (left[i] <= right[j]) {
                arr[k++] = left[i++];
            } else {
                arr[k++] = right[j++];
            }
        }

        while (i < left.length) {
            arr[k++] = left[i++];
        }

        while (j < right.length) {
            arr[k++] = right[j++];
        }
    }

    public static void main(String[] args) {
        int[] arr = {18, 2, 28, 7, 90, 45};

        System.out.println("Array before sorting:");
        for (int num : arr) {
            System.out.print(num + " ");
        }

        mergeSort(arr);

        System.out.println("\nArray after sorting:");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

Outputnya di sini adalah: Mari kita jelaskan lebih tepatnya cara kerjanya. Algoritme membagi Array menjadi dua bagian secara rekursif hingga kasus dasar tercapai (ketika Array memiliki satu atau nol elemen). Kemudian ia menggabungkan kembali bagian yang telah diurutkan menggunakan metode penggabungan. Metode penggabungan mengambil tiga array sebagai input: Array asli dan subarray kiri dan kanan (kiri dan kanan). Ini membandingkan elemen dari subarray kiri dan kanan dan menggabungkannya ke dalam Array asli dalam urutan yang diurutkan.

Sortir penyisipan

Pengurutan Penyisipan bekerja dengan menyisipkan berulang kali elemen dari bagian yang tidak disortir ke posisi yang benar di bagian yang diurutkan. Ini berkinerja baik untuk kumpulan data kecil atau data yang hampir diurutkan.

public class InsertionSort {
    public static void insertionSort(int[] myArray) {
        int n = myArray.length;

        for (int i = 1; i < n; i++) {
            int key = myArray[i];
            int j = i - 1;

            while (j >= 0 && myArray[j] > key) {
                myArray[j + 1] = myArray[j];
                j--;
            }

            myArray[j + 1] = key;
        }
    }

    public static void main(String[] args) {
        int[] arr = {18, 90, 7, 28, 45, 2};

        System.out.println("Array before sorting:");
        for (int num : arr) {
            System.out.print(num + " ");
        }

        insertionSort(arr);

        System.out.println("\nArray after sorting:");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

Output dari program ini seperti biasa: Di sini metode insertionSort mengimplementasikan algoritma Insertion Sort. Itu mengulangi Array dan menganggap setiap elemen sebagai kunci. Ini membandingkan kunci dengan elemen sebelumnya dan memindahkannya satu posisi ke depan jika lebih besar, secara efektif menggeser elemen untuk memberikan ruang bagi kunci pada posisi yang benar. Loop luar melakukan iterasi dari elemen kedua ( i = 1 ) ke elemen terakhir Array. Loop dalam dimulai dari elemen saat ini ( arr[i] ) dan berjalan mundur ( j = i - 1 ) hingga menemukan posisi kunci yang benar atau mencapai awal Array . Di dalam loop dalam, jika sebuah elemen ( arr[j] ) lebih besar dari kuncinya, maka elemen tersebut akan digeser satu posisi ke depan ( arr[j + 1] = arr[j] ) untuk memberikan ruang bagi kunci. Proses ini berlanjut hingga posisi kunci yang benar ditemukan. Setelah loop dalam selesai, kunci ditempatkan pada posisi yang benar ( arr[j + 1] = key ). Dalam metode utama, contoh array dibuat dan dicetak sebelum dan sesudah pengurutan menggunakan metode insertionSort .

Penyortiran cepat

Penyortiran Cepat adalah algoritma bagi-dan-taklukkan yang memilih elemen pivot dan mempartisi Array di sekitar pivot. Biasanya, Penyortiran Cepat lebih cepat daripada Pengurutan Gabung untuk kumpulan data berukuran kecil dan menengah karena faktor konstanta yang rendah.

public class QuickSort {

       public static void quickSort(int[] myArray, int low, int high) {
           if (low < high) {
               int pivotIndex = partition(myArray, low, high);
               quickSort(myArray, low, pivotIndex - 1);
               quickSort(myArray, pivotIndex + 1, high);
           }
       }

       public static int partition(int[] arr, int low, int high) {
           int pivot = arr[high];
           int i = low - 1;

           for (int j = low; j < high; j++) {
               if (arr[j] <= pivot) {
                   i++;
                   swap(arr, i, j);
               }
           }

           swap(arr, i + 1, high);
           return i + 1;
       }

       public static void swap(int[] arr, int i, int j) {
           int temp = arr[i];
           arr[i] = arr[j];
           arr[j] = temp;
       }

       public static void main(String[] args) {
           int[] arr = {18, 28, 2, 90, 7, 45};

           System.out.println("Array before sorting:");
           for (int num : arr) {
               System.out.print(num + " ");
           }

           quickSort(arr, 0, arr.length - 1);

           System.out.println("\nArray after sorting:");
           for (int num : arr) {
               System.out.print(num + " ");
           }
       }
}

Outputnya ada di sini: Jadi di sini kita punya tiga metode untuk menerapkan pengurutan cepat. Metode quickSort mengambil tiga parameter: Array yang akan diurutkan, indeks subarray rendah, dan indeks tinggi subarray. Awalnya, ia memeriksa apakah subarray memiliki lebih dari satu elemen. Jika demikian, ia memilih pivot menggunakan metode partisi, mengurutkan subarray sebelum pivot secara rekursif, dan mengurutkan subarray setelah pivot secara rekursif. Metode partisi memilih pivot sebagai elemen terakhir dari subarray ( arr[high] ). Ini menetapkan indeks partisi (i) ke indeks rendah dikurangi 1. Kemudian melakukan iterasi dari indeks rendah ke indeks tinggi - 1 dan memeriksa apakah setiap elemen kurang dari atau sama dengan pivot. Jika demikian, ia menukar elemen dengan elemen pada indeks partisi (i) dan menambah indeks partisi. Terakhir, ia menukar elemen pivot dengan elemen pada indeks partisi +1 dan mengembalikan indeks partisi. Metode partisi memilih pivot sebagai elemen terakhir dari subarray ( arr[high] ). Ini menetapkan indeks partisi (i) ke indeks rendah dikurangi 1. Kemudian melakukan iterasi dari indeks rendah ke indeks tinggi - 1 dan memeriksa apakah setiap item lebih kecil atau sama dengan pivot. Jika demikian, ia menukar elemen dengan elemen pada indeks partisi (i) dan menambah indeks partisi. Terakhir, ia menukar elemen pivot dengan elemen pada indeks partisi +1 dan mengembalikan indeks partisi. Metode swap adalah metode utilitas yang digunakan untuk menukar dua elemen dalam Array . Dalam metode utama , contoh array dibuat dan dicetak sebelum dan sesudah pengurutan menggunakan metode quickSort .

Kesimpulan

Dari artikel ini Anda telah mengetahui cara mengurutkan array dalam bahasa Java. Anda dapat menggunakan metode Arrays.sort bawaan atau menulis implementasi Anda sendiri atas metode pengurutan populer seperti pengurutan gelembung, pengurutan gabungan, dan seterusnya. Anda juga dapat mencoba menyerang metode penyortiran Anda sendiri. Itu tergantung pada tugas Anda. Jika Anda perlu menyelesaikan masalah penyortiran dengan cepat, cukup gunakan metode yang telah ditulis sebelumnya. Jika Anda mempelajari pemrograman dan mencoba menjadi lebih baik, ada baiknya Anda menulis sendiri beberapa metode pengurutan.