Belajar Bahasa C : #12 Sorting
Hallo
Sobat Ambisius!!
Pada
kesempatan kali ini, kita akan mulai mempelajari penggunaan Sorting pada
bahasa C.
Sorting
merupakan suatu proses penyortiran atau pengurutan sebuah data.
Terdapat 2 macam pengurutan data pada sorting yaitu :
1. Berdasarkan ascending (kecil ke besar).
2. Berdasarkan Descending (besar ke kecil).
A. Tipe
– Tipe Sorting :
·
Bubble Sort
·
Insertion Sort
·
Selection Sort
·
Counting Sort
·
Advanced Sort
·
Quick Sort
·
Merge Sort
·
Radix Sort
·
Bucket Sort
·
Shell Sort
1. Bubble
sort
Bubble sort merupakan
algoritma pengurutan yang membandingkan dua data yang berdekatan dan menukarnya
sampai tidak dalam urutan yang diinginkan.
Cara kerja dari
Bubble Sort
Bubble sort menggunakan teknik iterasi. Iterasi merupakan proses melakukan
perulangan sebanyak data yang diketahui. Intinya pada iterasi melakukan
perbandingan antara dua data.
Misalkan kita mencoba
mengurutkan data dalam urutan kecil ke besar (Ascending).
1. Iterasi Pertama (Bandingkan dan Tukar)
Penjelasan
:
·
Mulai
dari indeks pertama, bandingkan data pertama dan kedua.
·
Jika data
pertama lebih besar dari data kedua, mereka ditukar.
Karena contoh tersebut mengurutkan data berdasarkan kecil ke besar (ascending).
·
Sekarang,
bandingkan data kedua dan ketiga. Tukarkan jika tidak berurutan.
· Proses di atas berlangsung hingga elemen terakhir.
2. Iterasi Kedua (Melanjutkan proses iterasi dari iterasi pertama)
Penjelasan
:
·
Proses iterasi kedua melanjutkan hasil dari
iterasi pertama.
· Proses pertukaran datanya pun sama saja. Jika data yang dibandingkan sudah benar maka tidak perlu terjadi pertukaran.
3. Iterasi Ketiga
·
Walaupun
sudah ke sorting iterasi tetap berlanjut
·
Karena
iterasi menyesuaikan banyaknya
data (contoh soal : 10 2 1 4 3).
·
Karena ada
5 data maka harus 5-1 = 4 kali iterasi.
·
intinya
pada iterasi membandingkan 2 data terus menerus.
4. Iterasi Keempat
·
Iterasi keempat penjelasannya sama seperti
dengan iterasi ketiga, yaitu banyaknya iterasi bergantung pada banyaknya data.
Kurang lebih seperti itu teori dari penggunaan bubble sort.
Kamu dapat mengurutkan data dari kecil ke besar (ascending) atau dari besar ke
kecil (descending). Prosesnya sama saja yaitu membandingkan dua buah data
secara terus menerus.
Contoh program Bubble sort :
#include<stdio.h>
//Melakukan pertukaran jika data tidak sesuai.
void swap(int *a, int *b){
int temp = *a;
*a = *b;
*b = temp;
}
void bubbleSort(int arr[], int N){
for(int i =0; i<N-1; i++){ //N-1 karena index dimulai dr 0.
//Melakukan looping untuk mengakses array pada setiap data.
for(int j=0; j<N-1-i; j++){
//Tanda > mengurutkan berdasarkan ascending
//Tanda < mengurutkan berdasarkan descending
if(arr[j] > arr[j+1]){
//Memanggil function swap yang berfungsi untuk menukar data.
swap(&arr[j], &arr[j+1]);
}
}
}
}
void print(int arr[], int N){
for(int i=0; i<N; i++){
printf("%d ", arr[i]);
}
}
int main(){
int arr[] = {10, 2, 1, 4, 3};
//Mencari panjang array dari data tersebut.
int N = sizeof(arr)/sizeof(arr[0]);
printf("Sebelum Sort: ");
print(arr,N);
puts("");
printf("Sesudah Sort: ");
bubbleSort(arr, N);
print(arr, N);
puts("");
return 0;
}
Penjelasan
:
·
Pada function swap tedapat 2 variabel dalam
parameter, yaitu variabel int *a dan int *b yang berfungsi sebagai dua buah
data. Terdapat juga variabel penampung yaitu int temp. Function swap berisi
pertukaran data a dengan b.
·
Pada function bubblesort berfungsi melakukan
looping dan eksekusi program bubblesort.
·
int N berfungsi sebagai ukuran array atau
banyaknya data.
·
Pada function print hanya berfungsi untuk
mencetak data.
·
Pada function main terdapat data yang ingin di
sorting. Lalu terdapat pencarian panjang array dan terdapat pemanggilan
function sehingga dapat mengeluarkan output.
Output :
2. Insertion sort
Insertion sort merupakan teknik sorting dengan cara
menyisipkan atau memasukan setiap elemen secara berulang berulang.
Konsep insertion sort bisa diibaratkan sebuah kartu. Untuk
lebih jelasnya perhatikan gambar berikut.
Contohnya kita melakukan sort berdasarkan kecil ke besar
(ascending) 4 buah data yaitu {4,7,1,2}.
Langkah pertama bandingkan nomor 4 dengan 7, karena 4 <
7 maka tidak perlu diubah.
Langkah kedua bandingkan nomor 7 dengan 1, karena 7 > 1 maka ubah posisi.
Langkah ketiga bandingkan nomor 4 dengan 1, karena 4 > 1 maka ubah posisi.
Langkah kelima bandingkan nomor 7 dengan 2, karena 7 > 2 maka ubah posisi.
Langkah keenam bandingkan nomor 4 dengan 2, karena 4 > 2 maka ubah posisi.#include<stdio.h>
void insertionSort(int *Data, int n){
int temp, j;
for (int i = 1; i <= n-1; i++){ //n-1 karena index dimulai dr 0.
temp = Data[i];
j = i-1;
//Data[j] > temp berfungsi untuk mengurutkan data secara ascending.
//Data[j] < temp berfungsi untuk mengurutkan data secara descending.
while(j>=0 && Data[j] > temp){
Data[j+1] = Data[j];
j--;
}
Data[j+1] = temp;
}
}
void print(int* Data, int n){
for (int i = 0; i < n; i++){
printf("%d ", Data[i]);
}
printf("\n");
}
int main(){
int Data[] = {4, 7, 1, 2};
//Mencari panjang array dan menyesuaikan ukuran array dari data tersebut.
int n = sizeof(Data)/sizeof(Data[0]);
printf("Sebelum Sort: ");
print(Data, n);
printf("Sesudah Sort: ");
insertionSort(Data, n);
print(Data, n);
return 0;
}
Penjelasan
:
·
Pada function Insertionsort berfungsi melakukan
looping dan eksekusi program Insertionsort.
·
int n berfungsi sebagai ukuran array atau
banyaknya data.
·
Pada function print hanya berfungsi untuk
mencetak data.
·
Pada function main terdapat data yang ingin di
sorting. Lalu terdapat pencarian panjang array dan terdapat pemanggilan
function sehingga dapat mengeluarkan output.
Output :
3. Selection Sort
Selection sort menggunakan perbandingan data, selection
sort akan membandingkan data 1 dengan lainnya dan jika menemukan data yang
terkecil maka data tersebut menjadi acuannya.
Contohnya kali ini kita akan mengerjakan teori dari
selection sort. Contoh soal diketahui
terdapat 4 buah data, dengan angka 9,7,6,1. Urutkanlah data tersebut
berdasarkan ascending.
Langkah 1 :
·
Gunakanlah data pertama yaitu 9 sebagai
acuannya, lalu bandingkan dengan data kedua yaitu 7. Karena 7 < 9 maka
sekarang 7 yang menjadi acuannya.
·
Bandingkan angka 7 dengan data selanjutnya
yaitu 6. Karena 6 < 7 maka angka 6 menjadi acuannya.
·
Kemudian bandingkan angka 6 dengan data
selanjutya yaitu 1. Karena 1 < 6 maka angka 1 menjadi acuannya.
·
Lalu tukar angka 1 dengan angka 9 yang menjadi
angka acuan awal.
Langkah 2 :
·
Bandingkan data kedua yaitu 7 dengan data
selanjutnya yaitu 6. Karena 6 < 7 maka angka 6 menjadi acuannya.
·
Kemudian tukar angka 6 dan 7.
Contoh program Selection sort :
#include <stdio.h>
//Melakukan pertukaran jika data tidak sesuai.
void swap(int *a, int *b){
int temp = *a;
*a = *b;
*b = temp;
}
void SelectionSort (int Data[ ], int n) {
// variabel sementara untuk menyimpan posisi data minimum
int min;
// mengurangi ukuran efektif array sebanyak satu di setiap iterasi.
for(int i = 0; i < n-1 ; i++) {
// anggap saja data pertama menjadi minimum dari array yang tidak disortir .
min = i ;
// memberikan ukuran efektif dari array yang tidak disortir.
for(int j = i+1; j < n ; j++ ) {
if(Data[ j ] < Data[ min ]) { //mencari data minimum
min = j ;
}
}
// meletakkan data minimum pada posisi yang tepat
swap (&Data[ min ], &Data[ i ]) ;
}
}
void print(int* Data, int n){
for (int i = 0; i < n; i++){
printf("%d ", Data[i]);
}
printf("\n");
}
int main(){
int Data[] = {9, 7, 6, 1};
//Mencari panjang array dan menyesuaikan ukuran array dari data tersebut.
int n = sizeof(Data)/sizeof(Data[0]);
printf("Sebelum Sort: ");
print(Data, n);
printf("Sesudah Sort: ");
SelectionSort(Data, n);
print(Data, n);
return 0;
}
Penjelasan
:
·
Pada function Selectionsort berfungsi melakukan
looping dan eksekusi program Selectionsort.
·
int n berfungsi sebagai ukuran array atau
banyaknya data.
·
Pada function print hanya berfungsi untuk
mencetak data.
·
Pada function main terdapat data yang ingin di
sorting. Lalu terdapat pencarian panjang array dan terdapat pemanggilan
function sehingga dapat mengeluarkan output.
Output :
0 Response to "Belajar Bahasa C : #12 Sorting"
Post a Comment