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;

      }

}