Pengurutan (Sorting)
• proses mangatur sekumpulan obyek/data menurut urutan atau susunan tertentu.
• Urutan obyek/data tersebut dapat menaik (ascending) atau menurun (desencending).
• Data yang diurutkan dapat berupa data bertipe dasar atau data bertipe struktur
• Data yang sudah terurut memiliki keuntungan yaitu Mempercepat proses pencarian data.
Metode Pengurutan
Algoritma pengurutan / sorting bermacam-macam dan setiap algoritma ini memiliki kinerja yang berbeda-beda. Berikut ini macam-macam algoritma pengurutan:
1. Metode Selection Sort
2. Metode Buble Sort
3. Metode Insertion
Hal yg mempengaruhi Kecepatan Algoritma Sorting adalah Jumlah Operasi Perbandingan & Jumlah OperasiPemindahan Data
Selection Sort (Metode Seleksi).
Tehnik pengurutan dengan cara pemilihan elemen dgn memilih elemen data terkecil utk kemudian dibandingkan & ditukarkan dgn elemen pd data awal, dst s/d seluruh elemen shg akan menghasilkan pola data yg telah disort.
• Merupakan kombinasi antara sorting dan searching
• Untuk setiap proses, akan dicari elemen-elemen yang belum diurutkan yang memiliki nilai terkecil atau terbesar akan dipertukarkan ke posisi yang tepat di dalam array.
• Misalnya untuk putaran pertama, akan dicari data dengan nilai terkecil dan data ini akan ditempatkan di indeks terkecil (data[0]), pada putaran kedua akan dicari data kedua terkecil, dan akan ditempatkan di indeks kedua (data[1]).
ALGORITMA SELECTION SORT.
- Pengecekan dimulai data ke-1 sampai dengan data ke-n
- Tentukan bilangan dengan Index terkecil dari data bilangan tersebut
- Tukar bilangan dengan Index terkecil tersebut dengan bilangan pertama ( I = 1 ) dari data bilangan tersebut
- Lakukan langkah 2 dan 3 untuk bilangan berikutnya ( I= I+1 ) sampai didapatkan urutan yg optimal
Metode Bubble Sort (Gelembung)
Teknik
yang diinspirasi oleh gelembung sabun yang berada dipermukaan air.
Karena berat jenis gelembung lebih ringan dari pada air, maka gelembung
akan naik keatas.
(benda yang berat akan terbenam, benda ringan terapung).
Elemen data yang paling kecil diapungkan “diangkat keatas” melalui proses pertukaran.
Bubble Sort mengurutkan data dengan cara membandingkan elemen sekarang dengan elemen berikutnya
Algoritma Bubble Sort
- Pengecekan mulai dari data ke-1 sampai data ke-n
- Bandingkan data ke-n dengan data sebelumnya (n-1)
- Jika lebih kecil maka pindahkan bilangan tersebut dengan bilangan yg ada didepannya ( sebelumnya ) satu persatu (n-1,n-2,n-3,....dst)
- Jika lebih besar maka tidak terjadi pemindahan
- Ulangi langkah 2 dan 3 s/d sort optimal.
Analogi :
Larik dengan urut menaik, elemen larik yang berharga paling kecil ‘diapungkan’, artinya diangkat ke atas (atau ke ujung kiri larik) melalui proses pertukaran. Proses pengapungan ini dilakukan sebanyak N-1 langkah dengan N adalah ukuran larik. Pada akhir setiap langkah ke-I, larik L[1..N] akan terdiri atas dua bagian yaitu bagian yang sudah terurut, yaitu L[1..I] dan bagian yang belum terurut L[I+1..N]. Setelah langkah terakhir, diperoleh larik L[1..N] yang terurut menaik.
Bubble Sort
Disebut juga dengan metode Penukaran (Exchange Sort), yaitu metoda yang
mendasarkan pada penukaran elemen untuk mencapai keadaan urut yang
diinginkan.
Algoritma Metode gelembung :
- langkah 0 : Baca vector yang akan diurutkan (dalam program utama)
- langkah 1 : Kerjakan langkah 2 untuk i = 1 sampai N-1
- langkah 2 : Kerjakan langkah 3 untuk j = 1 sampai N- i
- langkah 3 : Tes apakah A[j] > A[j +1] ? Jika ya, tukarkan nilai kedua elemen ini
- langkah 4 : Selesai
Metode INSERTION SORT (Sisip)
1) Algoritma ini dianalogikan seperti mengurutkan kartu, selembar demi selembar kartu diambil dan disisipkan (insert) ke tempat yang seharusnya.
2) Pengurutan dimulai dari data ke-2 sampai dengan data terakhir, jika ditemukan data yang lebih kecil, maka akan ditempatkan (diinsert) diposisi yang seharusnya.
3) Pada penyisipan elemen, maka elemen-elemen lain akan bergeser ke belakang
Analogi :
- mengurutkan satu set kartu dari kartu yang bernilai paling kecil hingga yang paling besar.
- Seluruh kartu diletakkan pada meja, kita sebut meja pertama, disusun dari kiri ke kanan dan atas ke bawah.
- Kemudian pada meja kedua tempat meletakkan kartu yang diurutkan.
- Ambil kartu pertama yang terletak pada pojok kiri atas meja pertama dan letakkan pada meja kedua.
- Ambil kartu kedua dari meja pertama, bandingkan dengan kartu yang berada pada meja kedua, kemudian letakkan pada urutan yang sesuai setelah perbandingan.
- Proses tersebut akan berlangsung hingga seluruh kartu pada meja pertama telah diletakkan berurutan pada meja kedua.
Materi ini kudapat dari kelompok 3
