Alpro & Strukdat 1 C++ (Sorting)
Dwiny Meidelfi, M.Cs
void tukar(int a, int b) { int t; t = data[b]; data[b] = data[a]; data[a] = t; } void selection_sort() { int pos,i,j; for(i=1;i<=n-1;i++) { pos = i; for(j = i+1;j<=n;j++) { if(data[j] < data[pos]) pos = j; } if(pos != i) tukar(pos,i); } }
Pengurutan (sorting)
Merupakan proses untuk menyusun kembali kumpulan entri-entri yang telah dimasukkan dengan suatu aturan tertentu. Memudahkan pengelolaan data, misalnya pencarian data. Secara umum ada 2 (dua) macam pengurutan : 1) Pengurutan secara menaik (ascenden) Misal : Array A dengan elemen N A[1] ≤ A[2] ≤ A[3] ≤ … ≤ A[N] 2) Pengurutan secara menurun (descenden) Misal : Array A dengan elemen N A[1] ≥ A[2] ≥ A[3] ≥ … ≥ A[N]
Pengurutan (sorting)
Keuntungannya : 1. Data mudah dicari (misalnya dalam buku telepon atau kamus bahasa), mudah untuk dibetulkan, dihapus, disisipi atau digabungkan. 2. Dalam keadaan terurutkan, kita mudah melakukan pengecekan apakah ada data yang hilang. 3. Mempercepat proses pencarian data yang harus dilakukan berulang kali.
Metode Sorting Metode sorting yang sering digunakan: Selection Sort Bubble Sort Insertion Sort Quick Sort Shell Sort Merge Sort dst...
Selection Sort
Adalah memilih elemen maksimum/minimum dari Larik Menempatkan elemen maksimum/ minimum tersebut pada awal/akhir larik (elemen ujung) Elemen terujung tersebut ‘diisolasi’ dan tidak disertakan pada proses selanjutnya. Proses yg sama diulang untuk elemen larik yg tersisa Memilih elemen maksimum/minimum berikutnya dan mempertukarkannya dengan elemen terujung larik sisa.
Selection Sort Langkah-langkah berikut: 1) Mulai dari indeks 0, mencari nilai terkecil pada seluruh array. 2) Tukar nilai terkecil yang ditemukan dengan nilai pada indeks 0. 3) Ulangi langkah 1 & 2 mulai dari indeks berikutnya. → menemukan elemen terkecil dalam array, dan meletakkannya di posisi pertama. Kemudian menemukan elemen terkecil berikutnya, dan meletakkannya di posisi kedua. Proses ini akan diulang sampai kita kehabisan elemen.
Selection Sort {30, 50, 20, 10, 40} → Pertama, kita menemukan elemen terkecil yaitu 10, mulai dari indeks 0: {30, 50, 20, 10, 40} → Kemudian swap 10 dengan elemen pada indeks 0 yaitu 30: {10, 50, 20, 30, 40} → Sekarang elemen pertama telah diurutkan, jadi kita bisa mengabaikannya. → Selanjutnya, kita dapat mulai menemukan elemen terkecil terkecil berikutnya, mulai dari indeks 1:
Step by step -1 Contoh diberikan sederetan array nilai, yaitu : 7
5
3
13
11
1. Mendeklarasikan array yang berisi bilangan seperti contoh di atas. int deretangka[5];
Step by step -2 Contoh diberikan sederetan array nilai, yaitu : 7
5
3
13
11
2. Mendeklarasikan bilangan counter sebagai counter perulangan. int deretangka[5]; int i,j;
Step by step -3 7
5
3
13
11
3. Mendeklarasikan perulangan yang memproses pertukaran nilai elemen dan pencarian nilai minimum.
LATIHAN 70 65 88 54 90 60 Urutkanlah nilai-nilai diatas berdasarkan ascending dan descending
void tukar(int a, int b) { int t; t = data[b]; data[b] = data[a]; data[a] = t; } void selection_sort() { int pos,i,j; for(i=1;i<=n-1;i++) { pos = i; for(j = i+1;j<=n;j++) { if(data[j] < data[pos]) pos = j; } if(pos != i) tukar(pos,i); } }
Bubblesort
Terinspirasi dari gelembung sabun (berat jenis gelembung lebih ringan dari berat jenis air) Dalam array yg terurut menaik, maka elemen larik yang paling kecil ‘diapungkan’ dengan cara diletakan keujung kiri larik melalui proses pertukaran.
Bubblesort Ide dasar dari metode ini adalah : 1. Membawa data terkecil dari data ke-1 s/d ke-n menjadi data[1]. 2. Membawa data terkecil dari data ke-2 s/d ke-n menjadi data[2]. 3. … 4. Membawa data terkecil dari data ke-(n-1) s/d ke-n menjadi data[n-1].
Step by step -1 Contoh diberikan sederetan array nilai, yaitu : 23
45
12
24
56
1. Mendeklarasikan array yang berisi bilangan seperti contoh di atas. int deretangka[5];
Step by step -2 Contoh diberikan sederetan array nilai, yaitu : 23
45
12
24
56
2. Mendeklarasikan bilangan counter sebagai counter perulangan, dan variabel temp untuk menyimpan nilai sementara, dan variabel penanda apakah masih terjadi pertukaran atau tidak. int deretangka[5]; int i,j,temp;
Step by step -3 23
45
12
24
56
3. Mendeklarasikan perulangan yang memproses pertukaran nilai elemen dan pencarian nilai minimum. 1 untuk i=0 to n kerjakan langkah 2 2 untuk j=0 to n-1 kerjakan langkah 3 3 cek apakah a[j] > a[j+1] maka tukar 4 selesai
LATIHAN 70 65 88 54 90 60 Urutkanlah nilai-nilai diatas berdasarkan ascending dan descending
void tukar(int a, int b) { int t; t = data[b]; data[b] = data[a]; data[a] = t; } void bubble_sort() { for(int i=1;i<=n;i++) { for(int j=n; j>=i; j--) { if(data[j] < data[j-1]) tukar(j,j-1); } } }
Insertion Sort
Adalah metode pengurutan dengan cara menyisipkan elemen larik pada posisi yang tepat. Pencarian posisi yg tepat dilakukan dengan menyisir larik (array). Selama penyisiran dilakukan pergeseran elemen larik. Data dicek satu per satu mulai dari yang kedua sampai dengan yang terakhir. Apabila ditemukan data yang lebih kecil daripada data sebelumnya, maka data tersebut disisipkan pada posisi yang sesuai. Analoginya sesuai dengan permainan kartu.
Insertion Sort 1. Baca vektor yang akan diurutkan 2. Kerjakan langkah 2- 5 untuk I =2 sampai N 3. Tentukan T=A[I](elemen yang akan disisipkan) A[0]=T(data sentinen ) dan J=I-1 4. Tentukan, selama T < A[J] dan j>0 kerjakan A[J+1]=A[J] dan J=J-1 End looping no.4; 5. Tentukan a[j+1)=T {untuk menempatkan elemen di posisi yang semestinya}
void tukar(int a, int b) { int t; t = data[b]; data[b] = data[a]; data[a] = t; } void insertion_sort() { int temp,i,j; for(i=1;i<=n;i++) { temp = data[i]; j = i -1; while(data[j]>temp && j>=0) { data[j+1] = data[j]; j--; } data[j+1] = temp; } }
TUGAS Buatlah program yang menyimpan nama-nama mahasiswa beserta nilai ujian praktikumnya. Kemudian urutkan nama-nama mahasiswa tersebut berdasarkan nilai ujian dari yang terendah ke yang tertinggi. → gunakan selection sort dan bubble sort.
