SORTING
Sorting atau
pengurutan data adalah proses yang sering harus dilakukan dalam pengolahan
data. Sortdalam 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 dalamarray 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
1.1 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].
Pada akhir langkah N-2, elemen L[N-2] berisi nilai minimun ke
[N-2] dan array L[0..N-2] terurut menaik (elemen yang tersisa
adalah L[N-1], tidak perlu diurut karena hanya satu-satunya).
Misal array L dengan N = 5 buah elemen yang
belum terurut. Array akan diurutkan secara ascending(menaik).
|
8
|
9
|
7
|
6
|
1
|
0 1
2 3 4
Pass 1 :
I = 0 ;J= N-1=
4
8 9
7 1
6
J =
3
8 9 1
7 6
J =
2 8 1
9
7 6
J =
1 1
8
9
7 6
Hasil akhir langkah 1 :
|
1
|
8
|
9
|
7
|
6
|
0
1 2
3 4
Pass 2 :
I = 1 ;J= N-1=
4 1
8 9 6
7
J =
3 1 8 6
9 7
J =
2 1 6
8
9 7
Hasil akhir langkah 2 :
|
1
|
6
|
8
|
9
|
7
|
0
1 2
3 4
Pass 3 :
I = 2 ;J= N-1=
4 1 6 8 7
9
J =
3 1 6 7
8 9
Hasil akhir langkah 3 :
|
1
|
6
|
7
|
8
|
9
|
0
1 2
3 4
Pass 4 :
I = 3 ;J= N-1=
4 1 6 7 8 9
Hasil akhir langkah 4 :
|
1
|
6
|
7
|
8
|
9
|
0
1 2
3 4
Selesai. Array L sudah terurut !!
Pseudocode prosedur algoritma Bubble Sort secara Ascending
|
1. //prosedur algoritma Bubble Sort secara Ascending2.
//I.S:array sudah berisi nilai integer yang belum terurut
3. //F.S:nilai-nilai dalam array terurut secara Ascending
4. procedure v_Bubble(input/output A:array[0..4]of integer,
input N:integer)
5. KAMUS:
6. i,j,temp:integer
|
|
7. ALGORITMA:8. for(i=0;i<=(N-2);i++)
9. for(j=(N-1);j>=(i+1);j–)
10. if (A[j-1]>A[j])
11. tempßA[j-1]
12. A[j-1]ßA[j]
13. A[j]ßtemp
14. endif
15. endfor
16. endfor
17.end procedure
|
Program lengkap penerapan algoritma Bubble Sort dalam
bahasa C
|
1. #include <stdio.h>2. #include
<conio.h>
3.
4. void v_Bubble(int A[],int N);
5. void main()
6. { int L[5];
7. int i,N;
8. //proses untuk memasukkan data array
9. printf(“Banyak data :
“);scanf(“%i”,&N);
10. for(i=0;i<N;i++)
11. { printf(“Data ke-%i: “,i+1);
12. scanf(“%i”,&L[i]); }
//end loop i
13. //memanggil procedure bubble sort
14. v_Bubble(L,N);
15.
16. //proses menampilkan kembali data array
17. printf(“\nData Array Terurut\n”);
18. for(i=0;i<N;i++)
19. { printf(“%3i”,L[i]); };
20. getche();
21. } //end main program
22.
23. void v_Bubble(int A[5],int N)
24. { int a,b,temp;
25. //proses sortir dengan bubble sort
26. for(a=0;a<=(N-2);a++)
27. { for(b=(N-1);b>=(a+1);b–)
28. { if (A[b-1] > A[b])
29. { temp = A[b-1];
30. A[b-1]=
A[b];
31. A[b] =
temp; } //endif
32. } //end loop j
33. } //end loop i
34. } //end procedure v_Bubble
|
Output yang dihasilkan:
1.2 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 :
- Algoritma pengurutan maksimum (maximum
selection sort), yaitu memilih elemen maksimum sebagai basis
pengurutan.
- Algoritma pengurutan minimum (minimum
selection sort), yaitu memilih elemen minimum sebagai basis
pengurutan.
1.2.1 Maximum Selection
Sort Ascending
Untuk mendapatkan array yang
terurut menaik (ascending), algoritma maximum
selection sort dapat ditulis sebagai berikut :
- Jumlah Pass = N-1 (jumlah pass)
- 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 secaraAscending (menaik),
dengan algoritma maximum selection sort.
|
9
|
7
|
12
|
6
|
1
|
|
0
|
1
|
2
|
3
|
4
|
Pass 1 :
Ÿ Cari elemen maksimum di dalam array L[0..4].
Maks=L[2]=12
Ÿ Tukar Maks dengan L[4], diperoleh :
|
9
|
7
|
1
|
6
|
12
|
|
0
|
1
|
2
|
3
|
4
|
Pass 2 :
(berdasarkan susunan array pada Pass 1)
Ÿ Cari elemen maksimum di dalam array L[0..3].
Maks=L[0]=9
Ÿ Tukar Maks dengan L[3], diperoleh :
|
6
|
7
|
1
|
9
|
12
|
|
0
|
1
|
2
|
3
|
4
|
Pass 3:
(berdasarkan susunan array pada Pass 2)
Ÿ Cari elemen maksimum di dalam array L[0..2].
Maks=L[1]=7
Ÿ Tukar Maks dengan L[2], diperoleh :
|
6
|
1
|
7
|
9
|
12
|
|
0
|
1
|
2
|
3
|
4
|
Pass 4 :
(berdasarkan susunan array pada Pass 3)
Ÿ Cari elemen maksimum di dalam array L[0..1].
Maks=L[0]=6
Ÿ Tukar Maks dengan L[1], diperoleh :
|
1
|
6
|
7
|
9
|
12
|
|
0
|
1
|
2
|
3
|
4
|
Selesai, array L sudah terurut secara Ascending.
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
Ascending2. //I.S:array sudah berisi nilai integer yang belum terurut
3. //F.S:nilai-nilai dalam array terurut 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;kßk-1)
9. maksß0;
10. // cari elemen maksimum
11. for(j=0;j<=k;jßj+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 Tempat2. //I.S:nilai-nilai yang
dikirimkan sudah terdefinisi sebelumnya
3. //F.S:nilai yang 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
|
Output yang dihasilkan:
1.2.2 Maximum Selection
Sort Descending
Misal, terdapat array L
dengan N = 5 buah elemen yang belum terururt. Array akan
diurutkan secaraDescending (menurun),
dengan algoritma maximum selection sort.
|
9
|
8
|
11
|
7
|
12
|
|
0
|
1
|
2
|
3
|
4
|
Pass 1 :
Ÿ Cari elemen maksimum di dalam array L[0..4].
Maks=L[4]=12
Ÿ Tukar Maks dengan L[0], diperoleh :
|
12
|
8
|
11
|
7
|
9
|
|
0
|
1
|
2
|
3
|
4
|
Pass 2 :
(berdasarkan susunan array pada Pass 1)
Ÿ Cari elemen maksimum di dalam array L[1..4].
Maks=L[2]=11
Ÿ Tukar Maks dengan L[1], diperoleh :
|
12
|
11
|
8
|
7
|
9
|
|
0
|
1
|
2
|
3
|
4
|
Pass 3 :
(berdasarkan susunan array pada Pass 2)
Ÿ Cari elemen maksimum di dalam array L[2..4].
Maks=L[4]=9
Ÿ Tukar Maks dengan L[2], diperoleh :
|
12
|
11
|
9
|
7
|
8
|
|
0
|
1
|
2
|
3
|
4
|
Pass 4 :
(berdasarkan susunan array pada Pass 3)
Ÿ Cari elemen maksimum di dalam array L[3..4].
Maks=L[4]=8
Ÿ Tukar Maks dengan L[3], diperoleh :
|
12
|
11
|
9
|
8
|
7
|
|
0
|
1
|
2
|
3
|
4
|
Selesai array L
sudah terurut secara Descending (menurun)
Pseudocode Algoritma Maximum Selection Sort secara Descending :
|
1. //prosedur algoritma Maximum Selection Sort secara
Descending
|
2. //I.S:array sudah berisi nilai integer yang belum terurut
3. //F.S:nilai-nilai dalam array terurut secara Descending
4. procedure v_SelDesc(input/output A:array[0..4]of
integer,
input N:integer)
5. KAMUS:
6. k,maks,j,temp:integer7. 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
Output yang dihasilkan:
1.2.3 Minimum Selection
Sort Ascending
Untuk mendapatkan array yang
terurut menaik (ascending), algoritma minimum selection
sort dapat ditulis sebagai berikut :
- Jumlah Pass = N-1 (jumlah pass)
- cari elemen minimum (min) mulai dari
elemen ke – I sampai elemen ke – (N-1)
- pertukarkan min dengan
elemen ke – I
- Untuk setiap pass ke – I = 0,1,….., N-1,
lakukan :
Rincian setiap pass adalah sebagai berikut :
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).
Jadi, pada setiap pass pengurutan terdapat
proses mencari harga minimum dan proses pertukaran dua buah elemen array.
Misal, terdapat array L
dengan N = 5 buah elemen yang belum terururt. Array akan
diurutkan secaraAscending (menaik), dengan algoritma
minimum selection sort.
|
9
|
7
|
12
|
6
|
1
|
|
0
|
1
|
2
|
3
|
4
|
Pass 1 :
Ÿ Cari elemen terkecil di dalam array L[0..4].
Min=L[4]=1
Ÿ Tukar Min dengan L[0], diperoleh :
|
1
|
7
|
12
|
6
|
9
|
|
0
|
1
|
2
|
3
|
4
|
Pass 2 :
(berdasarkan susunan array pada Pass 1)
Ÿ Cari elemen terkecil di dalam array L[1..4].
Min=L[3]=6
Ÿ Tukar Min dengan L[1], diperoleh :
|
1
|
6
|
12
|
7
|
9
|
|
0
|
1
|
2
|
3
|
4
|
Pass 3:
(berdasarkan susunan array pada Pass 2)
Ÿ Cari elemen terkecil di dalam array L[2..4].
Min=L[3]=7
Ÿ Tukar Min dengan L[2], diperoleh :
|
1
|
6
|
7
|
12
|
9
|
|
0
|
1
|
2
|
3
|
4
|
Pass 4 :
(berdasarkan susunan array pada Pass 3)
Ÿ Cari elemen terkecil di dalam array L[3..4].
Min=L[4]=9
Ÿ Tukar Min dengan L[3], diperoleh :
|
1
|
6
|
7
|
9
|
12
|
|
0
|
1
|
2
|
3
|
4
|
Selesai, array L sudah terurut secara Ascending.
Pseudocode Algoritma Minimum Selection Sort secara Ascending :
|
1. //prosedur algoritma Minimum Selection Sort secara
Ascending
|
2. //I.S:array sudah berisi nilai integer yang belum terurut
3. //F.S:nilai-nilai dalam array terurut secara Ascending
4. procedure v_minAsc(input/output A:array[0..4]of integer,
input N:integer)
5. KAMUS:
6. k,min,j,temp:integer7. 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])
13. min ß j
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 ascending selection 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
Output yang dihasilkan:
1.2.4 Minimum Selection
Sort Descending
Misal, terdapat array L
dengan N = 5 buah elemen yang belum terururt. Array akan
diurutkan secaraDescending (menurun),
dengan algoritma minimum selection sort.
|
9
|
8
|
11
|
7
|
12
|
|
0
|
1
|
2
|
3
|
4
|
Pass 1 :
Ÿ Cari elemen terkecil di dalam array L[0..4]. Min=L[3]=7
Ÿ Tukar Min dengan L[4], diperoleh :
|
9
|
8
|
11
|
12
|
7
|
|
0
|
1
|
2
|
3
|
4
|
Pass 2 :
(berdasarkan susunan array pada Pass 1)
Ÿ Cari elemen terkecil di dalam array L[0..3]. Min=L[1]=8
Ÿ Tukar Min dengan L[3], diperoleh :
|
9
|
12
|
11
|
8
|
7
|
|
0
|
1
|
2
|
3
|
4
|
Pass 3 :
(berdasarkan susunan array pada Pass 2)
Ÿ Cari elemen terkecil di dalam array L[0..2]. Min=L[0]=9
Ÿ Tukar Min dengan L[2], diperoleh :
|
11
|
12
|
9
|
8
|
7
|
|
0
|
1
|
2
|
3
|
4
|
Pass 4 :
(berdasarkan susunan array pada Pass 3)
Ÿ Cari elemen terkecil di dalam array L[0..1]. Min=L[0]=11
Ÿ Tukar Min dengan L[1], diperoleh :
|
12
|
11
|
9
|
8
|
7
|
|
0
|
1
|
2
|
3
|
4
|
Selesai array L
sudah terurut secara Descending (menurun)
Pseudocode Algoritma Minimum
Selection Sort secara Descending :
|
1. //prosedur algoritma Minimum Selection Sort secara
Descending
|
2. //I.S:array sudah berisi nilai integer yang belum terurut
3. //F.S:nilai-nilai dalam array terurut secara Descending
4. procedure v_minDesc(input/output A:array[0..4]of integer,
input N:integer)
5. KAMUS:
6. k,j,temp,min :
integer7. 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
Output yang dihasilkan:
1.3 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 sortingdisebut
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.
|
L[]
|
15
|
10
|
7
|
22
|
17
|
5
|
12
|
|
|
0
|
1
|
2
|
3
|
4
|
5
|
6
|
||
Tahapan Insertion Sort:
1. Dimulai dari L[1] :
Simpan nilai L[1] ke variabel X.
(Pass-1)
Geser masing-masing satu langkah ke kanan semua nilai yang ada disebelah kiri
L[1] satu persatu apabila nilai tersebut lebih besar dari X.
Setelah itu insert-kan (sisipkan) X di bekas
tempat nilai yang terakhir digeser.
2. Dilanjutkan ke
L[2]: Simpan nilai L[2] ke variabel X
(Pass-2)
Geser masing-masing satu langkah ke kanan semua nilai yang ada disebelah kiri
L[2] satu persatu apabila nilai tersebut lebih besar dari X.
Setelah itu insert-kan (sisipkan) X di bekas
tempat nilai yang terakhir di geser.
3. Demikian seterusnya untuk L[3], L[4],L[5], dan
terakhir L[6] bila n = 7. Sehingga untuk n = 7 ada 6pass proses
pengurutan.
Berikut ilustrasi dari 6 pass tersebut:
|
Data awal:
|
15
|
10
|
7
|
22
|
17
|
5
|
12
|
|
|
0
|
1
|
2
|
3
|
4
|
5
|
6
|
||
|
Pass-1:
|
15
|
10
|
7
|
22
|
17
|
5
|
12
|
10
|
||
|
0
|
1
|
2
|
3
|
4
|
5
|
6
|
X
|
|||
Pass 1 dimulai dari kolom L[1], X=L[1]=10
15 lebih besar dari 10, maka geser 15 ke kanan. Proses selesai
karena sudah sampai kolom 1. Kemudian insert X menggantikan 15.
|
15
|
15
|
7
|
22
|
17
|
5
|
12
|
||||||||
|
0
|
1
|
2
|
3
|
4
|
5
|
6
|
||||||||
|
10
|
15
|
7
|
22
|
17
|
5
|
12
|
||||||||
|
0
|
1
|
2
|
3
|
4
|
5
|
6
|
||||||||
|
Hasil Pass 1:
|
10
|
15
|
7
|
22
|
17
|
5
|
12
|
|
|
0
|
1
|
2
|
3
|
4
|
5
|
6
|
||
|
Pass-2:
|
10
|
15
|
7
|
22
|
17
|
5
|
12
|
7
|
||
|
0
|
1
|
2
|
3
|
4
|
5
|
6
|
X
|
|||
Pass 2 dimulai dari L[2], X=L[2]=7.
15 lebih besar dari 7, maka geser 15 ke kanan. 10 lebih besar
dari 7, maka geser 10 ke kanan. Proses selesai karena sudah sampai kolom 1.
Kemudian insert X menggantikan 10.
|
15
|
15
|
22
|
17
|
5
|
12
|
|||||||||
|
0
|
1
|
2
|
3
|
4
|
5
|
6
|
||||||||
|
10
|
10
|
15
|
22
|
17
|
5
|
12
|
||||||||
|
0
|
1
|
2
|
3
|
4
|
5
|
6
|
||||||||
|
7
|
10
|
15
|
22
|
17
|
5
|
12
|
||||||||
|
0
|
1
|
2
|
3
|
4
|
5
|
6
|
||||||||
|
Hasil Pass 2:
|
7
|
10
|
15
|
22
|
17
|
5
|
12
|
|||||||||||
|
0
|
1
|
2
|
3
|
4
|
5
|
6
|
||||||||||||
|
Pass-3:
|
7
|
10
|
15
|
22
|
17
|
5
|
12
|
22
|
||||||||||
|
0
|
1
|
2
|
3
|
4
|
5
|
6
|
X
|
|||||||||||
Pass 3 dimulai dari L[3], X=L[3]=22.
15 tidak lebih besar dari 22, maka proses selesai. Kemudian
insert X menggantikan 22.
Proses berlanjut sampai Pass 6. Hasil tiap pass dapat
digambarkan sebagai berikut:
|
Data awal:
|
15
|
10
|
7
|
22
|
17
|
5
|
12
|
|
|
0
|
1
|
2
|
3
|
4
|
5
|
6
|
||
|
Pass 1:
|
10
|
15
|
7
|
22
|
17
|
5
|
12
|
|
|
0
|
1
|
2
|
3
|
4
|
5
|
6
|
||
|
Pass 2:
|
7
|
10
|
15
|
22
|
17
|
5
|
12
|
|
|
0
|
1
|
2
|
3
|
4
|
5
|
6
|
||
|
Pass 3:
|
7
|
10
|
15
|
22
|
17
|
5
|
12
|
|
|
0
|
1
|
2
|
3
|
4
|
5
|
6
|
||
|
Pass 4:
|
7
|
10
|
15
|
17
|
22
|
5
|
12
|
|
|
0
|
1
|
2
|
3
|
4
|
5
|
6
|
||
|
Pass 5:
|
5
|
7
|
10
|
15
|
17
|
22
|
12
|
|
|
0
|
1
|
2
|
3
|
4
|
5
|
6
|
||
|
Pass 6:
|
5
|
7
|
10
|
12
|
15
|
17
|
22
|
|
|
0
|
1
|
2
|
3
|
4
|
5
|
6
|
||
Selesai array L
sudah terurut secara Ascending (menaik)
Pseudocode Algoritma Insertion
Sort secara Ascending :
|
1. //prosedur algoritma Insertion Sort secara Ascending
|
2. //I.S:array sudah berisi nilai integer yang belum terurut
3. //F.S:nilai-nilai dalam array terurut secara Ascending
4. procedure v_inAsc(input/output A:array[0..6]of integer,
input N:integer)
5. KAMUS:
6. k,X,i:integer7. 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
Output yang dihasilkan:
- Algorithm Data Structures and Problem Solving
with C++. 1997. Addison Wesley.
- Moh. Sjukani, Algoritma dan Struktur Data.
Mitra Wacana Media
- Inggriani Liem, Diktat Catatan Singkat Bahasa
C Agustus 2003. ITB
- Inggriani Liem, Diktat Kuliah Dasar
Pemrograman April 2007. ITB
- Rinaldi Munir, Algoritma dan Pemrograman.
Informatika Bandung
- Schaum, Programming with C++ 2nd. 2000. McGraw-Hill
- Schaum. Teach yourself C++ in 21 days. 2007.
McGraw-Hill
- http://www.cs.aau.dk/~normark/prog3-03/html/notes/paradigms_themes-paradigms.html akses
pada 18 Juli 2009 14.00
- http://encyclopedia.thefreedictionary.com/Programming%20paradigm akses
pada 18 Juli 2009 14.00
1.4 SHELL SORT (METODE SHELL)
Metode ini disebut juga dengan metode pertambahan menurun
(diminishing increment). Metode ini dikembangkan oleh Donald L. Shell pada
tahun 1959, sehingga sering disebut dengan Metode Shell Sort. Metode ini
mengurutkan data dengan cara membandingkan suatu data dengan data lain yang
memiliki jarak tertentu, kemudian dilakukan penukaran bila diperlukan. Proses
pengurutan dengan metode Shell dapat dijelaskan sebagai berikut :
Pertama-tama adalah menentukan jarak mula-mula dari data yang
akan dibandingkan, yaitu N / 2. Data pertama dibandingkan dengan data dengan
jarak N / 2. Apabila data pertama lebih besar dari data ke N / 2 tersebut maka
kedua data tersebut ditukar. Kemudian data kedua dibandingkan dengan jarak yang
sama yaitu N / 2. Demikian seterusnya sampai seluruh data dibandingkan sehingga
semua data ke-j selalu lebih kecil daripada data ke-(j + N / 2).
Pada proses berikutnya, digunakan jarak (N / 2) / 2 atau N / 4. Data pertama dibandingkan dengan data dengan jarak N / 4. Apabila data pertama lebih besar dari data ke N / 4 tersebut maka kedua data tersebut ditukar. Kemudian data kedua dibandingkan dengan jarak yang sama yaitu N / 4. Demikianlah seterusnya hingga seluruh data dibandingkan sehingga semua data ke-j lebih kecil daripada data ke-(j + N / 4).
Pada proses berikutnya, digunakan jarak (N / 4) / 2 atau N / 8. Demikian seterusnya sampai jarak yang digunakan adalah 1.
Pada proses berikutnya, digunakan jarak (N / 2) / 2 atau N / 4. Data pertama dibandingkan dengan data dengan jarak N / 4. Apabila data pertama lebih besar dari data ke N / 4 tersebut maka kedua data tersebut ditukar. Kemudian data kedua dibandingkan dengan jarak yang sama yaitu N / 4. Demikianlah seterusnya hingga seluruh data dibandingkan sehingga semua data ke-j lebih kecil daripada data ke-(j + N / 4).
Pada proses berikutnya, digunakan jarak (N / 4) / 2 atau N / 8. Demikian seterusnya sampai jarak yang digunakan adalah 1.
Algoritma metode Shell dapat dituliskan sebagai berikut :
1. Jarak = N
2. Selama (Jarak > 1) kerjakan baris 3 sampai dengan 9
3. Jarak = Jarak / 2. Sudah = false
4. Kerjakan baris 4 sampai dengan 8 selama Sudah = false
5. Sudah = true
6. j = 0
7. Selama (j < N – Jarak) kerjakan baris 8 dan 9
8. Jika (Data[j] > Data[j + Jarak] maka tukar Data[j],
Data[j + Jarak].
Sudah = true
9. j = j + 1
2. Selama (Jarak > 1) kerjakan baris 3 sampai dengan 9
3. Jarak = Jarak / 2. Sudah = false
4. Kerjakan baris 4 sampai dengan 8 selama Sudah = false
5. Sudah = true
6. j = 0
7. Selama (j < N – Jarak) kerjakan baris 8 dan 9
8. Jika (Data[j] > Data[j + Jarak] maka tukar Data[j],
Data[j + Jarak].
Sudah = true
9. j = j + 1
Di bawah ini merupakan prosedur yang menggunakan metode Shell:
|
void ShellSort(int N)
{ int Jarak, i, j; bool Sudah; Jarak = N; while(Lompat > 1) { Jarak = Jarak / 2; Sudah = false; while(!Sudah) { Sudah = true; for(j=0; j<N-Jarak; j++) { i = j + Jarak; if(Data[j] > Data[i]) { Tukar(&Data[j], &Data[i]); Sudah = false; } } } } } |
1.5 MERGE SORT
MergeSort adalah algoritma yang berdasarkan strategi
divide-and-conquer. Algoritma ini tediri dari dua bagian utama, yaitu
bagian pembagian list menjadi sublist-sublist yang lebih kecil dan bagian sort
(pengurutan) dan merge (penggabungan) pada sublist-sublist tersebut.
1) Divide:
membagi masalah menjadi beberapa submasalah yang memiliki kemiripan dengan
masalah semula namun berukuran lebih kecil (idealnya berukuran hampir sama),
2) Conquer: memecahkan
(menyelesaikan) masing-masing submasalah (secara rekursif), dan
3) Combine: mengabungkan
solusi masing-masing submasalah sehingga membentuk solusi masalah semula.
Skema Umum Algoritma Divide
and Conquer
|
procedure DIVIDE_and_CONQUER(input n : integer)
{ Menyelesaikan masalah dengan algoritma D-and-C.
Masukan: masukan yang berukuran n
Keluaran: solusi dari masalah semula }
Deklarasi
r, k : integer
Algoritma
if n £ n0 then {ukuran masalah sudah cukup kecil
}
SOLVE upa-masalah yang berukuran n
ini
else
Bagi menjadi r upa-masalah,
masing-masing berukuran n/k
for masing-masing dari r upa-masalah do
DIVIDE_and_CONQUER(n/k)
endfor
COMBINE solusi dari r upa-masalah
menjadi solusi masalah semula }
Endif
|
|
|
Diberikan sebuah array dengan elemen yang terdefinisi adalah
sebagai berikut :
[ 6, 19, 2, 45, 33, 12 ]. Cari nilai max dan min dalam array
[ 6, 19, 2, 45, 33, 12 ]. Cari nilai max dan min dalam array
Algoritma Bila diselesaikan secara divide and conquer
|
Procedure MinMax(input A : TabelInt, awal, akhir : int; output
min, max : int)
min1, min2, max1, max2, k : int;
if ( awal=akhir ) then min <- awal max<- akhir else if (awal = akhir-1) then min <- Aawal max <-Aakhir else min <- Aakhir max <- Aawal else k <- (awal+akhir) div 2 MinMax ( A, awal, k, min1, max1); MinMax (A, k+1, akhir, min2, max2); If ( min1 < min2 ) then Min <- min1 Else Min <- min2 If ( max1 > max2 ) then Max <- max1 Else Max <- max2 |
Algoritma Merge Sort
Merge Sort (A,p,r)
Dimana A = lariknya
P= Posisi Indeks 1
r : posisi indeks 2
qß(p+r)/2
T(n) = 2
Merge Sort
(A,p,r)
n
if p < r then
1
q¬(p+r)/2
(n/2)
Merge-Sort(A, p,
q)
T(n/2)
Merge-Sort(A, q+1,
r)
(divide + (n/2)
Merge(A, p, q,
r)
combine (O) karena linear.
Contoh program merge sort dalam pascal
type INTARRAY = array[1..100000] of integer;
procedure gen_array(var A:INTARRAY; N:integer);
var i:integer;
begin
for i:=1 to N do A[i]:=Random(10*N);
end;
var i:integer;
begin
for i:=1 to N do A[i]:=Random(10*N);
end;
{copia l’array X in Y}
procedure copy_array(var X, Y:INTARRAY; n:integer);
var i:integer;
begin
for i := 0 to N do Y[i] := X[i];
end;
procedure copy_array(var X, Y:INTARRAY; n:integer);
var i:integer;
begin
for i := 0 to N do Y[i] := X[i];
end;
function min(a,b:integer):integer;
begin if a
else min := b;
end;
begin if a
else min := b;
end;
procedure print_array(var A:INTARRAY; N:integer);
var i:integer;
begin
for i:=1 to min(n, 100) do
begin
write(A[i]:6);
if ((i mod 10)= 0) then writeln;
end;
if (n>100) then writeln(‘……’); //writeln(‘array troppo lungo da scrivere’);
end;
var i:integer;
begin
for i:=1 to min(n, 100) do
begin
write(A[i]:6);
if ((i mod 10)= 0) then writeln;
end;
if (n>100) then writeln(‘……’); //writeln(‘array troppo lungo da scrivere’);
end;
procedure InsSort(var A: INTARRAY; N: integer);
var i, j, t, indM: integer;
begin {Insertion Sort }
for i := 1 to N-1 do
begin
indM:=i;
for j:=i+1 to N do
if A[j]
t:= A[i];
A[i]:=A[indM];
A[indM] := t;
end;
end;
var i, j, t, indM: integer;
begin {Insertion Sort }
for i := 1 to N-1 do
begin
indM:=i;
for j:=i+1 to N do
if A[j]
t:= A[i];
A[i]:=A[indM];
A[indM] := t;
end;
end;
procedure Merge (var A: INTARRAY; p, q, r: integer);
var i, j, k: integer;
var B: INTARRAY;
begin { Merge }
i := p;
j := q + 1;
k := p;
while ((i <= q) and (j <= r)) do
begin
if (A[i] < A[j])
then begin
B[k] := A[i];
i := i + 1;
end
else begin
B[k] := A[j];
j := j + 1;
end;
k := k + 1;
end;
while (i <= q) do
begin
B[k] := A[i];
k := k + 1;
i := i + 1;
end;
while (j <= r) do
begin
B[k] := A[j];
k := k + 1;
j := j + 1;
end;
for k := p to r do A[k] := B[k];
end;
var i, j, k: integer;
var B: INTARRAY;
begin { Merge }
i := p;
j := q + 1;
k := p;
while ((i <= q) and (j <= r)) do
begin
if (A[i] < A[j])
then begin
B[k] := A[i];
i := i + 1;
end
else begin
B[k] := A[j];
j := j + 1;
end;
k := k + 1;
end;
while (i <= q) do
begin
B[k] := A[i];
k := k + 1;
i := i + 1;
end;
while (j <= r) do
begin
B[k] := A[j];
k := k + 1;
j := j + 1;
end;
for k := p to r do A[k] := B[k];
end;
procedure MergeSort (var A: INTARRAY; p, r: integer);
var q: integer;
begin { MergeSort }
if (p < r) then
begin
q := (p + r) div 2;
MergeSort (A, p, q);
MergeSort (A, q + 1, r);
Merge (A, p, q, r);
end;
end.
var q: integer;
begin { MergeSort }
if (p < r) then
begin
q := (p + r) div 2;
MergeSort (A, p, q);
MergeSort (A, q + 1, r);
Merge (A, p, q, r);
end;
end.
Implementasi Merge Sort :
|
#include <stdio.h>
|
#include <stdlib.h>
#include <string.h>
void printv(char* in, int *v, int n) {
printf(“%s”, in);
int i = 0;
for (; i < n; ++i)
printf(“%d “, v[i]);
printf(“\n”);
void merge(int *v, int p, int q, int r) {
int i = p;
int j = q + 1;
int *tmp = (int*)malloc((r – p + 1) * sizeof(int));
int k = 0;
while ((i <= q) && (j <= r)) {
if (v[i] < v[j])
tmp[k++] = v[i++];
else
tmp[k++] = v[j++];
}
while (i <= q)
tmp[k++] = v[i++];
while (j <= r)
tmp[k++] = v[j++];
memcpy(v + p, tmp, (r – p + 1) * sizeof(int));
free(tmp);
}
void mergeS(int *v, int p, int r) {
if (p < r) {
int q = (p + r) / 2;
mergeS(v, p, q);
mergeS(v, q + 1, r);
merge(v, p, q, r);
}
}
int main(int argc, char *argv[]) {
int n = 10;
int v[] = {9, 8, 7, 6, 5, 5, 4, 3, 2, 1};
printv(“V: “, v, n);
mergeS(v, 0, n – 1);
printv(“V: “, v, n);
return 0;
}
Output :
1.6 RADIX SORT
Radix Sort adalah metode sorting tanpa pembandingan dengan kata
lain, sorting Non-Comparasion sort dimana dalam prosesnya tidak melakukan
perbandingan antar data. Secara umum yang proses yang dilakukan dalam metode
ini adalah mengklasifikasikan data sesuai dengan kategori terurut yang tertentu
dan dalam tiap kategorinya dilakukan pengklasifikasian lagi dan seterusnya
sesuai dengan kebutuhan. Dan kemudian subkategori-subkategori tersebut
digabungkan kembali, yang secara dilakukan hanya dengan metode sederhana
concatenation.
Apa itu Radix Sort??? Radix Sort merupakan algoritma pengurutan
yang ajaib yang mana mengatur pengurutan nilainya tanpa melakukan beberapa
perbandingan pada data yang dimasukkan. Kata radix bermakna harafiah posisi
dalam angka [1]. Di mana sederhananya, dalam representasi desimal, radix adalah
digitnya. Dalam implementasinya, Radix Sort merupakan algoritma pengurutan yang
cepat, mudah, dan sangat efektif. Namun banyak orang yang berpikir bahwa
algoritma ini memiliki banyak batasan di mana untuk kasus-kasus tertentu tidak
dapat dilakukan dengan algoritma ini, seperti pengurutan bilangan pecahan dan
bilangan negatif,
Berdasarkan urutan pemrosesan radixnya, Radix Sort terbagi 2
macam, yaitu: LSD (Least Significant Digit), di mana pemrosesan dimulai dari
radix yang paling tidak signifikan. dan MSD (Most Significant Digit), di mana
pemrosesan dimulai dari radix yang paling signifikan.
Proses dasar Radix Sort adalah mengkategorikan data-data menjadi
subkumpulan-subkumpulan data sesuai dengan nilai radix-nya, mengkonkatenasinya,
kemudian mengkategorikannya kembali berdasar nilai radix lainnya.
Dibawah ini adalah syntax Radix Sort:
|
#include
|
#include
main()
{
int a, b, leng, data[100], d, m, temp[100], index;
printf(“Banyak data : “);
scanf(“%d”,&leng);
for (a=0;a
{
printf(“data %d = “,a+1);
scanf(“%d”,&d);
if (d<1000) { data[a]=d; } else a–; }
printf(“\nData Anda: “); for (a=0;a {
printf(“\nData %d= %d “,a+1,data[a]); } index=0; for
(a=0;a<=9;a++) //lsb sort for (b=0;b { if (data[b]<100) { m=data[b]%10; }
else { m=data[b]%100; m=m%10; } if (m==a) { temp[index]=data[b]; index++; } }
for (a=0;a<=9;a++) { data[a]=temp[a]; } index=0; for (a=0;a<=9;a++) //csb
sort for (b=0;b { if (data[b]<100) { m=data[b]/10; } else { m=data[b]%100;
m=m/10; } if (m==a) { temp[index]=data[b]; index++; } } for (a=0;a<=9;a++) {
data[a]=temp[a]; } index=0; for (a=0;a<=9;a++) //msb sort for (b=0;b {
m=data[b]/100; if (m==a) { temp[index]=data[b]; index++; } } for
(a=0;a<=9;a++) { data[a]=temp[a]; } printf(“\n\nSetelah di Sorting\n”); for
(a=0;a<(leng);a++) { printf(“%d”,data[a]); printf(“\n”); } }
1.7 METODE QUICK
SORT
Quick Sort adalah metode pengurutan data yang dikemukan pertama
kali oleh C.AR Hoare pada tahun 1962. Metode ini menggunakan strategi “pecah-pecah”
dengan mekanisme seperti berikut : Larik L[p..r] (dengan indeks terkecil adalah
p dan indeks terbesar yaitu r) disusun ulang (dipartisi) menjadi dua buah larik
A[p..q] dan A[q+1..r] sehingga setiap elemen dalam A[q+1..r]. Selanjutnya kedua
larik tersebut diurutkan secara rekursif. Dengan sendirinya kombinasi kedua
larik tersebut membentuk larik dengan data yang telah urut.
Implementasi quick sort dapat dilihat di bawah ini.
Algoritma :
SUBRUTIN quick_sort (L,p,r]
JIKA p <– partisi (L,p,r)
Quick_sort (L,p,r)
Quick_sort (L,q+1,r)
AKHIR – JIKA
AKHIR – SUBRUTIN
Untuk mengurutkan isi keseluruhan larik L, diperlukan
pemanggilan seperti berikut :
Quick_sort (L,0,jumlah_elemen(L)-1)
Subrutin partisi sendiri seperti berikut :
SUBRUTIN partisi (L,p,r)
x <– L[p]
i <– p
j <– r
ULANG SAMPAI BENAR
ULANG SELAMA L[j] > x
j <– j – i
AKHIR – ULANG
ULANG SELAMA L[I] < x
i<–i +1
AKHIR-ULANG
JIKA i<j MAKA
//Tukarkan L[i] dengan L[j]
tmp=L[i]
L[i] <– L[j]
L[j]<–tmp
SEBALIKNYA
NILAI – BALIK j
AKHIR-JIKA
AKHIR-ULANG
AKHIR-SUBRUTIN
Pertama-tama x <– L[q] dipakai untuk membagi larik L[p..r]
menjadi dua bagian (disebut pemartisian) dengan kondisi semua elemen bagian
kiri selalu lebih kecil daripada nilai elemen pivot dan nilai semua elemen
bagian kanan selalu lebih kecil daripada nilai elemen pivot. Pemartisian
dilakukan dengan menggunakan varibel i dan j. Dalam hal ini i berupa petunjuk
yang bergerak naik, sedangkan j adalah penunjuk bergerak turun. Variabel j
bergeser turun secara terus-menerus sehingga L[j]<= elemen pivot, sedangkan
i digeser naik secara terus-menerus sampai memenuhui kondisi L[j] >= elemen
pivot. Proses pengulangan dilakukan sampai nilai i >= j. Pada keadaan
seperti ini nilai balik subrutin partisi berupa j.
Implementasi ke dalam bahasa c++
|
#include <iostream.h>
#include <conio.h>
void tampilkan_larik(int data[], int n)
{
int i;
for (i=0;i<n;i++)
cout<<data[i]<<” “;
cout<<“\n”;
}
int partisi (int data[], int p, int r)
{
int x,i,j,tmp;
x=data[p];
i=p;
j=r;
while(1)
{
while(data[j]>x)
j=j-1;
while(data[i]<x)
i=i+1;
if (i<j)
{
//tukarkan data
tmp=data[i];
data[i]=data[j];
data[j]=tmp;
}
else
return j;
}
}
void quick_sort(int data[], int p, int r)
{
int q;
if(p<r)
{
q=partisi(data,p,r);
quick_sort(data,p,q);
quick_sort(data, q+1,r);
}
}
int main()
{
const jum_data=9;
int i;
int data[]={25,57,48,37,12,92,80,33,1};
cout<<“Data sebelum diurut: “<<endl;
for(int ctr=0; ctr<9; ctr++)
{
cout<<data[ctr]<<” “;
}
quick_sort(data,0,jum_data-1);
//hasil pengurutan
cout<<endl;
cout<<endl;
cout<<“hasil pengurutan:\n”;
tampilkan_larik(data,jum_data);
getch();
|
1.8 HEAP SORT
Metode heap sort adalah metode dari pengembangan tree. Heap sort
memiliki kecepatan O(NlogN). Heap sort melakukan suatu pengurutan menggunakan
suatu struktur data yang di sebut heap. Heap memiliki kompleksitas yang besar
dalam pembuatan kodenya, tetapi heap sort mampu mengurutkan data-data yang
sangat banyak dengan waktu yang cepat. Dalam sorting biasanya mempunyai sebuah
aturan, berikut adalah aturan dari heap sort :
- Untuk mengisikan heap dimulai dari level 1
sampai ke level dibawahnya, bila dalam level yang sama semua kunci heap
belum terisi maka tidak boleh mengisi dibawahnya.
- Heap dlm kondisi terurut apabila left child
<> parent.
- Penambahan kunci diletakkan pada posisi
terakhir dari level dan disebelah kanan child yg terakhir, kemudian
diurutkan dengan cara upheap.
- Bila menghapus heap dgn mengambil kunci pada
parent di level 1 kemudian digantikan posisi kunci terakhir, selanjutnya
disort kembali metode downheap.
- Berikut adalah langkah-langkahnya dari metode
heap sort :
Dalam langkah-langkahnya heap sort terbagi menjadi 2 langkah
yaitu insert_heap dan build_heap,
Insert_heap :
Pada bagian ini bertujuan untuk penghapusan suatu simpul pada
heap tree. pemilihan sebuah simpul untuk ditempatkan di posisi yang lebih atas,
dan menjaga tree tersebut tetap sebuah heaptree.
Berikut langkahnya :
- Setiap simpul yang dihapus(low) dicari anaknya
yang memiliki kunci terbesar/terkecil(large)
- Anak dengan kunci yang lebih besar
dipromosikan ke tempat simpul yang di hapus.
Langkah 1 dan 2 akan di lakukan berulang kali sampai simpul yang
dihapus tidak punya anak lagi atau simpul yang ingin dipromosikan lebih
besar/kecil daripada anak dari simpul yang dihapus yang memiliki kunci
terbesar/terkecil.
Build Heap :
Pada bagian ini kita akan merapikan data-data yang telah acak
tadi, sehingga membentuk heap yang sempurna. kita dapat menggunakan fungsi
insert_heap untuk memasukkan setiap masukan ke bagian heap yang terdiri dari
semua masukan yang masuk. Sehingga jadilah heap yang sempurna.
Analisis heap sort :
Pseudocode :
Insert heap :
procedure Max-Heapify(A, i)
**turn almost-heap into a heap
**pre-condition: tree rooted at A[i] is almost-heap
**post-condition: tree rooted at A[i] is a heap
lc leftchild(i)
rc rightchild(i)
if lc _ heapsize(A) and A[lc] > A[i] then
largest lc
else
largest i
if rc _ heapsize(A) and A[rc] > A[largest] then
largest rc
if largest 6= i then
exchange A[i] $ A[largest]
Max-Heapify(A, largest)
Build heap :
procedure Build-Max-Heapify(A)
**turn an array into a heap
heapsize(A) length[A]
for i
_length[A]
2
_
downto 1
do Max-Heapify(A, i)
Main heap sort :
procedure Heapsort(A)
**post-condition: sorted array
Build-Max-Heap(A)
for i length[A] downto 2 do
exchange A[1] $ A[i]
heapsize(A) heapsize(A) − 1
Max-Heapify(A, 1)
Contoh program heap sort :
|
#include<stdio.h>
|
#include<conio.h>
#include<stdlib.h>
//—————————————————————————
typedef struct heap
{
int val;
struct heap *left,*right;
}*TR;
//—————————————————————————
TR new_node()
{
TR new;
new=malloc(sizeof(struct heap));
new->left=new->right=NULL;
return(new);
}
//—————————————————————————
TR get_node()
{
TR new;
new=new_node();
printf(“\n\n\t Masukkan angka :: “);
scanf(“%d”,&new->val);
return(new);
}
//—————————————————————————
void insert_node(TR temp,TR new)
{
if(temp->val>new->val)
if(temp->left!=NULL)
insert_node(temp->left,new);
else
temp->left=new;
else
if(temp->right!=NULL)
insert_node(temp->right,new);
else
temp->right=new;
}
//—————————————————————————
void heap_sort(TR temp)
{
if(temp!=NULL)
{
heap_sort(temp->left);
printf(“%d\t”,temp->val);
heap_sort(temp->right);
}
}
//—————————————————————————
TR create()
{
TR head,new,temp;
char c;
head=new_node();
new=get_node();
head->left=new;
printf(“\n\n\t Tambah angka lainnya (Y/N) :: “);
c=getche();
while(c==’y’||c==’Y’)
{
new=get_node();
insert_node(head->left,new);
printf(“\n\n\t Tambah angka lainnya (Y/N) :: “);
c=getche();
}
return(head);
}
//—————————————————————————
void main()
{
TR head;
int choice;
textcolor(10);
while(1)
{
clrscr();
printf(“\n\n\t ******* MENU *******”);
printf(“\n\n\t 1> READ LIST”);
printf(“\n\n\t 2> HEAP SORT”);
printf(“\n\n\t 3> KELUAR”);
printf(“\n\n\t PILIH :: “);
scanf(“%d”,&choice);
switch(choice)
{
case 1:head=create();
break;
case 2:printf(“\n\n\t YANG UDAH DI SORTING :: “);
printf(“\n\n\t “);
heap_sort(head->left);
break;
case 3:printf(“\n\n\t TEKAN ESC KEY UNTUK KELUAR”);
if(getch()==27)
exit(0);
break;
}
getch();
}
}
0 komentar:
Posting Komentar