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;
}
}
