SelectionSort

Selection sort adalah tehnik pengurutan dengan cara memilih elemen atau proses kerja dengan cara memilih elemen terkecil untuk kemudian dibandingkan & ditukarkan dengan elemen data awal dab seterusnya sampai dengan seluruh elemen,sehingga akan menghasilkan pola data yang telah di sort.

Selection Sort berbeda dengan Bubble sort. Selection Sort pada dasarnya memilih data yang akan diurutkan menjadi dua bagian, yaitu bagaian yang sudah diurutkan dan bagian yang belum di urutkan.
Langkah pertama dicari data terkecil dari data pertama sampai data terakhir. Kemudian data terkecil ditukar dengan data pertama. Dengan demikian, data pertama sekarang mempunyai nilai paling kecil dibanding data yang lain. Langkah kedua, data terkecil kita cari mulai dari data kedua sampai terakhir. Data terkecil yang kita peroleh ditukar dengan data kedua dan demikian seterusnya sampai semua elemen dalam keadaan terurutkan. Metode ini lebih efektif dari pada metode Bubble karena tidak memerlukan banyak pertukaran dan pengalokasian memori.

Penerapan Algoritma SelectionSort:
#include <iostream>
#include <cstdio>
using namespace std;
void cetak(int *array,int length) //print array elements
{
int i=0;
for(i=0;i<length;i++)
cout<<array[i] << ” ” ;
cout << endl;
}
void selectionSort(int *arr,int n)//Bubble sort function
{
int i,j,minindex,tmp;
for(i=0;i<n-1;i++)
{
minindex=i;
for(j=i+1;j<n;j++)
if(arr[j] < arr[minindex])minindex=j;
if (minindex != i) {
tmp = arr[i];
arr[i] = arr[minindex];
arr[minindex] = tmp;
}
}
}
int main()
{
int a[]={9,6,5,23,2,66,14,8,2,7,1,8};   // array to sort
cetak(a,12);               // print elements
selectionSort(a,12);                 //call to bubble sort
cetak(a,12);               // print elements
return 0;
}

MergeSort

MergeSort adalah Metode pengurutan lanjut, sama dengan metode QuickSort. Metode ini juga menggunakan konsep devide and conquer yang membagi data S dalam dua kelompok yaitu S1 dan S2yang tidak beririsan (disjoint). Proses data dilakukan secara rekursif sampai data tidak dapat dibagi lagi atau dengan kata lain data dalam sub bagian menjadi tunggal.
Setelah data tidak dapat dibagi, proses penggabungan (Merging) dilakukan antara sub-sub bagian dengan memeperhatikan urutan data yang diinginkan (Ascending atau Descending). Proses penggabungan ini dilakukan sampai semua data tergabung dan terurut sesuai urutan yang diinginkan kompleksitas Algoritma MergeSort adalah O(n log n).

Penerapan Algoritma MergeSort: 

#include <iostream>
#include <cstdio>
using namespace std;
void cetak(int *array,int length) //print array elements
{
int i=0;
for(i=0;i<length;i++)
cout<<array[i] << ” ” ;
cout << endl;
}
void merge(int *arr, int size1, int size2) {
int temp[size1+size2];
int ptr1=0, ptr2=0;
int *arr1 = arr, *arr2 = arr+size1;
while (ptr1+ptr2 < size1+size2) {
if (ptr1 < size1 && arr1[ptr1] <= arr2[ptr2]
|| ptr1 < size1 && ptr2 >= size2)
temp[ptr1+ptr2] = arr1[ptr1++];
if (ptr2 < size2 && arr2[ptr2] < arr1[ptr1]
|| ptr2 < size2 && ptr1 >= size1)
temp[ptr1+ptr2] = arr2[ptr2++];
}
for (int i=0; i < size1+size2; i++)
arr[i] = temp[i];
}
void mergeSort(int *arr, int size) {
if (size == 1)
return;
int size1 = size/2, size2 = size-size1;
mergeSort(arr, size1);
mergeSort(arr+size1, size2);
merge(arr, size1, size2);
}
int main()
{
int a[]={9,6,5,23,2,66,14,8,2,7,1,8};   // array to sort
cetak(a,12);               // print elements
mergeSort(a,12);                 //call to bubble sort
cetak(a,12);               // print elements
return 0;
}

BubbleSort

BubbleSort adalah salah satu algoritma untuk sorting data, 

atau mengurutkan data dari yang terbesar ke yang terkecil atau 
sebaliknya (Ascending dan Descending). Algoritma BubbleSort

adalah algoritma sorting paling sederhana. Kelebihan dari 

algoritma ini adalah mudah dipahami dan yang paling simple.
Kekurangannya adalah salah satunya proses akan berhenti 

jika tidak ada pertukaran dalam satu iterasi. 

Sesuai dengan namanya proses pengurutannya mirip seperti gelembung. 

Terdapat proses pertukaran atau disebut Swapping.

Penerapan Algoritma BubbleSort: 

#include <iostream>
#include <cstdio>
using namespace std;
void cetak(int *array,int length) //print array elements
{ 
    int i=0;
    for(i=0;i<length;i++)
        cout<<array[i] << " " ;
    cout << endl;
} 

void bubbleSort(int *array,int length)//Bubble sort function 
{
    int i,j;
    for(i=0;i<length;i++)
    {
        for(j=0;j<i;j++)
        {
            if(array[i] < array[j])
            {
                int temp=array[i]; //swap 
                array[i]=array[j];
                array[j]=temp;
            }

        }
    }
}

int main()
{

    int a[]={9,6,5,23,2,66,14,8,2,7,1,8};   // array to sort 
    cetak(a,12);               // print elements
    bubbleSort(a,12);                 //call to bubble sort  
    cetak(a,12);               // print elements
    return 0; 

QuickSort

Quicksort merupakan Algoritma Sorting yang dikembangkan oleh Tony Hoare yang, secara kasus rata-rata, membuat pengurutan O(n log n) untuk mengurutkan n item. Algoritma ini juga dikenal sebagai Partition-Exchange Sort atau disebut sebagai Sorting Pergantian Pembagi. Pada kasus terburuknya, algoritma ini membuat perbandingan O(n²), malaupun kejadian seperti ini sangat langka. Quicksort sering lebih cepat dalam praktiknya dari pada algoritma O(n log n) yang lainnya. Dan juga, urutan dan referensi lokalisasi memori quicksort bekerja lebih baik dengan menggunakan cache CPU, jadi keseluruhan sorting dapat dilakukan hanya dengan ruang tambahan O(log n).
Quicksort merupakan sorting pembanding dan pada implementasi efisien tidak merupakan algoritma sorting yang stabil.

Penerapan Algoritma QuickSort:

#include <iostream>
#include <cstdio>
using namespace std;
void cetak(int *array,int length) //print array elements
{
    int i=0;
    for(i=0;i<length;i++)
        cout<<array[i] << " " ;
    cout << endl;
} 

//Function to determine the partisis
// partisis the array and returns the middle subscript
int partisi(int *array, int top, int bottom)
{
     int x = array[top];
     int i = top - 1;
     int j = bottom + 1;
     int temp;
     do
     {
           do      
           {
                  j--;
           }while (x >array[j]);

          do  
         {
                 i++;
          } while (x <array[i]);

          if (i < j)
         { 
                 temp = array[i];    
                 array[i] = array[j];
                 array[j] = temp;
         }
     }while (i < j);     
     return j;           // returns middle subscript  
}