Pengurutan didefinisikan sebagai suatu penyusunan ulang (pengorganisasian) himpunan obyek dengan aturan tertentu. Jenis pengurutan:
- Urut naik (ascending) yaitu jika data disusun mulai dari yang paling kecil hingga yang paling besar.
- Urut turun (descending) yaitu jika data disusun mulai dari yang paling besar hingga yang paling kecil.
Keuntungan dari data yang sudah terurut adalah kemudahan dalam mencari data tertentu dan kemudahan dalam melakukan perbaikan, disisipi data baru, dihapus serta digabungkan.
1. Pengurutan dengan Penyisipan Langsung
Pseudocode:
- Mulai dari n=1
- Bilangan ke-n diambil, cari posisi penyisipan yang sesuai dengan kriteria
- Geser bilangan-bilangan mulai posisi penyisipan hingga bilangan ke-n
- Sisipkan bilangan di posisi yang sesuai
- Tambahkan n dengan 1
- Ulangi langkah ke-2 sampai 5 hingga bernilai cacah bilangan.
| Angka awal | 10 | 5 | 12 | 0 | 32 | 56 | 34 | 6 | 11 | 99 |
|------------|----|----|----|----|----|----|----|----|----|----|
| proses 1 | 5 | 10 | 12 | 0 | 32 | 56 | 34 | 6 | 11 | 99 |
| proses 2 | 5 | 10 | 12 | 0 | 32 | 56 | 34 | 6 | 11 | 99 |
| proses 3 | 0 | 5 | 12 | 10 | 32 | 56 | 34 | 6 | 11 | 99 |
| proses 4 | 0 | 5 | 10 | 12 | 32 | 56 | 34 | 6 | 11 | 99 |
| proses 5 | 0 | 5 | 10 | 12 | 32 | 34 | 56 | 6 | 11 | 99 |
| proses 6 | 0 | 5 | 6 | 10 | 12 | 32 | 34 | 56 | 11 | 99 |
| proses 7 | 0 | 5 | 6 | 10 | 12 | 32 | 34 | 56 | 11 | 99 |
| proses 8 | 0 | 5 | 6 | 10 | 11 | 12 | 32 | 34 | 56 | 99 |
| terurut | 0 | 5 | 6 | 10 | 11 | 12 | 32 | 34 | 56 | 99 |
Program
int j,x;
for (int i=1;i<10;i++)
{
x=larik[i];
j=i-1;
while (x<larik[j])
{
larik[j+1]=larik[j];
j--;
}
larik[j+1]=x;
}
2. Pengurutan dengan Pemilian Langsung
Cara kerja metode ini adalah dengan memilih data yang paling kecil (ascending) atau paling besar (descending) kemudian meletakkannya pada posisi paling kiri dengan langkah-langkah penukaran. Misalkan kita akan melakukan pengurutan ascending, maka pertama kali kita tunjuk data yang pertama. Kemudian kita akan mencari data terkecil disebelah kanan data yang pertama tadi. Jika ada, maka data yang terkecil kita tukar dengan data yang pertama, sehingga data pertama pasti memuat data yang paling kecil. Selanjutnya kita lakukan hal yang sama untuk data ke-2 dan seterusnya.
Pseudocode:
- Kerjakan langkah 2-4 untuk i=1 hinggai i=n-1
- Tentukan lokasi = i
- Kerjakan langkah4-5 untuk j=i+1 hingga j=n
- Jika larik(lokasi) > larik(j), maka lokasi = j
- Tukarkan larik(lokasi) dengan larik(i)
| Angka awal | 10 | 5 | 12 | 0 | 32 | 56 | 34 | 6 | 11 | 99 |
|------------|----|----|----|----|----|----|----|----|----|----|
| proses 1 | 0 | 10 | 12 | 5 | 32 | 56 | 34 | 6 | 11 | 99 |
| proses 2 | 0 | 5 | 12 | 10 | 32 | 56 | 34 | 6 | 11 | 99 |
| proses 3 | 0 | 5 | 6 | 10 | 32 | 56 | 34 | 12 | 11 | 99 |
| proses 4 | 0 | 5 | 6 | 10 | 32 | 56 | 34 | 12 | 11 | 99 |
| proses 5 | 0 | 5 | 6 | 10 | 11 | 56 | 34 | 12 | 32 | 99 |
| proses 6 | 0 | 5 | 6 | 10 | 11 | 12 | 34 | 56 | 32 | 99 |
| proses 7 | 0 | 5 | 6 | 10 | 11 | 12 | 32 | 56 | 34 | 99 |
| proses 8 | 0 | 5 | 6 | 10 | 11 | 12 | 32 | 34 | 56 | 99 |
| terurut | 0 | 5 | 6 | 10 | 11 | 12 | 33 | 34 | 56 | 99 |
Program
int lokasi,temp;
for (int i=0;i<10;i++)
{
lokasi = i;
for(int j=i+1;j<10;j++)
{
if (larik[lokasi] > larik[j])
lokasi=j;
}
temp=larik[lokasi];
larik[lokasi]=larik[i];
larik[i]=temp;
}
3. Pengurutan dengan Metode Gelembung (Buble Sort)
Metode ini cukup mudah dipelajari, tetapi metode ini sangat tidak efisien karena melibatkan langkahlangkah perbandingan dan penukaran yang berjumlah sangat banyak. Ada dua cara yang dapat dilakukan untuk mengimplementasikan metode gelembung. Pertama kita letakkan data terbesar disebalah kanan, kemudian berturut-turut data tersebesar selanjutnya disebelah kirinya. Kedua, kita letakkan data paling kecil disebelah kiri, kemudian kita letakkan data terkecil selanjutnya disebelah kanannya. Kita akan membahas cara yang kedua.
Pseudocode:
- Kerjakan langkah untuk i=1 hingga n
- Kerjakan langkah untuk j=n hingga j=1
- Jika larik(j-1) > larik(j) maka tukarkan larik(j-1) dan larik(j)
Program
int temp;
for(int i=1;i<10;i++)
{
for(int j=9;j>=0;j--)
{
if(larik[j-1]>larik[j])
{
temp=larik[j];
larik[j]=larik[j-1];
larik[j-1]=temp;
}
}
}
Latihan
Program
#include <conio.h>
#include <iostream.h>
void main(){
int j, x;
int larik [10] = {10,5,12,0,32,56,34,6,11,99};
cout << "Data sebelum diurutkan : " << endl;
cout << " ";
for(int i=0; i<10; i++)
cout << larik [i] << " ";
cout << endl;
for(int i=1; i<10; i++){
x=larik[i];
j=i-1;
while (x<larik[j]){
larik[j+1]=larik[j];
j--;
}
larik[j+1]=x;
cout << endl;
cout << i << " -> ";
for(int z=0; z<10; z++)
cout << larik [z] << " ";
cout << endl;
}
cout << endl;
cout << "Data setelah diurutkan : " << endl;
cout << " ";
for(int i=0; i<10; i++)
cout << larik[i] << " ";
getch();
}
Sumber
Mata kuliah Struktur Data. STMIK EL Rahma Yogyakarta.
Disusun oleh Eko Riswanto
