selection sort - informatika.unsyiah.ac.idinformatika.unsyiah.ac.id/tfa/ds/selectionsort.pdf ·...
TRANSCRIPT
Selection SortMetode selection sort merupakan perbaikan dari metode bubble sort dengan
mengurangi jumlah perbandingan. Selection sort merupakan metode pengurutan dengan mencari nilai data terkecil dimulai dari data diposisi 0 hingga diposisi N-1. Jika terdapat N data dan data terkoleksi dari urutan 0 sampai dengan N-1 maka algoritma pengurutan dengan metode selection sort adalah sebagai berikut:
1. Cari data terkecil dalam interval j = 0 sampai dengan j = N-1
2. Jika pada posisi pos ditemukan data yang terkecil, tukarkan data diposisi pos dengan data di posisi i jika k.
3. Ulangi langkah 1 dan 2 dengan j = j+i sampai dengan j = N-1, dan seterusnya sampai j = N - 1.
Bila diketahui data awal berupa: 44 55 12 42 94 18 6 67, maka langkah per langkah pengurutan dengan metode selection sort adalah sebagai berikut:
Tabel 2. Langkah demi langkah pengurutan dengan metode selection sort.
44 55 12 42 94 18 06 67 Data Awal
06 55 12 42 94 18 44 67 Tukarkan data ke 1 dengan data ke 7
06 12 55 42 94 18 44 67 Tukarkan data ke 2 dengan data ke 3
06 12 18 42 94 55 44 67 Tukarkan data ke 3 dengan data ke 6
06 12 18 42 94 55 44 67 Data ke 4 tidak ditukarkan
06 12 18 42 44 55 94 67 Data ke 5 ditukarkan dengan data ke 7
06 12 18 42 44 55 94 67 Data ke 6 tidak ditukarkan
06 12 18 42 44 55 67 94 Data ke 7 ditukarkan dengan data ke 8
06 12 18 42 44 55 67 94 Data setelah terurut
Berikut implementasi dari metode selection sort dengan menggunakan bahasa C: void selectionsort(int arr[]) { int i,j; for (i = 0; i < N; i++) { int min = arr[i]; int pos = i; for (j = i; j < N; j++) { /* Cari nilai yang terkecil */ if (arr[j] < min) { min = arr[j]; pos = j; } } /* Tukar nilai terkecil ke arr[i] jika pos tdk sama i */ if(i!=pos) { int temp = arr[i];
Struktur Data 1Author: Taufik Fuadi Abidin, M.Tech Ph.D
arr[i] = arr[pos]; arr[pos] = temp; } }}
Insertion SortMetode pengurutan selection sort sering dipakai oleh orang saat bermain kartu
bridge dalam mengurutkan kartunya, yaitu dengan cara menyisip kartu yang lebih kecil ke urutan sebelum posisi kartu yang dibandingkannya. Perhatikan tabel berikut.
Tabel 3. Langkah demi langkah pengurutan dengan metode insertion sort.
67 33 21 84 49 50 75 Data awal
67 33 21 84 49 50 75 Inisialisasi data 1
33 67 21 84 49 50 75 Bandingkan data ke 2 dengan data ke 1. Tukar bila data yang dibanding lebih kecil dari data sebelumnya
21 33 67 84 49 50 75 Bandingkan data ke 3 dengan data ke 2 dan 1. Tukar bila data yang dibanding lebih kecil dari data sebelumnya
21 33 67 84 49 50 75 Bandingkan data ke 4 dengan data ke 3, 2 dan 1. Tukar bila data yang dibanding lebih kecil dari data sebelumnya
21 33 49 67 84 50 75 Bandingkan data ke 5 dengan data ke 4, 3, 2 dan 1. Tukar bila data yang dibanding lebih kecil dari data sebelumnya
21 33 49 50 67 84 75 Bandingkan data ke 6 dengan data ke 5, 4, 3, 2 dan 1. Tukar bila data yang dibanding lebih kecil dari data sebelumnya
21 33 49 50 67 75 84 Bandingkan data ke 7 dengan data ke 6, 5, 4, 3, 2 dan 1. Tukar bila data yang dibanding lebih kecil dari data sebelumnya
Berikut implementasi dari metode insertion sort dengan menggunakan bahasa C:
void insertionsort(int arr[]) { int i,j; for (i = 1; i < N; i++) { int temp = arr[i]; int pos = i; for (j = i; j > 0; j--) { if (temp < arr[j-1]) { arr[j] = arr[j-1]; pos--; } } arr[pos]=temp; }}
Struktur Data 2Author: Taufik Fuadi Abidin, M.Tech Ph.D