Macam - macam Teknik Pengurutan (Sorting)



Nama : Ian Widiasmara Levi
NPM : 55414044
Kelas : 1IA17
Mata Kuliah : Algoritma dan Pemrograman 1A
Dosen : Kunto Bayu A, ST.


1. Metode Sorting

Sorting  bisa didefinisikan sebagai suatu proses pengurutan data yang sebelumnya disusun secara acak sehingga menjadi tersusun secara teratur menurut suatu aturan tertentu. Sorting yang kita terapkan menggunakan tipe data array agar pemahaman serta pengimplementasiannya lebih mudah. Pada umumnya terdapat dua jenis pengurutan :
-   Ascending (Naik).

-   Descending (Turun).



Contoh :

Data                            :        Array [1..6] of Byte = (22, 10, 15, 3, 8, 2);

Data Acak                   :
22
10
15
3
8
2
Terurut Ascending      :
2
3
8
10
15
22
Terurut Descending    :
22
15
10
8
3
2


Untuk melakukan proses pengurutan tersebut dapat digunakan berbagai macam cara/metode.



Beberapa metode yang sudah umum digunakan diantaranya adalah :

1.    Bubble / Exchange Sort

2.    Selection Sort.

3.    Shell Sort.

4.    Quick Sort.
Metode Pengurutan Data

l     Pengurutan berdasarkan perbandingan (comparison-based sorting)

• Bubble sort, exchange sort

l     Pengurutan berdasarkan prioritas (priority queue sorting method)

• Selection sort, heap sort

l     Pengurutan berdasarkan penyisipan dan penjagaan terurut (insert and  keep sorted method)

• Insertion sort, tree sort

l     Pengurutan berdasarkan pembagian dan penguasaan (devide and conquer method)

• Quick sort, merge sort

l     Pengurutan berkurang menurun (diminishing increment sort method)

• Shell sort



2. Bubble/Exchange Sort

Metode ini merupakan metode yang paling sederhana dan paling tidak efisien, karena memerlukan waktu yang relatif lebih lama dibandingkan dengan metode-metode yang lainnya. Konsep dasar dari Bubble sort ialah membandingkan elemen yang sekarang degan elemen yang berikutnya, jika elemen sekarang > elemen berikutnya (untuk ascending), maka dilakukan proses penukaran. Proses sorting dapat dimulai dari data awal atau data akhir. Contoh dari proses Sorting dengan menggunakan metode Bubble Sort :


Iterasi

Ke

A[1]

A[2]

A[3]

A[4]

A[5]

A[6]
Awal
22
10
15
3
2
8
1
10
22
15
3
2
8

10
15
22
3
2
8

10
15
3
22
2
8

10
15
3
2
22
8

10
15
3
2
8
22
2
10
15
3
2
8
22

10
3
15
2
8
22

10
3
2
15
8
22

10
3
2
8
15
22

10
3
2
8
15
22
3
3
10
2
8
15
22

3
2
10
8
15
22


3
2
8
10
15
22

3
2
8
10
15
22

3
2
8
10
15
22
4
2
3
8
10
15
22

2
3
8
10
15
22

2
3
8
10
15
22

2
3
8
10
15
22

2
3
8
10
15
22
5
2
3
8
10
15
22

2
3
8
10
15
22

2
3
8
10
15
22

2
3
8
10
15
22

2
3
8
10
15
22
Akhir
2
3
8
10
15
22




Disini terlihat ketidak efisienan dari bubble sort yaitu harus menyelesaikan JumMax –1 dari data. Sedangkan jika kita melihat dari tabel diatas pada iterasi ke empat saja data sudah terurut dan seharusnya pada saat itu proses sudah berhenti, tapi dengan bubble sort proses harus dilakukan sampai looping selesai.





3. Selection Sort

Cara kerja metode ini didasarkan pada pencarian elemen dengan nilai terkecil, kemudian dilakukan  penukaran  dengan  elemen  ke-I.  Secara  singkat,  metode  ini  bisa  dijelaskan  sebagai berikut. Pada langkah pertama, dicari data yang terkecil dari data pertama sampai data terakhir. Kemudian data tersebut kita tukar dengan data pertama. Dengan demikian, data pertama sekarang mempunyai nilai paling kecil dibanding data lain. Pada langkah kedua, data terkecil kita cari mulai dari data kedua sampai data terakhir. Data terkecil yang kita peroleh kita tukar dengan data kedua. Demikian seterusnya sampai suluruh data terurut.
Contoh dari proses Sorting dengan menggunakan metode Selection Sort :

Iterasi Ke
A[1]
A[2]
A[3]
A[4]
A[5]
A[6]
Awal
22
10
15
3
2
8







I=1, Lok=5
2
10
15
3
22
8







I=2, Lok=4
2
3
15
10
22
8







I=3, Lok=6
2
3
8
10
22
15







I=4, Lok=4
2
3
8
10
22
15







I=5, Lok=6
2
3
8
10
15
22







Akhir
2
3
8
10
15
22







 


4. Shell Sort

Metode ini dikembangkan oleh Donald L. Shell pada tahun 1959. Dalam   metode ini jarak antara dua elemen yang dibandingkan dan ditukarkan tertentu. Secara singkat metode ini dijelaskan sebagai berikut. Pada langkah pertama, kita ambil elemen pertama dan kita bandingkan dengan elemen pada jarak tertentu dari elemen pertama tersebut. Kemudian elemen kedua kita bandingkan dengan elemen lain dengan jarak yang sama seperti diatas. Demikian seterusnya sampai seluruh elemen dibandingkan. Pada langkah kedua proses diulang dengan langkah yang lebih kecil, pada langkah ketiga jarak tersebut diperkecil lagi seluruh proses dihentikan jika jarak sudah sama dengan satu.

Contoh dari proses Sorting dengan menggunakan metode Selection Sort :

Jarak
A[1]
A[2]
A[3]
A[4]
A[5]
A[6]
Awal
22
10
15
3
2
8
Jarak = 3
22
10
15
3
2
8

3
10
15
22
2
8

3
2
15
22
10
8

3
2
8
22
10
15
Jarak = 1
3
2
8
22
10
15

2
3
8
22
10
15

2
3
8
22
10
15

2
3
8
22
10
15

2
3
8
10
22
15

2
3
8
10
15
22
Akhir
2
3
8
10
15
22

 


 


5. Quick Sort

Metode ini dikembangkan oleh C.A.R Hoare. Secara garis besar metode ini dijelaskan sebagai berikut. Misalnya kita ingin mengurutkan data A yang mempunyai N elemen. Kita pilih sembarang elemen dari data tersebut, bisanya elemen pertama, misalnya X. kemudian semua elemen tersebut disusun dengan menempatkan X pada posisi J sedemikian rupa sehingga elemen ke 1 sampai ke J-1 mempunyai nilai lebih kecil dari X dan elemen J+1 sampai ke N mempunyai nilai lebih besar dari X. Sampai saat ini kita sudah mempunyai dua sub data (kiri dan kanan). Langkah berikutnya diulang untuk setiap sub data.   

 




Sumber  :http://ilab.gunadarma.ac.id/modul/NewPTA2011-2012/Struktur%20Data/m7.pdf

Komentar

Posting Komentar

Postingan populer dari blog ini

Penerapan New Media ke dalam Internet

New media adalah hasil pengembangan serta penggabungan dari media tradisional dengan kekuatan teknologi dan menghasilkan sebuah media baru yang lebih canggih serta fungsinya mempermudah orang lain berkomunikasi dan mengenal dunia dimana saja kapan saja.    Media tradisional C ontohnya adalah film, gambar, musik yang kemudian dikembangkan menjadi menjadi internet, handphone, website, komputer multimedia, permainan komputer, CD-ROM, DVD, dll.  Dahulu seseorang berkomunikasi melalui media surat yang dikirim melalui kantor pos dan membutuhkan waktu lama untuk sampai kepada penerima. Namun sekarang seseorang dapat menyampaikan berita ataupun memberi kabar dengan menggunakan email yang hanya sekejap bisa sampai kepada penerima, tidak membutuhkan waktu banyak. Atau ada juga media chatting dengan webcam yang memungkinkan kita berkomunikasi dengan seseorang dengan melihat langsung serta mendengar langsung suaranya layaknya sedang berkomunikasi langsung.  ...
more »

Pengertian dan Pengantar Internet

1.    Pengertian Internet Internet merupakan singkatan dariInterconnection Networking, yaitu sebuah sistem global jaringan komputer yang saling menghubungkan antara satu dengan yang lain di seluruh penjuru dunia. Seluruh jaringan komputer yang saling terhubung menggunakan standar sistem global Transmission Control Protocol/Internet Protocol Suite (TCP/IP) sebagai protokol pertukaran paket (packet switching communication protocol) untuk melayani miliaran pengguna di seluruh dunia. Secara harfiah, Internet berasal dari tiga kata, yaitu inter, connection, dan networking. Inter merupakan singkatan dari international, Connection  mempunyai arti ‘hubungan’, dan Networking berarti ‘jaringan’. Jadi dapat disimpulkan Pengertian Internet adalah teknologi yang menghubungkan beberapa komputer atau beberapa jaringan komputer diseluruh dunia untuk berkomunikasi tanpa batasan ruang dan waktu. Jumlah jaringan komputer yang membentuk Internet sang...
more »

Penggunaan dan Pemanfaatan Internet

Untuk mengakses Internet, kita dapat memakai dua bentuk akses Internet yang umum, yaitu dial-up, dan jalurlebar. Di Indonesia, seperti negara berkembang dimana akses Internet dan penetrasi PC sudah cukup tinggi dengan di dukungnya Internet murah dan netbook murah, hanya saja di Indonesia operator kurang fair dalam menentukan harga dan bahkan ada salah satu operator yang sengaja membuat "perangkap jebakan" agar supaya si pengguna Internet bayar lebih mahal sampai ber juta-juta rupiah. Contoh tempat untuk mengakses internet seperti di warnet , cybercafe, hotspot dll. Tempat umum lainnya yang sering dipakai untuk akses Internet adalah di kampus dan di kantor. Disamping menggunakan PC (Personal Computer), kita juga dapat mengakses Internet melalui Handphone (HP) menggunakan Fasilitas yang disebut GPRS (General Packet Radio Service). GPRS merupakan salah satu standar komunikasi wireless (nirkabel) yang memiliki kecepatan koneksi 115 kbps dan mendukung aplikasi yang lebih ...
more »