This is default featured slide 1 title

Go to Blogger edit html and find these sentences.Now replace these sentences with your own descriptions.This theme is Bloggerized by Lasantha Bandara - Premiumbloggertemplates.com.

This is default featured slide 2 title

Go to Blogger edit html and find these sentences.Now replace these sentences with your own descriptions.This theme is Bloggerized by Lasantha Bandara - Premiumbloggertemplates.com.

This is default featured slide 3 title

Go to Blogger edit html and find these sentences.Now replace these sentences with your own descriptions.This theme is Bloggerized by Lasantha Bandara - Premiumbloggertemplates.com.

This is default featured slide 4 title

Go to Blogger edit html and find these sentences.Now replace these sentences with your own descriptions.This theme is Bloggerized by Lasantha Bandara - Premiumbloggertemplates.com.

This is default featured slide 5 title

Go to Blogger edit html and find these sentences.Now replace these sentences with your own descriptions.This theme is Bloggerized by Lasantha Bandara - Premiumbloggertemplates.com.

Senin, 13 April 2015

METODE PENGURUTAN ARRAY


TREE SORT

Tree sort adalah metode sorting dengan cara membangun pohon biner dengan menampilkan 3 hasil output:
PreOrder, InOrder, dan PostOrder.
Konsep dan Algoritma:
Konsep dasar dari tree sort adalah sebagaimana sebuah pohon, ada akar, batang, ranting, daun, dsb. Dalam tree sort ada istilah akar atau root dan daun atau leaf. Perhatikan gambar di atas :


Ketentuan dari gambar diatas adalah:

1. menjadi akar,
2. menjadi subtree kiri,
3. menjadi subtree kanan,
4 & 5. menjadi daun dari subtree kiri,
6. menjadi daun dari subtree kanan.

Langsung saja bisa memahami algoritmanya lewat coding di bawah ini:
    
#include "iostream"
#include "conio.h"
using namespace std;

struct Node {
  int item;          //variabel item
   Node *kiri;      //pointer ke subtree kiri
   Node *kanan;     //pointer ke subtree kanan
  };

void tambah(Node **akar,int itembaru)   //berisi pointer yang menunjuk ke pointer akar itu sendiri
  {
   if((*akar) == NULL)            //jika akar kosong maka membuat item baru      
   {
     Node *baru;                        //pointer baru
     baru = new Node;                   //new node = alamat baru
     baru->item = itembaru;   //baru di tunjuk oleh pointer item & di isi dengan item baru
     baru->kiri = NULL;       //baru ditunjuk dengan pointer kiri ,dan jika masihh kosong
     baru->kanan = NULL;  //baru ditunjuk dengan pointer kanan & jika kosong
     (*akar) = baru;         //pointer akar = variabel baru dengan alamat baru
     (*akar)->kiri = NULL;         
     (*akar)->kanan = NULL;        
     cout<<"Item bertambah!";
   }
   else if(itembaru < (*akar)->item)   tambah(&(*akar)->kiri,itembaru);       
// jika item yang ditambah di kiri 
   else if(itembaru > (*akar)->item)   tambah(&(*akar)->kanan,itembaru);       //jika item yang ditambah item ke kanan
   else if(itembaru == (*akar)->item) //jika item yang di input sama dengan item yang ditambah sebelumnya
     cout<<"Item sudah ada!";
  }
void tampil(Node *akar)     //fungsi menampilkan seluruh item yang telah di imput
  {
   if(akar != NULL){
   cout<<akar->item<<" ";      
   tampil(akar->kiri),   //rekursif dengan fungsi tampil dengan mengarah ke kanan
   tampil(akar->kanan);  //rekursif dengan fungsi tampil dengan mengarah ke kanan
  }}
 
void preOrder(Node *akar)       //fungsi cetak preOrder
  {
   if(akar != NULL){
   cout<< akar->item<<"  ";         //cetak item akar
   preOrder(akar->kiri),            //cetak di subtree kiri
   preOrder(akar->kanan);           //cetak di subtree kanan
  }}

void inOrder(Node *akar)        //fungsi cetak inOrder
  {
   if(akar != NULL){
   inOrder(akar->kiri),         //cetak di subtree kiri
   cout<< akar->item<<"  ";     //cetak item akar
   inOrder(akar->kanan);        //cetak di subtree kanan
  }}

void postOrder(Node *akar)      //fungsi cetak postOrder
  {
   if(akar != NULL){
   postOrder(akar->kiri),       //cetak di subtree kiri
   postOrder(akar->kanan);      //cetak di subtree kanan
   cout<< akar->item<<"  ";     //cetak item akar
  }}

main()
{
  int item;
  Node *phn;      //pointer phn untuk menghubungkan dengan link Node
  phn = NULL;     //alamat pointer phn pada NULL
  char pil;

  do {
    system("cls");
    cout<<"\tTREE SORT\n";
    cout<<"1. Tambah\n";
    cout<<"2. Pre-order\n";
    cout<<"3. In-order\n";
    cout<<"4. Post-order\n";
    cout<<"5. Keluar\n";
    cout<<"Silahkan masukkan pilihan anda (1-5)...  ";
    pil=getche();
        if(pil=='1')
        {
          cout<<"\n";
          cout<<"\nItem baru : ";cin>>item;
          tambah(&phn,item);    //fungsi tambah dengan menggunakan alamat pointer phn dengan variabel
        }
if(pil=='2')
        {
        if(phn!=NULL) {       //jika phn tidak kosong
          cout<< "\n-->Item yang masuk : ";tampil (phn);  //cetak item yang masuk
          cout<<"\n-->preOrde  : ";preOrder(phn); //cetak preOrder
          }
        else cout<<"\n-->Masih kosong!";
          getch();
        }

if(pil=='3')
        {
        if(phn!=NULL) {
          cout<< "\n-->Item yang masuk : ";tampil(phn);   //cetak item yang masuk
          cout<<"\n-->inOrder  : ";inOrder (phn); //cetak item inOrder
          }
        else cout<<"\n-->Masih kosong!";
          getch();
        }
if(pil=='4')
        {
        if(phn!=NULL) {
        cout<< "\n-->Item yang masuk : ";tampil (phn);    //cetak item yang masuk
        cout<<"\n-->postOrder  : ";postOrder(phn);        //cetak item postOrder
          }
        else cout<<"\n-->Masih kosong!";
          getch();
        }
        }
          while(pil!='5');
            cout<<"\n";




}

Hasil output:

1. PostOrder




2. InOrder






3. PreOrder



Exchange Sort




Cara pebngurutan Exchange Sort








 

Prosedur Exchange Sort

void exchange_sort(int data[])
{
for(int i=0;i<n-1;i++)
{
for(int j=i+1;j<n;j++)
{
if(data[i]<data[j])
tukar(&data[i],&data[j]);
}
}
}

Selection Sort
Pada algoritma selection sort mencari elemen yang tepat untuk diletakkan di posisi yang telah diketahui dan meletakkannya di posisi tersebut setelah data tersebut ditemukan. Selection sort ini membandingkan elemen yang saat ini dengan suatu elemen yang berikutnya hingga elemen yang terakhir. Apabila ditemukan elemen lain yang lebih kecil dari elemen yang saat ini maka dicatat posisinya dan kemudian ditukar.
Berikut script programnya :
#include<iostream>
#include<conio.h>

using namespace std;


template
 <class T>
void s_sort(T a[],int n)
{
     int i,j,t;
     for(i=0;i<n;i++)
     {
                     for(j=i+1;j<n;j++)
                     {
                                       if(a[j]<a[i]) //
for descending order use if(a[j]>a[i]) 
                                       {
                                                    t=a[i];
                                                    a[i]=a[j];
                                                    a[j]=t;
                                       }
                     }
     }
}


int main()
{
    int a[100],i,n;
    cout<<"Enter The number of Element:\n";
    cin>>n;
    cout<<"\nEnter Elements:\n";
    for(i=0;i<n;i++)
    {

                      cout<<"\nEnter:";
                    cin>>a[i];
    }
    s_sort(a,n);
    cout<<"\nAfter Sorting\n";
    for(i=0;i<n;i++)
    {
                    cout<<a[i]<<"\t";
    }
    getch();
    return 0;
}
Hasil Exsekusi







Heap Sort
function heapSort(a, count) is
input: sebuah larik tidak terurut a dengan panjang length
(pertama letakkan a dalam max-heap) heapify(a, count)
end := count -1
while end > 0 do
remove ( )
reheapify ( )
end := end – 1
Source code:

    void siftDown(int arr[], int start, int end) {
    /** start dan end berada dalam jangkauan array yang terdefinisi dengan start < end **/
    /** Menata array dalam jangkauan sesuai kriteria sifat heap **/

    /** deklarasi **/
    int root=start;        // pencarian dimulai dari root
    int child;            // menyimpan indeks anak yang diperiksa
    int inswap;            // indeks untuk swap
    int temp;

    /** sift ketika root masih memiliki anak **/
    /** indeks anak ada di 2*root+1 dan 2*root+2 **/
    while(2*root+1 <= end) {
    child     = 2*root+1;    // dapatkan data anak
    inswap     = root;

    /** Ambil elemen terbesar dan letakkan di root **/
    if(arr[inswap] < arr[child])
    inswap = child;

    if(child+1 <= end)
    if(arr[inswap] < arr[child+1])
    inswap = child+1;

    if(root!=inswap) {
    // pertukarkan
    temp         = arr[root];
    arr[root]     = arr[inswap];
    arr[inswap]    = temp;

    // track down, buat agar struktur heap di bawah konsisten
    root = inswap;
    } else return;
    }
    }

    //————————————————————————————

    void heapify(int arr[], int n) {
    /** n = jumlah elemen di array **/

        /** heapidy membentuk heap dengan bantuan siftdown. Hasil akhirnya adalah array yang tertata sesuai sifat heap **/

    /** mulai heapify dari tengah dan terus naik hingga indeks 0 **/
    int start=(n-2)/2;
    for(int i=start; i>=0; i–)
    siftDown(arr,i,n-1);
    }

    //————————————————————————————

    void heapsort(int arr[], int n) {

    /** n = jumlah elemen di array **/

    /** lakukan heapify untuk menciptakan heap semu **/
    heapify(arr,n);

    /** tercipta heap, elemen terbesar ada di root (indeks 0)
    *  lakukan iterasi untuk setiap langkah, pindahkan root ke akhir,
    *  decrement indeks dan lakukan penataan ulang lagi
    */
    int end=n-1;
    int temp;
    while(end>0) {
    // pindahkan root ke akhir
    temp     = arr[0];
    arr[0]     = arr[end];
    arr[end]= temp;

    // majukan end
    end -= 1;

    // lakukan penataan ulang dengan siftDown
    siftDown(arr,0,end);
    }
    }


Quick Sort
Algoritma ini rekursif, dan termasuk paradigma algoritma divide and conquer.


Algoritma Quick Sort
Algoritma ini terdiri dari 4 langkah utama:
1. Jika struktur data terdiri dari 1 atau 0 elemen yang harus diurutkan, kembalikan struktur data itu apa adanya.
2. Ambil sebuah elemen yang akan digunakan sebagai pivot point (poin poros). (Biasanya elemen yang paling kiri.)
3. Bagi struktur data menjadi dua bagian – satu dengan elemen-elemen yang lebih besar dari pada pivot point, dan yang lainnya dengan elemen-elemen yang lebih kecil dari pada pivot point.
4. Ulangi algoritma secara rekursif terhadap kedua paruh struktur data.

Merge Sort
Algoritma Merge Sort
Merge Sort (A,p,r)
Dimana A = lariknya
             P= Posisi Indeks 1
            r : posisi indeks 2
qß(p+r)/2                                                                                 T(n) = 2
Merge Sort (A,p,r)                                                      n
   if p < r then                                                              1
      q¬(p+r)/2                                                               (n/2)
      Merge-Sort(A, p, q)                                 T(n/2)
      Merge-Sort(A, q+1, r)                              (divide + (n/2)
      Merge(A, p, q, r)                                      combine (O) karena linear.
#include <iostream>
using namespace std;
#include <conio.h>
void merge(int *,int, int , int );
void mergesort(int *a, int low, int high)
{
    int mid;
    if (low < high)
    {
        mid=(low+high)/2;
        mergesort(a,low,mid);
        mergesort(a,mid+1,high);
        merge(a,low,high,mid);
    }
    return;
}
void merge(int *a, int low, int high, int mid)
{
    int i, j, k, c[50];
    i = low;
    k = low;
    j = mid + 1;
    while (i <= mid && j <= high)
    {
        if (a[i] < a[j])
        {
            c[k] = a[i];
            k++;
            i++;
        }
        else
        {
            c[k] = a[j];
            k++;
            j++;
        }
    }
    while (i <= mid)
    {
        c[k] = a[i];
        k++;
        i++;
    }
    while (j <= high)
    {
        c[k] = a[j];
        k++;
        j++;
    }
    for (i = low; i < k; i++)
    {
        a[i] = c[i];
    }
}
int main()
{
    int a[20], i, b[20];
    cout<<"enter  the elements\n";
    for (i = 0; i < 5; i++)
    {
        cin>>a[i];
    }
    mergesort(a, 0, 4);
    cout<<"sorted array\n";
    for (i = 0; i < 5; i++)
    {
        cout<<a[i];
    }
    cout<<"enter  the elements\n";
    for (i = 0; i < 5; i++)
    {
        cin>>b[i];
    }
    mergesort(b, 0, 4);
    cout<<"sorted array\n";
    for (i = 0; i < 5; i++)
    {
        cout<<b[i];
    }
    getch();
}

Hasil exsekusi :















 
Shell Sort
Algoritma metode Shell dapat dituliskan sebagai berikut :
1.      Jarak = N
2.      Selama (Jarak > 1) kerjakan baris 3 sampai dengan 9
3.      Jarak = Jarak / 2. Sudah = false
4.      Kerjakan baris 4 sampai dengan 8 selama Sudah = false
5.      Sudah = true
6.      j = 0
7.      Selama (j < N – Jarak) kerjakan baris 8 dan 9
8.      Jika (Data[j] > Data[j + Jarak] maka tukar Data[j],
Data[j + Jarak].
Sudah = true
9.      j = j + 1
Contoh dari proses Sorting dengan menggunakan metode Shell Sort:
Script program                    :
#include<iostream>

using namespace std;

int main(void)

{

   int array[5];    // An array of integer

   int length = 5;  // Length of the array

   int i, j, d;

   int tmp, flag;

   //some input

   for(i=0; i<length; i++)

   {
         cout<<"Enter a number: ";
         cin>>array[i];
   }

   //Algorithm
   d=length;
   flag=1;
   while(flag || (d>1))
   {
         flag=0;
         d=(d+1)/2;
         for(i=0; i<(length -d); i++)
         {
               if(array[i+d]>array[i])
               {
                     tmp=array[i+d];
                     array[i+d]=array[i];
                     array[i]=tmp;
                     flag=1;
               }
            }
   }

   //Some output
   for(i=0; i<5; i++)
   {
         cout<<array[i]<<endl;
      }
}