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 keempat cari angka berikutnya yang belum terurut.

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.

Jika data sudah berurut maka tidak ada yang perlu dibandingkan dan sorting berhasil.

Contoh program Insertion sort :

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

Share this post