Twitter
FacebookSorting
Dalam aktivitas sehari-hari kita sering dihadapkan pada perlunya melakukan sorting (pengurutan). Mahasiswa diabsen (call) berdasarkan Nimnya. Mahasiswa ujian di lab berdasarkan NIM, dsb.
Pengurutan biasanya dilakukan untuk tujuan mempermudah pencarian, misalnya mencari nomor telepon, dibuku telepon, mengetahui grade mahasiswa dan sebagainya.
Proses Sorting
Sewaktu seseorang memasukkan data ke komputer, tumpukan berkas yang ada sangat jarang di urutkan terlebih dahulu. Mungkin karena alasan akan memakan waktu atau sulit melakukan secara manual, atau bahkan tidak mungkin dilakukan. Bagaimana mungkin kita dapat memasukkan data secara urut (misalkan urut nama) pada saat proses pendaftaran mahasiswa baru masih berlangsung. Karenanya untuk mempermudah dan mempercepat proses pengurutan, programer akan melakukannya secara programming saja.
Pertimbangan ketika akan melakukan sorting
Ketika akan melakukan pengurutan data di komputer, maka hal-hal yang akan dipertimbangkan meliputi:
1. Perlu tidaknya data di sorting
2. Besarnya atau banyaknya data yang akan di urutkan
3. Kemampuan atau kapasitas komputer atau media penyimpanan data.
4. Metode pengurutan
Fasilitas Sorting di Bahasa Pemrograman
Para pengguna komputer memang sudah banyak dimanjakan oleh fasilitas yang diberikan oleh bahasa pemrograman atau software application yang digunakan, terutama untuk bahasa pemrograman yang telah dirancang untuk kebutuhan tertentu (paket program). Di bahasa pemrograman dBase, FoxPro dan sejenisnya untuk melakukan pengurutan data tinggal menulis perintah SORT atau INDEX saja. Maka urusan pengurutan sudah selesai dikerjakan, tanpa perlu mengetahui bagaimana komputer bekerja atau menggunakan teknik bagaimana pengurutan terhadap data dilakukannya.
Namun demikian, untuk bahasa pemrograman yang generik sifatnya, untuk mengurutkan data, Anda perlu membuat programnya sendiri dan sudah barang tentu harus memikirkan teknik seperti apa untuk melakukan pengurutan.
Teknik-teknik Sorting
Pada garis besarnya, ada tiga teknik sorting yaitu:
1. Insertion sort (Sorting penyisipan)
2. Selection Sort (Sorting Pemilihan)
3. Exchange Sort (Sorting Penukaran)
Teknik sorting sangat erat kaitannya dengan proses pembandingan dan penukaran tempat antar elemen data. Kita tidak dapat menentukan dengan pasti, mana dari ketiga teknik sorting tersebut yang merupakan teknik terbaik (melakukan perbandingan dan penukaran tempat antar elemen data yang paling sedikit). Banyaknya proses perbandingan dan penukaran tempat antar elemen data tersebut juga terkait dengan susunan elemen-elemen datanya.
Sehingga kecepatan dalam melakukan sorting juga ditentukan atas tiga kondisi susunan elemen-elemen datanya. Waktu terbaik akan diperoleh ketika susunan elemen-elemen datanya sudah sama dengan susunan yang diinginkan melalui pengurutannya. Waktu terburuk akan didapatkan ketika susunan elemen-elemen datanya terbalik dari susunan yang dikehendaki. Waktu rata-rata diperoleh dengan memperhitungkan berbagai susunan bentuk elemen-elemen datanya.
Insertion Sort
Teknik ini adalah dengan membandingkan elemen ke-n (n mulai dari 2 hingga elemen terakhir) dengan elemen-elemen sebelumnya. Bila elemen yang dibandingkan bernilai lebih kecil, maka tukar posisinya.
Contoh: 8, 3, 7, 4
Pada langkah pertama, elemen ke dua akan dibandingkan dengan elemen pertama, 3 dibandingkan dengan 8, maka kedua elemen tersebut saling ditukar tempatnya yang menghasilkan urutan 3, 8, 7, 4 (dua elemen pertama sudah urut).
Pada langkah kedua, elemen ke tiga akan dibandingkan dengan elemen ke dua, 7 dibandingkan dengan 8, terjadi penukaran tempat yang menghasilkan urutan 3, 7, 8, 4.
Selanjutnya, 7 tersebut dibandingkan dengan elemen pertama, yaitu 3. Tidak terjadi penukaran tempat karena 3 memang lebih kecil dari 7 (tiga elemen pertama sudah urut)
Pada langkah ketiga elemen keempat, yaitu 4 dibandingkan dengan elemen ketiga. Angka 4 lebih kecil dari 8, terjadi penukaran tempat, hasil sementara adalah 3, 7, 4, 8. Angka 4 tadi dibandingkan dengan elemen kedua, 4 lebih kecil dari 7, terjadi penukaran tempat, hasil sementara adalah 3, 4, 7, 8. Selanjutnya angka 4 dibandingkan dengan elemen pertama, yaitu 3. Karena 4 lebih besar dari tiga maka tidak terjadi penukaran tempat.
Jadi empat elemen pertama sudah urut = hasil akhir
Sub-sub langkah ketiga : 3, 7, 8, 4 (awal) -> 4 banding 8, tukar
Hasilnya : 3, 7, 4, 8 -> 4 banding 7, tukar
Hasilnya : 3, 4, 7, 8 -> 4 banding 3, tetap
Hasilnya : 3, 4, 7, 8 (akhir)
Selection Sort
Teknik ini adalah mencari nilai elemen terkecil kemudian letakan dan tukar dengan posisi ke-n (n mulai dari 1 hingga elemen terakhir).
Contoh : 8, 3, 7, 4
Pada langkah pertama, hasil sortirnya 3, 8, 7, 4 (mulai dari elemen pertama, elemen terkecil = 3, letakkan dan tukar dengan elemen pertama.
Pada langkah kedua, hasil sortirnya 3, 4, 7, 8 (mulai dari elemen kedua, elemen terkecil = 4, letakkan dan tukarkan dengan elemen kedua).
Pada langkah ketiga, hasil sortirnya 3, 4, 7, 8 (mulai dari elemen ketiga, elemen terkecil =7, letakkan dan tukarkan dengan elemen ketiga, hasilnya tetap.
Exchange Sort
Contoh umum yang menggambarkan exchange sort adalah bubble sort. Algoritma dari teknik ini adalah dengan melakukan proses perbandingan sebanyak n elemen dimulai dari n=1 (selanjutnya disebut mulai = 1). Bandingkan seluruh elemen di awali dengan elemen sebelah kanan hingga ke-n. bila elemen tersebut < dari mulai, maka lakukan pertukaran tempat. Lakukan pada elemen mulai + 1 seperti proses sebelumnya hingga mulai + 1 = n
Contoh data awal 8, 7, 6, 5, 4
Pass 1 Proses 1, bandingkan 8 (elemen pertama) dengan 7 (elemen kedua)
hasilnya : 7, 8, 6, 5, 4
Proses 2, bandingkan 7 (elemen pertama) dengan 6 (elemen ketiga)
hasilnya : 6, 8, 7, 5, 4
Proses 3, bandingkan 6 (elemen pertama) dengan 5 (elemen keempat)
hasilnya : 5, 8, 7, 6, 4
Proses 4, bandingkan 5 (elemen pertama) dengan 4 (elemen kelima)
hasilnya : 4, 8, 7, 6, 5 (urutan pass 1 telah diperoleh)
Pass 2 dimulai dengan elemen kedua, bandingkan dengan elemen 3 hingga elemen ke 5
Proses 1 menghasilkan : 4, 7, 8, 6, 5
Proses 2 menghasilkan : 4, 6, 8, 7, 5
Proses 3 menghasilkan : 4, 5, 8, 7, 6 (urutan pass 2 telah diperoleh)
Pass 3 dimulai dengan elemen ketiga, bandingkan dengan elemen 4 hingga elemen ke 5
Proses 1 menghasilkan : 4, 5, 7, 8, 6
Proses 2 menghasilkan : 4, 5, 6, 8, 7 (urutan pass 3 telah diperoleh)
Pass 4 dimulai dengan elemen keempat, bandingkan dengan elemen 5
Proses 1 menghasilkan : 4, 5, 6, 7, 8 (urutan ke 4 dan ke 5 telah diperoleh)
sumber gratiaweb.com/elearning
Please Click This Link Below to Subscribe Ledakan Lemon
SUBSCRIBE
CTRL+D to Bookmark This Page
Click Follow Button on The Left-Top Corner of this page or one on the Right Sidebar to Follow this Blog. Thank You
0 komentar: (+add yours?)
Posting Komentar