Sorting dengan Metode Insertion dan Merge Sort

Insertion Sort   
Posting sebelumnya dibahas tentang Bubble Sort  dan Selection Sort, kali ini akan membahas Insertion Sort. Mirip dengan cara orang mengurutkan kartu, selembar demi selembar kartu diambil
dan disisipkan (insert) ke tempat yang seharusnya.  Pengurutan dimulai dari data ke-2 sampai dengan data terakhir, jika ditemukan data yang lebih kecil , maka akan ditempatkan ( diinsert ) diposisi yang seharusnya. Pada penyisipan elemen, maka elemen-elemen lain akan bergeser ke belakang.

Contoh dari Insertion Sort
 











Prosedur Insertion Sort
void insertion_sort(){
    int temp;
    for (int 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;
        }
}

Merge Sort
Algoritma dirumuskan dalam 3 langkah berpola divide-and-conquer. Berikut menjelaskan langkah kerja dari Merge sort. 

1. Divide  : Memilah elemen – elemen dari rangkaian data menjadi dua bagian.
2. Conquer : Conquer setiap bagian dengan memanggil prosedur merge sort secara rekursif
3. Kombinasi : Mengkombinasikan dua bagian tersebut secara rekursif untuk mendapatkan rangkaian data berurutanProses rekursi berhenti jika mencapai elemen dasar. Hal ini terjadi bilamana bagian yang akan diurutkan menyisakan tepat satu elemen. Sisa pengurutan satu elemen tersebut menandakan bahwa bagian tersebut telah terurut sesuai rangkaian.

Contoh dari Merge Sort

 

Prosedur Merge Sort
public static void mergeSort_srt(int array[],int lo, int n){
int low = lo;
int high = n;
if (low >= high) {  
    return;
     }
    int middle = (low + high) / 2;
    mergeSort_srt(array, low, middle);
    mergeSort_srt(array, middle + 1, high);
    int end_low = middle;
    int start_high = middle + 1;

    while ((lo <= end_low) && (start_high <= high)) {
          if (array[low] < array[start_high]) {
            low++;
            } else {
        int Temp = array[start_high];
        for (int k = start_high- 1; k >= low; k--) {
              array[k+1] = array[k];
        }
                array[low] = Temp;
                low++;
                end_low++;
                start_high++;
            }
        }
    }

}

SHARE THIS