Tugas Pendahuluan Pertemuan 9 SORTING (Lanjut 2)

PERTEMUAN   IX

SORTING (Lanjut 2)

TUGAS PENDAHULUAN

1.      1. Jelaskan kekurangan menggunakan metode shell sort dan insertion sort dengan metode –metode sorting lainnya!

2.      2. Jelaskan perbedaan program sorting dengan menggunakan antara metode shell sort dan insertion sort!

3.      3. Jelaskan tahapan-tahapan sorting menggunakan metode shell sort!

4.      4. Jelaskan tahapan-tahapan sorting menggunakan metode insertion sort!

Jawaban

1.      1. Kekurangan metode shell sort yaitu:

-          Membutuhkan method tambahan.

-          Sulit untuk membagi masalah.

Kekurangan metode insertion sort yaitu:

-          Banyaknya operasi yang diperlukan dalam mencari posisi yang tepat untuk elemen larik.

-          Untuk larik yang jumlahnya besar ini tidak praktis.

-          Jika list terurut terbalik sehingga setiap eksekusi dari perintah harus memindai dan mengganti seluruh bagian sebelum menyisipkan elemen berikutnya.

-          Membutuhkan waktu 0(n2) pada data yang tidak terurut, sehingga tidak cocok dalam pengurutan elemen dalam jumlah besar.

2.      2. a. Shell sort

metode pengurutan yang hampir sama dengan insertion sort, dimana pada setiap nilai i dalam n/i item diurutkan. Pada setiap pergantian nilai, i dikurangi sampai 1 sebagai nilai terakhir.

     b. insertion sort

salah satu metode sorting dengan cara menyisipkan/insert. Pada dasarnya insertion sort memilih data yang akan diurutkan menjadi dua bagian, yang belum diurutkan dan yang sudah diurutkan.

3.      3. Tahapan-tahapan sorting menggunakan metode shell sort.

Pertama-tama adalah menentukan jarak mula-mula dari data yang akan dibandingkan, yaitu N/2. Data pertama dibandingkan dengan data dengan jarak N/2. Apabila data pertama lebih besar dari data ke N/2 tersebut makna kedua data tersebut ditukar. Kemudian data kedua dibandingkan dengan jarak yang sama yaitu N/2. Demikian seterusnya sampai seluruh data dibandingkan sehinga semua data ke-j selalu lebih kecil daripada data ke-(j+N/2).

Pada proses berikutnya, digunakan jarak (N/2)/2 atau N/4. Data pertama dibandingkan dengan data dengan jarak N/4. Apabila data pertama lebih besar dari data ke N/4 tersebut maka kedua data tersebut ditukar. Kemudian data kedua dibandingkan dengan jarak yang sama yaitu N/4. Demikianlah seterusnya hingga seluruh data dibandingkan sehingga semua data ke-j lebih kecil daripada data ke-(j+N/4).

Pada proses berikutnya, digunakan jarak (N/4)/2 atau N/8, demikian seterusnya sampai jarak yang digunakan adalah 1.

4.      4. Tahapan-tahapan sorting menggunakan metode insertion sort.

Dalam pengurutan datanya. Jika data sudah ada, maka pengurutan dimulai dengan mengambil satu data dan membandingkannya dengan data-data yang ada didepannya. Jika data yang diambil memenuhi syarat perbandingan, maka data yang diambil tersebut akan diletakkan didepan data yang dibandingkan, kemudian data-data yang dibandingkan akan bergeser mundur.

Catatan: Dalam hal pengurutan data dengan metode insertion sort ini, data yang diambil akan dibandingkan dengan data-data yang ada disebelah kiri/data sebelumnya (data-data sebelum data yang diambil). Jika proses tersebut selesai, maka akan dilanjutkan dengan data-data selanjutnya (data ke-3, data ke-4,... dan seterusnya). Proses akan berlangsung sampai data-data terurutkan dengan benar.