PENGURUTAN

1 PENGANTAR
             Pengurutan data (sorting) secara umum bisa didefinisikan sebagai suatu proses untuk menyusun kembali himpunan obyek menggunakan aturan tertentu. Secara umum ada dua jenis pengurutan data, yaitu pengurutan secara urut naik (ascending), yaitu dari data yang nilainya paling kecil sampai data yang nilainya paling besar; dan pengurutan secara urut turun (descending), yaitu dari data yang mempunyai nilai paling besar sampai paling kecil.

2 METODA PENGURUTAN DATA
             Dalam melakukan pengurutan data perlu diperhatikan nilai efisiensinya, ukuran efisiensi yang baik diperoleh dari banyaknya pembandingan dan perpindahan yang harus dilakukan. Terdapat beberapa metoda yang disebut dengan metoda langsung (straight method), yang seluruhnya memerlukan N2 pembandingan (N adalah banyaknya elemen yang akan diurutkan). Metoda langsung ini bisa dikelompokkan menjadi tiga metoda, yaitu penyisipan (insertion), seleksi (selection), dan penukaran (exchange).

2.1 Metoda Gelembung (Bubble Sort)
             Metoda gelembung (Bubble Sort), sering juga disebut dengan metoda penukaran (Exchange Sort), adalah metoda yang mendasarkan penukaran dua buah elemen untuk mencapai keadaan urut yang diinginkan.
             Metoda ini cukup mudah untu dipahami dan diprogram, tetapi dari beberapa metoda yang ada metoda ini yang paling tidak efisien. Alasannya adalah apabila mengurutkan vektor sebanyak N elemen dan pada iterasi yang kurang dari N – 1, maka iterasi tersebut harus tetap dilaksanakan sampai N – 1. Dengan demikian, dalam metoda gelembung akan terjadi pembandingan dan pemindahan atau penukaran dua elemen sebanyak :
         C = ( N2 – N ) / 2

Untuk membawa vektor menjadi dalam keadaan urut bisa dilakukan dengan dua cara, yaitu :
1. Selalu meletakkan elemen dengan nilai paling besar pada posisi terakhir (posisi ke N). Kemudian elemen         dengan nilai paling besar kedua diletakkan pada posisi ke N – 1, dan seterusnya.
2. Selalu meletakkan elemen dengan nilai paling kecil pada posisi 1. Kemudian elemen dengan nilai paling           besar kedua diletakkan pada posisi ke 2, dan seterusnya.

Berikut disajikan Algoritma gelembung :
Algoritma GELEMBUNG
Langkah 0     Baca vektor yang akan diurutkan.
Langkah 1     Kerjakan langkah 2 untuk I = 1 sampai N – 1.
Langkah 2     Kerjakan langkah 3 untuk J = 1 sampai N – I.
Langkah 3     Test : apakah A [ J ] > A [ J + 1 ] ?
                      Jika ya, tukarkan nilai kedua elemen ini.
Langkah 4     Selesai.

2.2 Metoda Seleksi ( Selection Sort)
             Cara kerja metoda seleksi didasarkan pada pencarian elemen dengan nilai terkecil, kemudian dilakukan penukaran dengan elemen ke I. Secara singkat, metode ini bisa dijelaskan sebagai berikut :
      1. Dicari data yang terkecil dari data pertama sampai data terakhir. Data terkecil tersebut ditukarkan          dengan data pertama. (data pertama sekarang mempunyai nilai terkecil).
      2. Data terkecil kedua dicari mulai dari data kedua sampai data terakhir. Data terkecil yang diperoleh          ditukar dengan data kedua.
      3. Demikian seterusnya sampai seluruh vektor dalam keadaan urut.

2.3 Metoda Penyisipan (Insertion Sort)
      Metoda penyisipan (insertion), banyak digunakan oleh pemain kartu dengan menggunakan metoda penyisipan pada sebuah vektor dengan 9 buah elemen.