sorting

TUGAS PERSENTASE1. BENI NOVIANTO 08 411 188

2. MARATUNAVINGAH 08 411 193

3. LUKMAN 08 411 206

4. FADLY RAIS. W 08 411 180

5. MUHAMMAD IKBAL. T 08 411 039

6. BUMIN. N. NASIR 08 411 115

7. ISTAMON SURBAKTI 08 411 208

8. GANANG ADY. P 08 411 190

9. RANDI SAPUTRA 08 411 194

10. NOVIJANTI A.R.TEMALURU 08 411 209

11. SEPRIANI. A. BATUBARA 08 411 158

12. JUAN S. UNIPLAITA 08 411 118

13. FERDY TANADI 08 411 156

14. BARKAH SAFARA 08 411 016

15. IGNASIUS HILIR 08 411 142

SORTING

A. PENGERTIAN

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 Acak : 22 10 15 3 8 2Terurut Ascending : 2 3 8 10 15 22Terurut Descending : 22 15 10 8 3 2`

B. METODE SORTING

Beberapa metode yang sudah umum digunakan diantaranya adalah :1. Bubble / Exchange Sort2. Selection Sort.3. Insertion Sort.4. Quick Sort.5. Heap Sort.6. Shell Sort.

1. Bubble Sort

Penguruttan Ascending jika elemen sekarang lebih besar dari elemen berikutnya maka kedua elemen tersebutt ditukar.

Penguruttan Descendiing Jiika elemen sekarang lebih kecil dari elemen berikutnya, maka kedua elemen tersebutt ditukar.

Algoritma ini seolah-olah menggeser satu per satu elemen dari kanan ke kiri atau kiri ke kanan, tergantung jenis penguruttannya.

Ketika satu proses telah selesai, maka bubblle sortt akan mengulangi proses, demikian seterusnya dari 0 sampai dengan itterasii sebanyak n-1.

Kapan berhentinya? Bubblle sortt berhenti jika seluruh array tellah diperiksa dan tidak ada pertukaran lagi yang bisa dilakukan, serta tercapai perurutan yang telah diinginkan.

Contoh :

• Diberikan data awal 22 10 15 3 8 2

• Proses 1

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

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

Proses 4

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

Hasil : 2 3 8 10 15 22

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

Proses 5 2 3 8 10 22 15

2 3 8 10 15 22

2. Selection Sort

Definisi• Merupakan kombinasi antara sorting dan searching• Misalnya untuk putaran pertama, akan dicari data

dengan nilai terkecil dan data ini akan ditempatkan pada index terkecil (Data[0]), pada putaran kedua akan dicari data kedua terkecil dan akan ditempatkan pada index kedua terkecil (data[1]).

• Selama proses, perbandingan dan pengubahan hanya dilakukan pada index pembanding saja, pertukaran data secara fisik terjadi pada akhir proses

Contoh :

Proses

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

Hasil : 2 3 8 10 15 22

• Diberikan data awal 22 10 15 3 8 2

3. Insertion Sort

Definisi :• Mirip dengan cara orang mengurutkan kartu,

selembar demi selembar kartu diambil dan disisipkan (insert) ke tempat yang seharusnya.

• Pengurutan dimulai dari data ke-2 sampai dengan data terakhir, jika ditemukan data yang lebih kecil, maka akan ditempatkan (diinsert) diposisi yang seharusnya.

• Pada penyisipan elemen, maka elemen-elemen lain akan bergeser ke belakang

Contoh :

• Diberikan data awal 22 10 15 3 8 2

Proses

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

Hasil : 2 3 8 10 15 22

4. Quick SortDefinisi :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 (kiridan kanan). Langkah berikutnya diulang untuk setiap sub data.

Contoh :

5. Heap Sort

Definisi :

• Salah satu teknik sortir yang memanfaatkan bentuk pohon binary.

• Maxheap adalah penyortiran dari besar ke kecil.

• Minheap adalah penyortian dari kecil ke besar.

Penulisan hasil sortir mengikuti langkah –langkah penghapusan hasil elemen sebagai berikut :

1.Hapus akar (root)2.Letakkan elemen data terakhir di posisi

akarnya3.Lakukan tindakan atas elemen data tersebut

seperi proses 14.Lakukan langkah 1 hingga pohon menjadi

kosong.

Max Heap

Contoh :

22 10 15 3 8 2

22

Proses 1 Proses 2

22

10

Proses 3

22

10 15

Pohon Maxheap

Proses 4

22

10 15

3

Proses 5

22

10 15

3 8

Proses 6

22

10 15

3 8 2

Sorting MaxHeap

22

10 15

3 8 2

Proses Sorting

2

10 15

3 8

= {22}

Fase 1

22

10 15

3 8 2

Fase 2

15

10 2

3 8

8

10 2

3

= {22, 15}

Fase 3

10

8 2

3

3

8 2

= {22, 15, 10}

Fase 4

8

3 2

2

3

= {22, 15, 10, 8}

Fase 5

3

2

2

= {22, 15, 10, 8, 3}

Hasil = {22, 15, 10, 8, 3, 2}

Minheap

Contoh :22 10 15 3 8 2

22

Proses 1 Proses 2

10

22

Proses 3

10

22 15

Pohon Minheap

Proses 4

3

10 15

22

Proses 5

3

8 15

22 10

Proses 6

2

8 3

22 10 15

Sorting MinHeap

2

8 3

22 10 15

Proses Sorting

15

8 3

22 10

= {2}

Fase 2

3

8 3

22 10

Fase 1

2

8 3

22 10 15

10

8 15

22

= {2, 3}

Fase 3

8

10 15

22

22

10 15

= {2, 3, 8}

Fase 4

10

22 15

15

22

= {2, 3, 8,10}

Fase 5

22

= {2, 3, 8, 10, 15, 22}

Hasil = {2, 3, 8, 10, 15, 22}

6. Shell Sort

Definisi :

Sortir ini digunakan untuk jumlah data yang besar.Dengan membagi-bagi menjadi sub-sub bagian mulai dari sedikit elemen hingga keseluruhan elemen tersebut menjadi data yang sudah urut.Sortir ini digunakan bila kapasitas memori tidak sanggup untuk menampung seluruh data yang akan disortir.

Contoh :

Diberikan data :

71,60,51,45,22,10,15,3,8,2,20,18,30,32

Pass 1 : data dibagi menjadi sub-sub yang tiap subnya berisi 2 elemen, kemudian disortir, hasilnya :

60,71 45,51 10,22 3,15 2,8 18,20 30,32

Pass 2 : gabungan dua subbagian sebelumnya menjadi 1 subbagian, kemudian disortir, hasilnya:

45,51,60,71 3,15 10,22 2,8,18,20 30,32

Pass 3 : Lakukan seperti langkah 2 hingga seluruh subbagian menjadi satu bagian.

3,10,15,22,45,51,60,71 2,8,18,20,30,32

Hasil Akhir :

2,3,8,10,15,18,20,22,30,32,45,51,60,71