Seringkali perancang program perlu mengurutkan sekumpulan data yang
dimiliki untuk memudahkan pemrosesan selanjutnya terhadap data tersebut.Pengurutan adalah sebuah algoritma dasar yang sering diperlukan dalam
pembuatan program. Berbagai algoritma pengurutan telah diciptakan dan
dapat digunakan. Pemahaman tentang beberapa algoritma pengurutan dasar
perlu diketahui, termasuk cara penggunaannya dalam program.
1. Memahami konsep pengurutan
2. Mengenal beberapa algoritma pengurutan
3. Menerapkan algoritma pengurutan dalam program
Pengertian Sort
Sorting atau pengurutan data adalah proses yang sering harus dilakukan
dalam pengolahan data. Sort dalam hal ini diartikan mengurutkan data yang
berada dalam suatu tempat penyimpanan, dengan urutan tertentu baik urut
menaik (ascending) dari nilai terkecil sampai dengan nilai terbesar, atau urut
menurun (descending) dari nilai terbesar sampai dengan nilai terkecil. Sorting
adalah proses pengurutan.
Terdapat dua macam pengurutan:
⟹ Pengurutan internal (internal sort), yaitu pengurutan terhadap
sekumpulan data yang disimpan dalam media internal komputer
yang dapat diakses setiap elemennya secara langsung. Dapat
dikatakan sebagai pengurutan tabel
⟹ Pengurutan eksternal (external sort), yaitu pengurutan data
yang disimpan dalam memori sekunder, biasanya data bervolume
besar sehingga tidak mampu untuk dimuat semuanya dalam memori.
Dalam courseware ini, hanya akan dibahas algoritma pengurutan internal,
dengan data berada dalam array satu dimensi.
Algoritma pengurutan internal yang utama antara lain:
1. Bubble Sort
2. Selection Sort
3. Insertion Sort
4. Shell Sort
5. Merge Sort
6. Radix Sort
7. Quick Sort
8. Heap Sort
Dalam courseware ini hanya akan dibahas tiga metode sort yang pertama yang
dianggap mudah, yaitu: Bubble Sort , Selection Sort dan Insertion Sort
Bubble Sort
Bubble sort adalah proses pengurutan sederhana yang bekerja dengan
cara berulang kali membandingkan dua elemen data pada suatu saat dan
menukar elemen data yang urutannya salah. Ide dari Bubble sort adalah
gelembung air yang akan "mengapung" untuk table yang terurut menaik
(ascending). Elemen bernilai kecil akan "diapungkan" (ke indeks terkecil),
artinya diangkat ke "atas" (indeks terkecil) melalui pertukaran. Karena algoritma ini melakukan pengurutan dengan cara membandingkan elemen-
elemen data satu sama lain, maka bubble sort termasuk ke dalam jenis
algoritma comparison-based sorting.
Proses dalam Bubble sort dilakukan sebanyak N-1 langkah (pass) dengan N
adalah ukuran array. Pada akhir setiap langkah ke – I , array L[0..N] akan
terdiri atas dua bagian, yaitu bagian yang sudah terurut L[0..I] dan bagian
yang belum terurut L[I+1..N-1]. Setelah langkah terakhir, diperoleh
array L[0..N-1] yang terurut menaik.
Untuk mendapatkan urutan yang menaik, algoritmanya dapat ditulis secara
global sebagai berikut :
Untuk setiap pass ke – I = 0,1,.........., N-2 , lakukan :
Mulai dari elemen J = N-1, N-2,....., I + 1, lakukan :
➤ Bandingkan L[J-1] dengan L[J]
➤ Pertukarkan L[J-1] dengan L[J] jika L[J-1] > L[J]
Rincian setiap pass adalah sebagai berikut :
Pass 1: I = 0. Mulai dari elemen J = N-1,N–2,...,1, bandingkan
L[J-1] dengan L[J]. Jika L[J-1] > L[J],
pertukarkan L[J-1] dengan L[J]. Pada akhir langkah 1, elemen L[0] berisi harga minimum pertama.
Pass 2: I = 1. Mulai dari elemen J = N-1,N–2,...,2, bandingkan
L[J-1] dengan L[J]. Jika L[J-1] > L[J], pertukarkan L[J-
1] dengan L[J]. Pada akhir langkah 2, elemen L[1] berisi
harga minimum kedua dan array L[0..1] terurut, sedangkan
L[2..(N-1)] belum terurut.
Pass 3: I = 2. Mulai dari elemen J = N-1,N–2,...,3, bandingkan
L[J-1] dengan L[J]. Jika L[J-1] > L[J], pertukarkan L[J-
1] dengan L[J]. Pada akhir langkah 3, elemen L[2] berisi
harga minimum ketiga dan array L[0..2] terurut,
sedangkan L[3..(N-1)] belum terurut.
Pass N-1: Mulai dari elemen J = N-1, bandingkan L[J-1] dengan
L[J]. Jika L[J-1] > L[J], pertukarkan L[J-1] dengan
L[J].
Selection Sort
Algoritma Selection sort memilih elemen maksimum/minimum array,
lalu menempatkan elemen maksimum/minimum itu pada awal atau akhir array
(tergantung pada urutannya ascending/descending). Selanjutnya elemen
tersebut tidak disertakan pada proses selanjutnya. Karena setiap kali selection
sort harus membandingkan elemen-elemen data, algoritma ini termasuk dalam
comparison-based sorting.
Seperti pada algoritma Bubble Sort, proses memilih nilai maksimum /minimum
dilakukan pada setiap pass. Jika array berukuran N, maka jumlah pass adalah
N-1.
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.
Maximum Selection Sort Ascending
Untuk mendapatkan array yang terurut menaik (ascending), algoritma
maximum selection sort dapat ditulis sebagai berikut :
1. Jumlah Pass = N-1 (jumlah pass)
2. Untuk setiap pass ke – I = 0,1,....., jumlah pass lakukan :
⟹ cari elemen maksimum (maks) mulai dari elemen ke – I
sampai elemen ke – (N-1)
⟹ pertukarkan maks dengan elemen ke – I
⟹ kurangi N dengan satu
Rincian setiap pass adalah sebagai berikut :
Langkah 1 : Cari elemen maksimum di dalam L[0..(N-1)]
Pertukarkan elemen maksimum dengan elemen L[N-1]
Langkah 2 : Cari elemen maksimum di dalam L[0..N-2]
Pertukarkan elemen maksimum dengan elemen L[N-2]
Langkah 3 : Cari elemen maksimum di dalam L[0..N-3]
Pertukarkan elemen maksimum dengan elemen L[N-3]
..............
Langkah N-1: Tentukan elemen maksimum di dalam L[0..1]
Pertukarkan elemen maksimum dengan elemen L[0]
(elemen yang tersisa adalah L[0], tidak perlu diurut karena hanya satu-
satunya).
Jadi , pada setiap pass pengurutan terdapat proses mencari harga maksimum
dan proses pertukaran dua buah elemen array.
Misal, terdapat array L dengan N = 5 buah elemen yang belum terurut. Array
akan diurutkan secara Ascending (menaik), dengan algoritma maximum
selection sort.
Berikut ini akan diberikan pseudocode procedure Maximum Selection Sort
Ascending dan pseudocode procedure untuk tukar tempat.
Pseudocode Algoritma
Maximum Selection Sort secara Ascending :
1. //prosedur algoritma
Maximum Selection Sort secara Ascending
2. //I.S:arraysudah berisi
nilai integeryang belum terurut
3. //F.S:nilai-nilai dalam
arrayterurut secara Ascending
4. procedure
v_SelAsc(input/output A:array[0..4]of integer,
input N:integer)
5. KAMUS:
|
6. maks,k,j,temp:integer
7. ALGORITMA:
8. for(k=(N-1);k>=0;kk-1)
9. maks⬅0;
10. // cari elemen
maksimum
11. for(j=0;j<=k;jj+1)
12. if (A[j] >
A[maks])
13. maks⬅j;
14. endif
15. endfor
16. v_Tukar(A[k],A[maks])
//panggil procedure v_Tukar
17. endfor
18.end procedure
|
Pseudocode Algoritma Tukar Tempat :
1. //prosedur algoritma
Tukar Tempat
2. //I.S:nilai-nilaiyang
dikirimkan sudah terdefinisi sebelumnya
3. //F.S:nilaiyang
dikirimkan tertukar nilainya
4. procedure
v_Tukar(input/output P:integer,
input/output M:integer)
5. KAMUS:
6. temp:integer
|
7. ALGORITMA:
8. temp P
9. P ⬅ M
10. M ⬅ temp
11.endprocedure
|
Program lengkap penerapan algoritma Maximum Selection Sort Ascending dalam
bahasa C:
#include <stdio.h>
#include <conio.h>
void v_SelAsc(int A[],int
N);
void v_Tukar(int *P,int
*M);
main()
{ int L[5];
int i,N;
//input data array
printf("Banyak Data:
");scanf("%i",&N);
for(i=0;i<N;i++)
{ printf("Data ke-%i:
",i+1);
scanf("%i",&L[i]);
} //end loop i
//memanggil procedure
v_SelAsc
v_SelAsc(L,N);
//menampilkan kembali data
array
printf("\nData
Terurut:\n");
for(i=0;i<N;i++)
{
printf("%3i",L[i]); } //end loop i
getche();
}
void v_SelAsc(int A[5],int
N)
{ int maks,k,j,temp;
for(k=(N-1);k>=0;k--)
{ maks=0;
for(j=0;j<=k;j++)
{ if (A[j] > A[maks])
{ maks=j; } //endif
} //end loop j
v_Tukar(&A[k],&A[maks]);
} //end loop k
} //end procedure v_SelAsc
void v_Tukar(int *P,int *M)
{ int temp;
temp = *P;
*P = *M;
*M = temp;
} //end procedure v_Tukar
|
Maximum Selection Sort Descending
Misal, terdapat array L dengan N = 5 buah elemen yang belum
terururt. Array akan diurutkan secara Descending (menurun), dengan
algoritma maximum selection sort:
1. //prosedur algoritma
Maximum Selection Sort secara Descending
2. //I.S:arraysudah berisi
nilai integeryang belum terurut
3. //F.S:nilai-nilai dalam
arrayterurut secara Descending
4. procedure
v_SelDesc(input/output A:array[0..4]of integer,
input N:integer)
5. KAMUS:
6. k,maks,j,temp:integer
7. ALGORITMA:
8. for(k=0;k<=(N-2);k⬅k+1)
9. //cari elemen maksimum
10. maks⬅k
11.
for(j=(k+1);j<=(N-1);j⬅j+1)
12. if (A[j] > A[maks])
13. maks⬅j
14. endif
15. endfor
16. temp⬅A[k]
17. A[k]⬅A[maks]
18. A[maks]⬅temp
19. endfor
|
Program lengkap penerapan algoritma Maximum Selection Sort Descending
dalam bahasa C:
1. #include
<stdio.h>
2. #include
<conio.h>
3. void v_Tukar(int *P,int
*M);
4. void v_SelDesc(int
A[5],int N);
5. main()
6. { int L[5];
7. int i,k,j,maks,temp,N;
8. printf("Banyak
Data: ");scanf("%i",&N);
9. //input data array
10. printf("Input
Data Array\n");
11. for(i=0;i<N;i++)
12. { printf("Data
ke-%i = ",i+1);
13.
scanf("%i",&L[i]); } //endloop i
14. //panggil procedure
v_SelDesc
15. v_SelDesc(L,N);
16. printf("\nOutput
Data Array Terurut:\n");
17. for(i=0;i<N;i++)
18. { printf("
%5i",L[i]); } //endloop i
19.
20. printf("\nTekan
Enter...\n");
21. getche();
22. } //end main program
23.
24. void v_SelDesc(int
A[5],int N)
25. { int k,maks,j,temp;
26. //proses sorting max
descending
27.
for(k=0;k<=(N-2);k++)
28. { //cari elemen maksimum
29. maks=k;
30.
for(j=(k+1);j<=(N-1);j++)
31. { if (A[j] >
A[maks])
32. maks=j; } //endfor
loop j
33.
v_Tukar(&A[k],&A[maks]);
34. } //endfor loop k
35. } //end procedure
v_SelDesc
36.
37. void v_Tukar(int
*P,int *M)
38. { int temp;
39. temp = *P;
40. *P = *M;
41. *M = temp;
42. } //end procedure
v_Tukar
|
Minimum Selection Sort Ascending
Untuk mendapatkan array yang terurut menaik (ascending), algoritma
minimum selection sort dapat ditulis sebagai berikut :
1. Jumlah Pass = N-1 (jumlah pass)
2. Untuk setiap pass ke – I = 0,1,....., N-1, lakukan :
a. cari elemen minimum (min) mulai dari elemen ke – I
sampai elemen ke – (N-1)
b. pertukarkan min dengan elemen ke – I
Langkah 1 : Cari elemen minimum di dalam L[0..(N-1)]
Pertukarkan elemen terkecil dengan elemen L[0]
Langkah 2 : Cari elemen minimum di dalam L[1..(N-1)]
Pertukarkan elemen terkecil dengan elemen L[1]
Langkah 3 : Cari elemen minimum di dalam L[2..(N-1)]
Pertukarkan elemen terkecil dengan elemen L[2]
Langkah N-1: Tentukan elemen minimum di dalam L[(N-2)..(N-1)]
Pertukarkan elemen terkecil dengan elemen L[N-2]
(elemen yang tersisa adalah L[N-1], tidak perlu diurut karena
hanya satu-satunya).
Pseudocode Algoritma
Minimum Selection Sort secara Ascending :
1. //prosedur algoritma
Minimum Selection Sort secara Ascending
2. //I.S:arraysudah berisi
nilai integeryang belum terurut
3. //F.S:nilai-nilai dalam
arrayterurut secara Ascending
4. procedure
v_minAsc(input/output A:array[0..4]of integer,
input N:integer)
5. KAMUS:
6. k,min,j,temp:integer
7. ALGORITMA:
8. for(k=0;k<=(N-2);k⬅k+1)
9. //cari elemen terkecil
10. min ⬅ k
11. for(j=(k+1);j<=(N-1);j⬅j+1)
12. if (A[j] < A[min])
14. endif
15. endfor
16. v_Tukar(A[k],A[min])
17.endfor
|
Program lengkap penerapan algoritma Minimum Selection Sort Ascending dalam
bahasa C:
1. #include
<stdio.h>
2. #include
<conio.h>
3. void v_minAsc(int
A[5],int N);
4. void v_Tukar(int *P,int
*M);
5. main()
6. { int L[5];
7. int i,j,k,min,temp,N;
8. //input data array
9. printf("Input Data
Array\n");
10. printf("\nBanyak
Data : "); scanf("%i",&N);
11. for(i=0;i<N;i++)
12. { printf(" Data
ke-%i = ",i+1);
13.
scanf("%i",&L[i]); } //end loop i
14. //panggil procedure
v_minAsc
15. v_minAsc(L,N);
16. //output data array
17. printf("\n Data
Sortir:\n");
18. for(i=0;i<N;i++)
19. { printf("
%5i",L[i]); } //end loop i
20. printf("\n Tekan
Enter\n");
21. getche();
22. } //end main program
23.
24. void v_minAsc(int
A[5],int N)
25. { int k,min,j,temp;
26. //proses minimum
ascendingselection sort
27.
for(k=0;k<=(N-2);k++)
28. { min = k;
29.
for(j=(k+1);j<=(N-1);j++)
30. { if (A[j] <
A[min])
31. min = j; } //endloop j
32.
v_Tukar(&A[k],&A[min]); } //end loop k
33. } //end procedure
34.
35. void v_Tukar(int
*P,int *M)
36. { int temp;
37. temp = *P;
38. *P = *M;
39. *M = temp;
40. } //end procedure v_Tukar
|
Minimum Selection Sort Descending
Misal, terdapat array L dengan N = 5 buah elemen yang belum
terururt. Array akan diurutkan secara Descending (menurun), dengan
algoritma minimum selection sort.
Pseudocode Algoritma Minimum Selection Sort secara Descending :
Pseudocode Algoritma Minimum Selection Sort secara Descending :
1. //prosedur algoritma
Minimum Selection Sort secara Descending
2. //I.S:arraysudah berisi
nilai integeryang belum terurut
3. //F.S:nilai-nilai dalam
arrayterurut secara Descending
4. procedure
v_minDesc(input/output A:array[0..4]of integer,
input N:integer)
5. KAMUS:
6. k,j,temp,min : integer
|
7. ALGORITMA:
8. //minimum selection
sort descending
9. for(k=(N-1);k>=1;k⬅k-1)
10. min⬅0
11. //cari nilai terkecil
12. for(j=0;j<=k;j⬅j+1)
13. if (A[j] <
A[min])
14. min⬅j
15. endif
16. endfor
17. v_Tukar(A[k],A[min])
20. endfor
|
Program lengkap penerapan algoritma Minimum Selection Sort Descending
dalam bahasa C:
1. #include
<stdio.h>
2. #include
<conio.h>
3. void v_minDesc(int
A[5],int N);
4. void v_Tukar(int *P,int
*M);
5. main()
6. { int L[5];
7. int i,N;
8. //input data array
9. printf("Input Data
Array\n");
10. printf("\nBanyak
Data : ");scanf("%i",&N);
11. for(i=0;i<N;i++)
12. { printf(" Data ke-%i = ",i+1);
13. scanf("%i",&L[i]); } //endloop i
14. //panggil procedure v_minDesc
15. v_minDesc(L,N);
16. //output data array
17. printf("\n Data Sortir:\n");
18. for(i=0;i<N;i++)
19. { printf(" %5i",L[i]); } //endloop i
20. printf("\n Tekan Enter...\n");
21. getche();
22. } //end main program
23.
24. void v_minDesc(int A[5],int N)
25. { int k,j,temp,min;
26. //minimum selection sort descending
27. for(k=(N-1);k>=1;k--)
28. { min = 0;
29. for(j=0;j<=k;j++)
30. { if (A[j] < A[min])
31. min=j; } //endloop j
32. v_Tukar(&A[k],&A[min]); } //endloop k
33. } //end procedure v_minDesc
34.
35. void v_Tukar(int *P,int *M)
36. { int temp;
37. temp = *P;
38. *P = *M;
39. *M = temp;
40. } //end procedure v_Tukar
|
Insertion Sort
Insertion sort adalah sebuah algoritma pengurutan yang membandingkan
dua elemen data pertama, mengurutkannya, kemudian mengecek elemen data
berikutnya satu persatu dan membandingkannya dengan elemen data yang
telah diurutkan. Karena algoritma ini bekerja dengan membandingkan elemen-
elemen data yang akan diurutkan, algoritma ini termasuk pula dalam
comparison-based sort.
Ide dasar dari algoritma Insertion Sort ini adalah mencari tempat yang
"tepat" untuk setiap elemen array, dengan cara sequential search. Proses ini
kemudian menyisipkan sebuah elemen array yang diproses ke tempatnya yang
seharusnya. Proses dilakukan sebanyak N-1 tahapan (dalam sorting disebut
sebagai "pass"), dengan indeks dimulai dari 0.
Proses pengurutan dengan menggunakan algoritma Insertion Sort
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 dengan
posisi yang seharusnya.
Misal terdapat array satu dimensi L, yang terdiri dari 7 elemen array
(n=7). Array L sudah berisi data seperti dibawah ini dan akan diurutkan
secara ascending dengan algoritma Insertion Sort.
Pseudocode Algoritma Insertion Sort secara Ascending :
Pseudocode Algoritma Insertion Sort secara Ascending :
1. //prosedur algoritma
Insertion Sort secara Ascending
2. //I.S:arraysudah berisi
nilai integeryang belum terurut
3. //F.S:nilai-nilai dalam arrayterurut secara Ascending
4. procedure
v_inAsc(input/output A:array[0..6]of integer,
input
N:integer)
5. KAMUS:
6. k,X,i:integer
7. ALGORITMA:
8. //insertion sort ascending
9. k⬅1
10. while(k<=N-1)
11. i⬅k
12. X⬅A[i]
13. while(i>=1 && A[i-1]>X)
14. A[i]⬅A[i-1]
15. i⬅i-1
16. endwhile
17. A[i]⬅X
18. k⬅k+1
19. endwhile
|
Program lengkap penerapan algoritma Insertion Sort Ascending
dalam bahasa C:
#include <stdio.h>
#include <conio.h>
main()
{ int L[7];
int i,N;
void v_insertAsc(int
A[7],int N);
//input data array
printf("Input Data
Array\n");
printf("\nBanyak
Data: "); scanf("%i",&N);
for(i=0;i<N;i++)
{ printf("Nilai ke-%i
= ",i+1);
scanf("%i",&L[i]);
} //end loop i
//panggil procedure
v_inAsc
v_insAsc(L,N);
//output data array
printf("Data
terurut:\n");
for(i=0;i<N;i++)
{
printf("%5i",L[i]); } //end loop i
printf("\nTekan
Enter...\n");
getche();
}
void v_insAsc(int A[7],int
N)
{ int k,X,i;
//insertion sort ascending
k=1;
while(k<=N-1)
{ i=k;
X=A[i];
while(i>=1 && A[i-1]>X)
{ A[i]=A[i-1];
i--; } //endwhile
A[i]=X;
k++; } //endwhile
} //end procedure
|
1. Proses Sorting merupakan proses mengurutkan data yang berada dalam
suatu tempat penyimpanan, dengan urutan tertentu baik urut menaik
(ascending) dari nilai terkecil sampai dengan nilai terbesar, atau urut
menurun (descending) dari nilai terbesar sampai dengan nilai terkecil
2. Terdapat dua macam proses pengurutan, yaitu pengurutan internal
(internal sort) dan pengurutan eksternal (external sort).
3. Bubble sort adalah proses pengurutan sederhana yang bekerja dengan cara
berulang kali membandingkan dua elemen data pada suatu saat dan
menukar elemen data yang urutannya salah.
4. Algoritma Selection sort memilih elemen maksimum/minimum array, lalu
menempatkan elemen maksimum/minimum itu pada awal atau akhir array
(tergantung pada urutannya ascending/descending).
5. Algoritma Insertion Sort, mencari tempat yang "tepat" untuk setiap elemen
array, dengan cara sequential search. Proses ini kemudian menyisipkan
sebuah elemen array yang diproses ke tempatnya yang seharusnya.
~Sekian Terimakasih Semoga Bermanfaat~
