KAL
Menu

Pengurutan

Mengurutkan objek dengan Comparable dan Comparator, termasuk pengurutan multi-kunci.

Daftar isi

Mengurutkan koleksi berarti menyusun ulang elemennya menurut suatu aturan pembanding, dan Java menyediakan dua jalur untuk menyatakannya, yaitu Comparable yang tertanam di kelasnya dan Comparator yang berdiri di luar kelasnya. Topik ini mempraktikkan keduanya pada koleksi objek, menuntaskan pengurutan multi-kunci, lalu menutup dengan aturan main yang membuat hasil pengurutan tetap bisa diprediksi.

Urutan alami lewat Comparable#

Kelas yang menerapkan Comparable<T> wajib menyediakan metode compareTo(T), yang mengembalikan bilangan negatif bila objek ini mendahului parameter, nol bila setara, dan positif bila mendudukinya. Pemanggil hanya membaca tanda nilai kembalian itu, bukan besarnya. Setelah kontrak itu ada, Collections.sort maupun metode sort milik list sendiri dapat dipanggil tanpa argumen tambahan.

java DemoComparable.java 
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class DemoComparable {

    public static void main(String[] args) {
        List<Buku> rakBuku = new ArrayList<>();
        rakBuku.add(new Buku("Peta Jalur Pendakian", 240));
        rakBuku.add(new Buku("Panduan Merawat Sepeda", 180));
        rakBuku.add(new Buku("Kamus Miniatur", 96));

        System.out.println("sebelum diurutkan:");
        for (Buku buku : rakBuku) {
            System.out.println("  " + buku);
        }

        Collections.sort(rakBuku);

        System.out.println("sesudah diurutkan:");
        for (Buku buku : rakBuku) {
            System.out.println("  " + buku);
        }
    }
}

class Buku implements Comparable<Buku> {
    String judul;
    int jumlahHalaman;

    Buku(String judul, int jumlahHalaman) {
        this.judul = judul;
        this.jumlahHalaman = jumlahHalaman;
    }

    @Override
    public int compareTo(Buku lain) {
        return Integer.compare(this.jumlahHalaman, lain.jumlahHalaman);
    }

    @Override
    public String toString() {
        return judul + " (" + jumlahHalaman + " halaman)";
    }
}
text Keluaran 
sebelum diurutkan:
  Peta Jalur Pendakian (240 halaman)
  Panduan Merawat Sepeda (180 halaman)
  Kamus Miniatur (96 halaman)
sesudah diurutkan:
  Kamus Miniatur (96 halaman)
  Panduan Merawat Sepeda (180 halaman)
  Peta Jalur Pendakian (240 halaman)

Implementasi compareTo di atas menunjukkan kebiasaan yang sebaiknya ditiru, yaitu memanggil Integer.compare alih-alih mengurangi kedua bilangan. Pola pengurangan terlihat singkat, tetapi bisa meluber (overflow) untuk selisih yang besar, sedangkan compare selalu aman. Pengurutan di sini menaik, dan bila urutan menurun yang dikehendaki, cukup balik tandanya lewat Comparator seperti pada bagian berikut.

Urutan alami String juga perlu dipahami sebelum mengandalkannya. Pembandingannya mengikuti nilai Unicode tiap karakter, sehingga semua huruf kapital mendahului huruf kecil, dan teks “Zebra” akan terurut sebelum “apel”. Pengurutan nama dengan huruf campuran karenanya sering tidak sesuai dugaan, dan butuh Comparator khusus, misalnya lewat compareToIgnoreCase, bila yang dimaksud adalah urutan alfabet sehari-hari.

Urutan luar lewat Comparator#

Comparator<T> memisahkan aturan pengurutan dari kelasnya, sehingga satu kelas bisa disusun dengan banyak cara tanpa menyentuh kodenya. Bentuk lamanya menulis metode compare manual, sedangkan bentuk modernnya merakit aturan dari lambda lewat metode pabrik Comparator.comparing beserta saudara bertipenya.

java Contoh: merakit Comparator dari lambda 
// tidak-dijalankan
Comparator<Siswa> menurutNilai = Comparator.comparingInt(s -> s.nilai);
Comparator<Siswa> menurutNilaiMenurun = menurutNilai.reversed();
Comparator<Siswa> menurutNama = Comparator.comparing(s -> s.nama);

Metode pabrik itu memilih berdasarkan tipe field yang dibandingkan, misalnya comparingInt untuk int, comparingDouble untuk double, dan comparing untuk tipe yang punya urutan alami seperti String. Argumennya bisa berupa lambda, dan bila kelasnya menyediakan metode pembaca field, method reference membuat barisnya lebih ringkas lagi. Rangkaian pembanding kemudian bisa digabung lewat thenComparing, dan urutan penyambungannya menentukan urutan prioritas kuncinya.

Pengurutan multi-kunci#

Pengurutan nyata jarang bertumpu pada satu kunci. Kasus daftar siswa biasanya diurutkan menurut kelasnya lebih dahulu, lalu nilai tertinggi di dalam kelas yang sama, dan nama sebagai pemecah seri. Rangkaian thenComparing menampung kebutuhan itu dengan rapi.

java DemoComparator.java 
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

public class DemoComparator {

    public static void main(String[] args) {
        List<Siswa> daftarSiswa = new ArrayList<>();
        daftarSiswa.add(new Siswa("Ali", 3, 88));
        daftarSiswa.add(new Siswa("Budi", 1, 91));
        daftarSiswa.add(new Siswa("Citra", 3, 79));
        daftarSiswa.add(new Siswa("Dewi", 2, 91));
        daftarSiswa.add(new Siswa("Eka", 1, 84));

        Comparator<Siswa> urutanKelas = Comparator.comparingInt(s -> s.kelas);
        Comparator<Siswa> urutanKelasNilai = urutanKelas
                .thenComparing(Comparator.comparingInt((Siswa s) -> s.nilai).reversed())
                .thenComparing(s -> s.nama);

        daftarSiswa.sort(urutanKelasNilai);
        for (Siswa siswa : daftarSiswa) {
            System.out.println(siswa);
        }
    }
}

class Siswa {
    String nama;
    int kelas;
    int nilai;

    Siswa(String nama, int kelas, int nilai) {
        this.nama = nama;
        this.kelas = kelas;
        this.nilai = nilai;
    }

    @Override
    public String toString() {
        return "kelas " + kelas + " | nilai " + nilai + " | " + nama;
    }
}
text Keluaran 
kelas 1 | nilai 91 | Budi
kelas 1 | nilai 84 | Eka
kelas 2 | nilai 91 | Dewi
kelas 3 | nilai 88 | Ali
kelas 3 | nilai 79 | Citra

Keluarannya mengikuti tiga kunci secara berurutan. Kelas naik dari 1 sampai 3, nilai di dalam kelas yang sama turun karena reversed() hanya melekat pada pembanding nilai, dan nama hanya bekerja sebagai pemecah seri yang tak sempat terpakai pada data ini. Pemanggilan sort juga dilakukan langsung pada list lewat daftarSiswa.sort(...), bentuk yang kini lebih lazim daripada Collections.sort untuk list biasa.

Pengurutan di tempat lain#

sort milik list bukan satu-satunya tempat aturan pembanding ini bekerja. Kelas Arrays.sort mengurutkan array dengan aturan serupa, dan TreeSet serta TreeMap memanggil compareTo atau Comparator yang sama pada setiap penyisipan, sehingga isinya terjaga terurut tanpa pemanggilan sort sama sekali. Pengetahuan ini membuat satu implementasi pembanding bermanfaat di banyak tempat, bukan hanya di satu baris pengurutan.

Satu perbedaan penting perlu dicatat antara keduanya. Pengurutan objek, baik lewat Collections.sort, list.sort, maupun Arrays.sort untuk array objek, menjanjikan sifat stabil sebagaimana dicatat di atas. Sebaliknya, Arrays.sort untuk array primitif tidak menjanjikan kestabilan, dan itu bukan kelalaian, karena dua nilai int yang sama memang tidak bisa dibedakan satu sama lain. Akibatnya, aturan kunci kedua seperti “nilai sama diurutkan menurut nama” tidak dapat dinyatakan untuk array primitif, dan kebutuhan semacam itu diselesaikan dengan membungkus datanya dalam objek atau record.

Kesalahan umum#

  • Menulis return this.nilai - lain.nilai di dalam compareTo. Pengurangan bisa meluber untuk selisih yang melewati batas int dan menghasilkan tanda yang salah. Gunakan Integer.compare atau Double.compare.
  • Mengira sort menghasilkan list baru. Pengurutan terjadi di tempat, sehingga urutan lama hilang dan list aslinya yang berubah. Salin dahulu listnya bila urutan awal perlu dipertahankan.
  • Menempelkan reversed() pada seluruh rantai alih-alih pada kunci yang dikehendaki. reversed() membalik pembanding yang memanggilnya, sehingga letaknya menentukan kunci mana yang ikut terbalik.
  • Mengurutkan Set langsung lewat Collections.sort. Metode itu menerima List, karena pengurutan menuntut urutan posisi yang tidak dimiliki Set. Salin isinya ke ArrayList dahulu bila tampilan terurut diperlukan.

Ringkasan#

  • Comparable menanamkan satu urutan alami di kelasnya melalui compareTo, yang cukup dibaca tandanya saja.
  • Comparator melepas urutan ke luar kelas, dirakit lewat comparing, comparingInt, reversed, dan dirangkai thenComparing untuk banyak kunci.
  • list.sort(...) dan Collections.sort(...) mengurutkan di tempat dan bersifat stabil terhadap elemen yang setara.
  • compareTo sebaiknya sepakat dengan equals, karena struktur terurut seperti TreeSet mengandalkan pembandingnya semata.

Referensi#