Langkah pertama yang harus dilakukan dalam algoritma atau teknik Selection Sort adalah

Sebelumnya saya sudah menceritakan mengenai Bubble Sort. Pada tulisan ini saya akan menceritakan metode pengurutan yang lainnya, yaitu selection sort. Cerita ini merupakan kontribusi dari Alfredo Pranata B, M. Alqorni, dan M. Hasbi Allah, mahasiswa angkatan 2017 Program Studi Teknik Komputer, Politeknik Caltex Riau (PCR). Tanpa mengurangi keumuman dalam penerapannya, tulisan ini hanya menceritakan proses pengurutan secara menaik (ascending).

Table of Contents Show

PENGERTIAN SORT
1.1 BUBBLE SORT
1.2 SELECTION SORT
1.2.1 Maximum Selection Sort Ascending
1.2.2 Maximum Selection Sort Descending
Output yang dihasilkan:
1.2.3 Minimum Selection Sort Ascending
Output yang dihasilkan:
1.2.4 Minimum Selection Sort Descending
1.3 INSERTION SORT
1.4 SHELL SORT (METODE SHELL)
Video yang berhubungan

Secara sederhana, metode ini menerapkan dua proses utama, yaitu:

Pilih yang paling kecil
Tukar posisi (swap)

Soal

Diberikan data awal sebagai berikut:

Indeks	0	1	2	3	4	5	6	7	8
Data	2	10	3	1	17	25	16	9	18

Data tersebut akan diurutkan secara ascending menggunakan metode selection sort.

Jawaban

Berikut ini adalah proses-proses yang terjadi saat pengurutan.

Proses 1

Pilih nilai yang paling kecil dari indeks ke-0 sampai ke-8. Didapatkan 1 pada indeks ke-3. Tukar posisi nilai ini dengan nilai pada indeks ke-0. Sehingga diperoleh hasil sebagai berikut.

Indeks	0	1	2	3	4	5	6	7	8
Data	1	10	3	2	17	25	16	9	18

Proses 2

Pilih nilai yang paling kecil dari indeks ke-1 sampai ke-8. Didapatkan 2 pada indeks ke-3. Tukar posisi nilai ini dengan nilai pada indeks ke-1. Sehingga diperoleh hasil sebagai berikut.

Indeks	0	1	2	3	4	5	6	7	8
Data	1	2	3	10	17	25	16	9	18

Proses 3

Pilih nilai yang paling kecil dari indeks ke-2 sampai ke-8. Didapatkan 3 pada indeks ke-2. Tukar posisi nilai ini dengan nilai pada indeks ke-2 (tidak ada pertukaran). Sehingga diperoleh hasil sebagai berikut.

Indeks	0	1	2	3	4	5	6	7	8
Data	1	2	3	10	17	25	16	9	18

Proses 4

Pilih nilai yang paling kecil dari indeks ke-3 sampai ke-8. Didapatkan 9 pada indeks ke-7. Tukar posisi nilai ini dengan nilai pada indeks ke-3. Sehingga diperoleh hasil sebagai berikut.

Indeks	0	1	2	3	4	5	6	7	8
Data	1	2	3	9	17	25	16	10	18

Proses 5

Pilih nilai yang paling kecil dari indeks ke-4 sampai ke-8. Didapatkan 10 pada indeks ke-7. Tukar posisi nilai ini dengan nilai pada indeks ke-4. Sehingga diperoleh hasil sebagai berikut.

Indeks	0	1	2	3	4	5	6	7	8
Data	1	2	3	9	10	25	16	17	18

Proses 6

Pilih nilai yang paling kecil dari indeks ke-5 sampai ke-8. Didapatkan 16 pada indeks ke-6. Tukar posisi nilai ini dengan nilai pada indeks ke-5. Sehingga diperoleh hasil sebagai berikut.

Indeks	0	1	2	3	4	5	6	7	8
Data	1	2	3	9	10	16	25	17	18

Proses 7

Pilih nilai yang paling kecil dari indeks ke-6 sampai ke-8. Didapatkan 17 pada indeks ke-7. Tukar posisi nilai ini dengan nilai pada indeks ke-6. Sehingga diperoleh hasil sebagai berikut.

Indeks	0	1	2	3	4	5	6	7	8
Data	1	2	3	9	10	16	17	25	18

Proses 8

Pilih nilai yang paling kecil dari indeks ke-7 sampai ke-8. Didapatkan 18 pada indeks ke-8. Tukar posisi nilai ini dengan nilai pada indeks ke-7. Sehingga diperoleh hasil sebagai berikut.

Indeks	0	1	2	3	4	5	6	7	8
Data	1	2	3	9	10	16	17	18	25

Iterasi berakhir pada indeks ke-7 sehingga diperoleh nilai yang telah terurut secara ascending.

Berdasarkan proses yang telah diceritakan tersebut, seharusnya kita dapat men-generate algoritma pengurutan menggunakan metode selection sort.

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.

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

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).

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 :

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 :

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 :

0 1 2 3 4

Pass 4 :

I = 3 ;J= N-1= 4 1 6 7 8 9

Hasil akhir langkah 4 :

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>

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 secara Ascending (menaik), dengan algoritma maximum selection sort.

Pass 1 :

Ÿ Cari elemen maksimum di dalam array L[0..4]. Maks=L[2]=12

Ÿ Tukar Maks dengan L[4], diperoleh :

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 :

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 :

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 :

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 secara Descending (menurun), dengan algoritma maximum selection sort.

Pass 1 :

Ÿ Cari elemen maksimum di dalam array L[0..4]. Maks=L[4]=12

Ÿ Tukar Maks dengan L[0], diperoleh :

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 :

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 :

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 :

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

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)
1. cari elemen minimum (min) mulai dari elemen ke – I sampai elemen ke – (N-1)
2. 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 secara Ascending (menaik), dengan algoritma minimum selection sort.

Pass 1 :

Ÿ Cari elemen terkecil di dalam array L[0..4]. Min=L[4]=1

Ÿ Tukar Min dengan L[0], diperoleh :

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 :

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 :

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 :

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

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 secara Descending (menurun), dengan algoritma minimum selection sort.

Pass 1 :

Ÿ Cari elemen terkecil di dalam array L[0..4]. Min=L[3]=7

Ÿ Tukar Min dengan L[4], diperoleh :

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 :

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 :

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 :

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

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 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.

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 6 pass proses pengurutan.

Berikut ilustrasi dari 6 pass tersebut:

Data awal:

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:

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 <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:

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.