Pemograman SORTING (PENGURUTAN)

SORTING (PENGURUTAN).

     Sorting adalah proses mengatur sekumpulan objek menurut aturan atau susunan tertentu. Pengurutan dapat dilakukan secara ascending (urut naik = dari data kecil ke data lebih besar) dan descending (urut turun = dari data besar ke data lebih kecil) Banyak sekali algoritma pengurutan yang ada, tetapi disini akan kita pelajari 3 metode yaitu:

• Pengurutan Gelembung (bubble sort).
• Maksimum/Minimum (maksimum/minimum sort).
• Pengurutan sisip (insertion Sort).

Contoh: 

• Ascending : 1 3 5 6 8 10 25.
• Descending : 25 10 8 6 5 3 1.
• Data Acak : 5 6 8 1 3 25 10.

I. PENGURUTAN GELEMBUNG (BUBLE SORT).

    Metode pengurutan gelembung (bubble sort) diinspirasi oleh gelembung sabun yang ada di permukaan air. Karena berat jenis gelembung sabun lebih ringan daripada berat jenis air maka gelembung sabun akan selalu mengapung. Prinsip pengapungan ini juga dipakai pada pengurutan gelembung. Elemen yang berharga paling kecil “diapungkan”, artinya diangkat ke atas (atau ke ujung paling kiri) melalui pertukaran. Proses pengapungan ini dilakukan N kali langkah. Pada langkah ke-I, Larik[1..N] akan terdiri dari 2 bagian yaitu:

• Bagian yang sudah terurut yaitu L[1]..L[i].
• Bagian yang belum terurut L[i+1]..L[n].

Aturan buble sort(gelembung).

• mengurutkan data dengan cara membandingkan elemen sekarang dengan elemen berikutnya.
• Jika elemen sekarang lebih besar dari elemen berikutnya maka kedua elemen tersebut ditukar, jika pengurutan ascending.
• Jika elemen sekarang lebih kecil dari elemen berikutnya, maka kedua elemen tersebut ditukar, jika pengurutan descending.
• Bubble sort berhenti jika seluruh array telah diperiksa dan tidak ada pertukaran lagi yang bisa dilakukan.

Contoh : Apabila di dalam array dipunyai 6 buah data yang belum terurut yaitu 22, 10, 15, 3, 8, 2. Langkah pengurutan menggunakan metode Bubble Sort adalah sebagai berikut : 

Proses 1 

Proses 2

                                                   

Pada proses kedua, pengecekan dilakukan sampai dengan data ke-2 karena data pertama pasti sudah paling kecil.

Proses 3

                                

Proses 4

                                   

 Proses 5

                                      

II. SELECTION SORT(MAKSIMUM/MINIMUM)

Metode seleksi melakukan pengurutan dengan cara mencari data yang terkecil /terbesar untuk kemudian menukarkannya dengan data yang digunakan sebagai acuan atau sering dinamakan pivot.

Terdapat dua pendekatan dalam metode pengurutan dengan Selection Sort :

1. Algoritma pengurutan maksimum (maximum selection sort), yaitu memilih elemen maksimum sebagai basis pengurutan.
2. Algoritma pengurutan minimum (minimum selection sort), yaitu memilih elemen minimum sebagai basis pengurutan. 

Contoh : Tinjau larik dengan N=6 buah elemen dibawah ini yang belum terurut menjadi diurut naik.

Langkah 1: Cari elemen maksimum di dalam larik L[1..6] maks = L[5] = 76 Tukar maks dengan L[N],hasil akhir langkah 1:

Langkah 2: (berdasarkan susunan larik hasil langkah 1) Cari elemen maksimum di dalam larik L[1..5] maks = L[1] = 29 Tukar maks dengan L[5],hasil akhir langkah 2:

Langkah 3: (berdasarkan susunan larik hasil langkah 2) Cari elemen maksimum di dalam larik L[1..4] maks = L[2] = 27 Tukar maks dengan L[4],hasil akhir langkah 3: 

Langkah 4: (berdasarkan susunan larik hasil langkah 3) Cari elemen maksimum di dalam larik L[1..3] maks = L[1] = 21 Tukar maks dengan L[3],hasil akhir langkah 4: 

Langkah 5: 9 (berdasarkan susunan larik hasil langkah 4) Cari elemen maksimum di dalam larik L[1..2] maks = L[1] = 10 Tukar maks dengan L[2],hasil akhir langkah 5:

Selesai. Larik sudah terurutkan !