tugas struktur data

PENGURUTAN ARRAY

a.    Maximum/minimum sort

Gagasan maksimum/minimum adalah memilih elemen maksimum/minimum kemudian mempertukarkan elemen maksimum/minimum tersebut dengan elemen terujung larik (elemen ujung kiri atau elemen ujung kanan). Selanjutnya elemen terujung tersebut “diisolasi” dan tidak disertakan pada proses selanjutnya. Proses yang sama diulang untuk elemen larik yang tersisa, yaitu memilih elemen maksimum/minimum berikutnya dan mempertukarkannya dengan elemen terujung larik sisa.

Elemen array dengan niali maximum/minimum akan disimpan kebagian ujung array ( elemen pertama dan terakhir ). Selanjutnya nilai tersebut akan diisolasi atau diikat dan diikutkan lagi dalam proses selanjutnya.

b.    Selection sort

Pengurutan dengan metode selection ini bekerja dengan cara pemilihan salah satu elemen serta menganggapnya sebagai nilai terkecil. Kemudian nilai tersebut akan dibandingkan dengan elemen- elemen pada posisi berikutnya. Apabila nilai yang dipilih pertama kali lebih besar dari nilai elemen pembanding maka tukarkan kedua buah nilai tersebut.

Membandingkan elemen yang sekarang dengan elemen yang berikutnya sampai dengan elemen yang terakhir. Jika ditemukan elemen lain yang lebih kecil dari elemen sekarang maka dicatat posisinya dan kemudian ditukar. Dan begitu seterusnya.

c.    Bubble sort ( gelembung )

Metode pengurutan gelembung diinspirasikan oleh gelembung sabun yang berada dipermukaan air. Karena berat jenis gelembung sabun lebih ringan daripada berat jenis air, maka gelembung sabun selalu terapung ke atas permukaan.

Prinsip di atas dipakai pada pengurutan gelembung. Elemen larik yang berharga paling kecil “diapungkan”, artinya diangkat ke atas (ke ujung kiri larik) melalui proses pertukaran. Proses pengapungan terdiri dari N-1 langkah. Setiap akhir langkah ke-I, larik L[1..N] akan terdiri atas dua bagian, yaitu bagian yang sudah terurut, L[1..I] dan bagian yang belum terurut, L[I+1..N]. Langkah terakhir, diperoleh larik L[1..N] yang sudah terurut.

Dalam pengurutan ini data dengan nilai terkecil akan diapungkan keposisi teratas, dan sebaliknya data dengan nilai terbesar akan berada pada posisi terbawah.

d.    Pengurutan Sisip (Insertion Sort)

Pengurutan sisip adalah metode pengurutan dengan cara menyisipkan elemen larik pada posisi yang tepat. Pencarian posisi yang tepat dilakukan dengan melakukan pencarian beruntun di dalam larik. Selama pencarian posisi yang tepat dilakukan pergeseran elemen larik.

Pengurutan dilakukan dengan cara membandingkan data ke-I (dimana I dimulai dari data ke-2 sampai dengan data terakhir) dengan data berikutnya. Jika ditemukan data yang lebih kecil maka data tersebut  disisipkan ke depan sesuai posisi yang seharusnya.

e.    Pengurutan Gravitasi

Pengurutan gravitasi sebagai kebalikan dari pengurutan gelembung, yaitu “membenamkan” elemen larik yang berharga paling besar ke bawah, jadi proses “pemberatan” selalui dimulai dari “atas” ke “bawah”.

f.     Quick sort

Membandingkan suatu elemen (disebut pivot) dengan elemen yang lain dan menyusunnya sedemikian rupa sehingga elemen- elemen lain yang lebih kecil daripada pivot tersebut terletak di sebelah kirinya dan elemen-elemen lain yang lebih besar daripada pivot tersebut terletak di sebelah kanannya. Sehingga dengan demikian telah terbntuk dua sublist, yang terletak di sebelah kiri dan kanan dari pivot. Lalu pada sublist kiri dan sublist kanan kita anggap sebuah list baru dan kita kerjakan proses yang sama seperti sebelumnya. Demikian seterusnya sampai tidak terdapat sublist lagi. Sehingga didalamnya telah terjadi proses Rekursif