selection sort - informatika.unsyiah.ac.idinformatika.unsyiah.ac.id/tfa/ds/selectionsort.pdf ·...

2
Selection Sort Metode 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 1 Author: Taufik Fuadi Abidin, M.Tech Ph.D

Upload: dangdiep

Post on 11-May-2019

214 views

Category:

Documents


0 download

TRANSCRIPT

Page 1: Selection Sort - informatika.unsyiah.ac.idinformatika.unsyiah.ac.id/tfa/ds/selectionsort.pdf · Selection sort merupakan metode pengurutan dengan mencari nilai data terkecil dimulai

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

Page 2: Selection Sort - informatika.unsyiah.ac.idinformatika.unsyiah.ac.id/tfa/ds/selectionsort.pdf · Selection sort merupakan metode pengurutan dengan mencari nilai data terkecil dimulai

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