Pengurutan merupakan sesuatu yang umum dan sering diperlukan. Saat belajar algoritma dan pemrograman, topik pengurutan biasanya selalu ada. Masalah pengurutan ini juga sering muncul dalam programming, baik itu dalam programming ilmu komputer (seperti soal-soal ICPC, TopCoder, dll) maupun dalam programming dunia industri.
Andaikan kita seorang software developer yang sedang mengerjakan proyek web sepak bola. Dalam web tersebut, kita akan menampilkan klasmen suatu liga. Nah, buat yang belum mengerti apa itu klasmen, begini penjelasannya.
Klasmen merupakan tabel berisi data hasil pertandingan. Hasil pertandingan yang dimaksud adalah:
- jumlah pertandingan yang sudah dijalani (Wins + Draws + Loses [lihat 3 item selanjutnya!])
- jumlah pertandingan yang berakhir dengan dimenangkan (Wins, disingkat menjadi W)
- jumlah pertandingan yang berakhir seri (Draws, disingkat menjadi D)
- jumlah pertandingan yang berakhir dengan kekalahan (Loses, disingkat menjadi L)
- jumlah gol ke gawang lawan (Goals For, disingkat menjadi GF)
- jumlah gol ke gawang sendiri (Goals Against, disingkat menjadi GA)
- selisih gol (Goals Difference, disingkat menjadi GD, yaitu GF – GA)
- poin (Points, disingkat menjadi Pts, yaitu 3 * W + D)
Klasmen disusun berdasarkan poin. Tim yang memiliki poin lebih besar akan berada di atas, demikian sebaliknya. Jika poin kedua sama, diurutkan berdasarkan selisih gol. Tim yang memiliki selisih gol lebih besar akan berada di atas, demikian sebaliknya.
Perhatikan data hasil pertandingan (pertengahan Januari 2012) dari enam klub English Premier League berikut:
Klub/Tim Wins Draws Loses Goals-For Goals-Against ----------------------------------------------------------------- Arsenal 11 3 6 36 28 Chelsea 12 4 5 40 25 Liverpool 9 8 4 24 18 Manchester City 15 3 2 56 16 Manchester United 15 3 3 52 20 Tottenham Hotspur 14 4 3 39 21
Tabel di atas masih berisi data mentah dan belum diurutkan (urutan sementara berdasarkan nama klub). Untuk mengurutkannya, kita harus menghitung poin dan selisih goal, sebagai berikut:
Klub W D L GF GA Pts(1) GD(2) ---------------------------------------------------- Arsenal 11 3 6 36 28 36 8 Chelsea 12 4 5 40 25 40 15 Liverpool 9 8 4 24 18 35 6 Manchester City 15 3 2 56 16 48 40 Manchester United 15 3 3 52 20 48 32 Tottenham Hotspur 14 4 3 39 21 46 18 Keterangan (1) Pts = points = poin (2) GD = goals difference = selisih gol
Maka klasmen akan diperoleh sebagai berikut:
Klub W D L GF GA Pts GD ---------------------------------------------- Manchester City 15 3 2 56 16 48 40 Manchester United 15 3 3 52 20 48 32 Tottenham Hotspur 14 4 3 39 21 46 18 Chelsea 12 4 5 40 25 40 15 Arsenal 11 3 6 36 28 36 8 Liverpool 9 8 4 24 18 35 6
Perhatikan bahwa data sekarang telah diurut berdasarkan poin (Pts) dan selisih gol (GD). Ada dua klub yang memiliki poin sama, yaitu Manchester City dan Manchester United. Tetapi, karena selisih gol Manchester City lebih besar, klub tersebut berada di atas.
Sekarang, anggap data hasil pertandingan tersebut disimpan di tabel tbl_klasmen dalam database. Tabel tersebut memiliki struktur seperti ini:
Field Type ------------------------ team_name VARCHAR wins INTEGER draws INTEGER loses INTEGER goals_for INTEGER goals_against INTEGER
Dan berisi enam data seperti yang diperlihatkan pada tabel pertama di atas.
Jika menggunakan query SQL, maka untuk mendapatkan klasmen akan semudah ini:
SELECT *, (3 * wins + draws) AS points, (goals_for - goals_against) AS goals_difference FROM `tbl_klasmen` ORDER BY points DESC, goals_difference DESC;
Masalah selesai.
Bagaimana kalau datanya tidak berasal dari tabel database?
Jika Anda punya akses ke database, lalu juga punya akses untuk membuat tabel sementara (temporary table), maka Anda bisa membuat tabel sementara, kemudian memasukkan (insert) data ke tabel tersebut, lalu menjalankan query SQL di atas. Terakhir, hapus (drop) tabel sementara yang Anda buat tersebut.
Nah, bagaimana jika tidak memiliki akses ke database sama sekali?
Tentu saja kita harus mengurutkannya dari kode yang kita buat.
Di sini, saya tidak akan menjelaskan algoritma sorting secara detail, melainkan hanya menggunakan sesuatu yang sudah disediakan oleh bahasa pemrograman. Adapun bahasa pemrograman yang akan digunakan adalah Java. Berdasarkan kode Java ini, diharapkan Anda bisa mengimplementasikannya ke dalam bahasa pemrograman berorientasi objek lain, seperti C++, C#.
Sebagai pengganti tabel, tentu saja kita buatkan sebuah class. Pertama, kita akan membuat class berikut:
public class Klasmen
{
public String teamName;
public int wins, draws, loses, goalsFor, goalsAgainst;
}
Class Klasmen di atas memiliki variabel (member) yang sama seperti yang ada di tabel database, bedanya menggunakan bentuk penulisan camelCase. Selain itu, variabel tersebut dibuat public untuk menyingkat kode di pembahasan ini. Karena dengan public, kita nggak perlu setter ataupun getter.
Selanjutnya, kita buat constructor yang akan mengisi keenam variabel tersebut:
public class Klasmen
{
public String teamName;
public int wins, draws, loses, goalsFor, goalsAgainst;
public Klasmen(String teamName, int wins, int draws, int loses, int goalsFor, int goalsAgainst)
{
this.teamName = teamName;
this.wins = wins;
this.draws = draws;
this.loses = loses;
this.goalsFor = goalsFor;
this.goalsAgainst = goalsAgainst;
}
}
Maka dengan hasil di atas, nantinya kita bisa menggunakan class Klasmen sebagai berikut:
Klasmen manc = new Klasmen("Manchester City", 15, 3, 2, 56, 16);
Klasmen mu = new Klasmen("Manchester United", 15, 3, 3, 52, 20);
Lebih tepatnya, nantinya kita akan menggunakannya seperti ini (sebagai array):
Klasmen[] premierLeague = new Klasmen[] {
new Klasmen("Manchester City", 15, 3, 2, 56, 16),
new Klasmen("Manchester United", 15, 3, 3, 52, 20)
};
Sebelum kita bisa mengurutkannya, kita harus menghitung poin dan selisih gol terlebih dulu. Banyak cara yang bisa digunakan, misalnya dengan membuat method untuk menghitung poin dan selisih gol. Di sini, kita akan melakukan perhitungan di dalam constructor. Ini untuk menghemat kode yang dibuat:
public class Klasmen
{
public String teamName;
public int wins, draws, loses, goalsFor, goalsAgainst;
// variabel utk menampung poin dan selisih gol
public int points, goalsDifference;
public Klasmen(String teamName, int wins, int draws, int loses, int goalsFor, int goalsAgainst)
{
this.teamName = teamName;
this.wins = wins;
this.draws = draws;
this.loses = loses;
this.goalsFor = goalsFor;
this.goalsAgainst = goalsAgainst;
// hitung poin dan selisih gol
this.points = 3 * wins + draws;
this.goalsDifference = goalsFor - goalsAgainst;
}
}
Dengan tambahan kode seperti di atas, poin dan selisih gol akan langsung dihitung saat membuat object.
Sekarang masuk ke bagian utama, pengurutan.
Di Java, kita dapat mengurutkan array dengan cara ini:
Arrays.sort(variabel);
Sebagai contoh kita memiliki variabel ini:
int[] nilai = new int[] { 2, 0, 0, 6, 1, 4, 0, 1, 0, 8, 8 };
Maka kita bisa mengurutkannya seperti ini:
Arrays.sort(nilai);
Jika kita tampilkan hasilnya:
System.out.println(Arrays.toString(nilai));
akan diperoleh:
{0, 0, 0, 0, 1, 1, 2, 4, 6, 8, 8}
Nah, itu untuk array sederhana (array dari tipe data primitif). Bagaimana jika array dari class tertentu (seperti Klasmen[] tadi?).
Di Java, ada interface Comparable. Dengan membuat suatu class yang meng-implement Comparable, lalu melakukan implementasi method compareTo(), maka kita bisa memanggil Arrays.sort() pada array dari class tersebut. Dengan kata lain, jika kita memiliki:
class T implements Comparable<T>
{
T(int nilai)
{
// kode
}
public int compareTo(T x)
{
// logika pengurutan
}
}
dan kita membuat array ini:
T[] data = new T[] {
new T(2), // data ke-1
new T(0), // data ke-2
new T(0), // data ke-3
...
new T(8) // data ke-N
};
Kita bisa mengurutkannya dengan cara:
Arrays.sort(data);
Bagaimana item-item dalam variabel data tersebut diurutkan, bergantung pada hasil implementasi method compareTo().
Kode apa yang perlu ditulis di dalam method tersebut?
Method compareTo() menerima sebuah parameter, yaitu T x (object x dari class T). Class T ini adalah class yang didefinisikan saat melakukan implements Comparable<T>. Kembalian (return value) dari method ini adalah integer dengan ketentuan sebagai berikut:
- Apabila item ini lebih kecil daripada item x (lebih tepatnya berada sebelum item x di hasil pengurutan), kembalikan nilai negatif (< 0).
- Apabila item ini sama dengan item x, kembalikan nilai 0.
- Apabila item ini lebih besar daripada item x (lebih tepatnya berada setelah item x di hasil pengurutan), kembalikan nilai positif (> 0).
Kembangkan class Klasmen di atas menjadi seperti ini:
// implement Comparable<T>
public class Klasmen implements Comparable<Klasmen>
{
public String teamName;
public int wins, draws, loses, goalsFor, goalsAgainst;
public int points, goalsDifference;
public Klasmen(String teamName, int wins, int draws, int loses, int goalsFor, int goalsAgainst)
{
this.teamName = teamName;
this.wins = wins;
this.draws = draws;
this.loses = loses;
this.goalsFor = goalsFor;
this.goalsAgainst = goalsAgainst;
this.points = 3 * wins + draws;
this.goalsDifference = goalsFor - goalsAgainst;
}
// dan kita harus mengisi implementasi dari method ini.
public int compareTo(Klasmen o)
{
// logika pengurutan
}
}
Ada dua hal yang mau dibandingkan, yaitu poin dan selisih gol.
Jika poin tim A > poin tim B, maka tim A berada di atas tim B. Jika kita melihat dari atas, maka kita akan menjumpai tim A lalu tim B. Dengan kata lain, tim A berada sebelum tim B di hasil pengurutan, sehingga kembalikan nilai negatif (misalnya -1). Jika sebaliknya (poin tim A < poin tim B), berlaku juga sebaliknya, sehingga kembalikan nilai positif (misalnya 1). Jika sama (poin tim A = poin tim B), lakukan pengurutan berdasarkan kriteria kedua, yaitu selisih gol.
Jika selisih gol tim A > selisih gol tim B, maka tim A berada sebelum tim B di hasil pengurutan, sehingga kembalikan nilai negatif. Jika sebaliknya (selisih gol tim A < selisih gol tim B), berlaku juga sebaliknya, sehingga kembalikan nilai positif. Jika sama (selisih gol tim A = selisih gol tim B), kita anggap sama (kembalikan nilai 0). Di sini kita membatasi masalah pada pengurutan dengan dua kriteria, sehingga kita tidak membahas apabila selisih gol tim A = selisih gol tim B. Anda boleh saja menambahkan kriteria lainnya.
Kasus uji yang kita gunakan juga dibatasi pada dua kriteria ini. Artinya tidak ada kasus uji di mana poin tim A = poin tim B dan selisih gol tim A = selisih gol tim B.
Berdasarkan penjelasan di atas, bisa kita tuliskan sebagai berikut sebagai implementasi method int compareTo(Klasmen o):
public int compareTo(Klasmen o)
{
// -- kriteria pertama --
if (this.points != o.points)
{
if (this.points > o.points) {
return -1;
} else {
return 1;
}
// kalau mau singkat, 5 baris di atas bisa diganti jadi:
// return (this.points > o.points ? -1 : 1);
// karena this.points > o.points, maka berlaku sebaliknya yaitu o.points < this.points.
// karena o.points < this.points, maka o.points - this.points pasti < 0.
// sehingga 5 baris di atas bisa juga diganti dengan:
// return (o.points - this.points);
}
else
{
// -- kriteria kedua --
if (this.goalsDifference != o.goalsDifference)
{
return (o.goalsDifference - this.goalsDifference);
}
else
{
return 0; // batasan masalah, tidak ada kriteria ketiga.
}
}
}
Sehingga jika digabungkan, hasil akhir class Klasmen adalah sebagai berikut:
public class Klasmen implements Comparable<Klasmen>
{
public String teamName;
public int wins, draws, loses, goalsFor, goalsAgainst;
public int points, goalsDifference;
public Klasmen(String teamName, int wins, int draws, int loses, int goalsFor, int goalsAgainst)
{
this.teamName = teamName;
this.wins = wins;
this.draws = draws;
this.loses = loses;
this.goalsFor = goalsFor;
this.goalsAgainst = goalsAgainst;
this.points = 3 * wins + draws;
this.goalsDifference = goalsFor - goalsAgainst;
}
public int compareTo(Klasmen o)
{
if (this.points != o.points)
{
return (o.points - this.points);
}
else
{
if (this.goalsDifference !=o.goalsDifference)
{
return (o.goalsDifference - this.goalsDifference);
}
else
{
return 0;
}
}
}
}
Selesai. sekarang saatnya melakukan pengujian. Tuliskan kasus uji berikut:
Klasmen[] premierLeague = new Klasmen[] {
new Klasmen("Arsenal", 11, 3, 6, 36, 28),
new Klasmen("Chelsea", 12, 4, 5, 40, 25),
new Klasmen("Liverpool", 9, 8, 4, 24, 18),
new Klasmen("Manchester City", 15, 3, 2, 56, 16),
new Klasmen("Manchester United", 15, 3, 3, 52, 20),
new Klasmen("Tottenham Hotspur", 14, 4, 3, 39, 21)
};
Tampilkan isi array premierLeague sebelum diurutkan:
for (Klasmen klub : premierLeague) {
System.out.format("- %s [poin = %d, selisih gol = %d]\n", klub.teamName, klub.points, klub.goalsDifference);
}
Maka hasilnya seperti ini:
- Arsenal [poin = 36, selisih gol = 8] - Chelsea [poin = 40, selisih gol = 15] - Liverpool [poin = 35, selisih gol = 6] - Manchester City [poin = 48, selisih gol = 40] - Manchester United [poin = 48, selisih gol = 32] - Tottenham Hotspur [poin = 46, selisih gol = 18]
Lakukan pengurutan:
Arrays.sort(premierLeague);
Tampilkan isi array premierLeague setelah diurutkan:
for (Klasmen klub : premierLeague) {
System.out.format("- %s [poin = %d, selisih gol = %d]\n", klub.teamName, klub.points, klub.goalsDifference);
}
Maka hasilnya seperti ini:
- Manchester City [poin = 48, selisih gol = 40] - Manchester United [poin = 48, selisih gol = 32] - Tottenham Hotspur [poin = 46, selisih gol = 18] - Chelsea [poin = 40, selisih gol = 15] - Arsenal [poin = 36, selisih gol = 8] - Liverpool [poin = 35, selisih gol = 6]
Terlihat bahwa data sudah diurut berdasarkan poin terbesar ke poin terkecil. Jika poin sama, data diurut berdasarkan selisih gol terbesar ke selisih gol terkecil.
Loading tweets...
Komentar Terkini