metode sorting

 Tree sort

Tree sort adalah metode sorting dengan cara membangun pohon biner dengan menampilkan 3 hasik output: PreOrder,InOrder,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 bawah ini.

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.

Setiap objek dalam pohon biner berisi dua pointer, biasanya disebut kiri dan kanan.Selain pointer ini tentu saja node dapat berisi tipe data lainnya. Misalnya, pohon biner integer bisa terdiri dari objek dari jenis berikut:

       struct Node {

           int item; / / Data dalam node ini.

           Node *kiri; / / Pointer ke subtree kiri.

           Node * kanan; / / ​​Pointer ke subtree kanan.

       }

Program tree sort :

#include<stdio.h>
#include<conio.h>
#include<malloc.h>

typedef struct node{
int data;
node *left;
node *right;
};
node *root=NULL;

void Tambahnode(node **root, int isi) {
if((*root)==NULL){
node *baru;
baru= new node;
baru->data = isi;
baru->left = NULL;
baru->right = NULL;
(*root)=baru;
}
}

void preorder(node *root) {
if(root !=NULL) {
printf(“%i, “, root->data);
preorder(root->left);
preorder(root->right);
}
}

void inorder(node *root) {
if(root !=NULL) {
inorder(root->left);
printf(“%i, “, root->data);
inorder(root->right);
}
}

void postorder(node *root) {
if(root !=NULL) {
postorder(root->left);
postorder(root->right);
printf(“%i, “, root->data);
}
}

int main(){

int nil;
int x;
int y;
x=40;y=3;

gotoxy(x,y);
printf(“100\n”);
gotoxy(x-10,y+1);
printf(“90″);
gotoxy(x+10,y+1);
printf(“200\n”);
gotoxy(x-20,y+2);
printf(“80″);
gotoxy(x+20,y+2);
printf(“300\n”);
gotoxy(x-30,y+3);
printf(“70″);
gotoxy(x+30,y+3);
printf(“400\n”);
Tambahnode(&root,nil=100);
Tambahnode(&root->left,nil=90);
Tambahnode(&root->left->left,nil=80);
Tambahnode(&root->left->left->left,nil=70);
Tambahnode(&root->right,nil=200);
Tambahnode(&root->right->right,nil=300);
Tambahnode(&root->right->right->right,nil=400);
printf(“\nProgram By: AH. HANDOYO[1412110156]”);
printf(“\nTampilan secara PreOrder : “);
preorder(root);
printf(“\nTampilan secara InOrder : “);
inorder(root);
printf(“\nTampilan secara PostOrder : “);
postorder(root);

}

Output Program :

Exchange sort

•         Sangat mirip dengan Bubble Sort

•         Banyak yang mengatakan Bubble Sort sama dengan Exchange Sort

•         Pebedaan : dalam hal bagaimana membandingkan antar elemen-elemennya.

•         Exchange sort membandingkan suatu elemen dengan elemen-elemen lainnya dalam array tersebut, dan melakukan pertukaran elemen jika perlu.  Jadi ada elemen yang selalu menjadi elemen pusat (pivot).

•         Sedangkan Bubble sort akan membandingkan elemen pertama/terakhir dengan elemen sebelumnya/sesudahnya, kemudian elemen tersebut itu akan menjadi pusat (pivot) untuk dibandingkan dengan elemen sebelumnya/sesudahnya lagi, begitu seterusnya.

Exchange sort 2

Selection sort

•         Merupakan kombinasi antara sorting dan searching

•         Untuk setiap proses, akan dicari elemen-elemen yang belum diurutkan yang memiliki nilai terkecil atau terbesar akan dipertukarkan ke posisi yang tepat di dalam array.

•         Misalnya untuk putaran pertama, akan dicari data dengan nilai terkecil dan data ini akan ditempatkan di indeks terkecil (data[0]), pada putaran kedua akan dicari data kedua terkecil, dan akan ditempatkan di indeks kedua (data[1]).

•         Selama proses, pembandingan dan pengubahan hanya dilakukan pada indeks pembanding saja, pertukaran data secara fisik terjadi pada akhir proses.

HOMEDAFTAR ISITUKAR LINK

Heap Sort

 Heap Sort adalah sebuah algoritma pengurutan yang paling lambat dari algoritma yang memiliki kompleksitas O(n log n). Tetapi tidak seperti algoritma Merge Sort dan Quick Sort, algoritma Heap Sort tidak memerlukan rekursif yang besar atau menggunakan banyak tabel (array). Oleh karena itu, Heap Sort adalah pilihan yang baik untuk sebuah kumpulan data yang besar.

 Algoritma ini bekerja dengan menentukan elemen terbesar (atau terkecil) dari sebuah daftar elemen, dan diletakkan pada akhir (atau awal) dari daftar tersebut. Heap sort menyelesaikan sebuah pengurutan menggunakan struktur data yang disebut heap.

Algoritma ini dimulai dengan membangun sebuah array heap dengan membangun tumpukan dari kumpulan data, lalu memindahkan data terbesar ke bagian belakang dari sebuah tabel hasil. Setelah itu, array heap dibangun kembali, kemudian mengambil elemen terbesar untuk diletakkan di sebelah item yang telah dipindahkan tadi. Hal ini diulang sampai array heap habis.

Jadi secara umum, algoritma ini memerlukan dua buah tabel; satu tabel untuk menyimpan heap, dan satu tabel lainnya untuk menyimpan hasil. Walaupun lebih lambat dari Merge Sort atau Quick Sort, algoritma ini cocok untuk digunakan pada data yang berukuran besar.

Penerapan Algoritma Pengurutan Heap Sort

  Salah satu contoh penerapan algoritma pengurutan (sorting algorithm) heap sort adalah sebagai berikut: Misalkan terdapat suatu array bilangan bulat yang terdiri dari sepuluh buah anggota dengan nilai data 11, 9, 8, 27, 16, 25, 12, 13, 34, dan 43. Kita akan mengurutkan data diatas dengan menggunakan heapsort. Pertama-tama, array di atas dapat dipandang sebagai suatu Complete Binary Tree (CBT) sebagai berikut:

 
 Selanjutnya algoritma metoda heapify dilakukan dengan iterasi dari subtree node ke-4, ke-3, dan seterusnya berturut-turut hingga mencapai root (akar). Iterasi dilakukan mulai dari node ke-4 karena N/2 dalam contoh di atas adalah 5. Dan elemen kelima dari array memiliki nilai indeks 4 sebab indeks array biasanya diawali dari 0. Penerapan algoritma metoda heapify terhadap Complete Binary Tree (CBT) pada contoh di atas menghasilkan operasi-operasi pertukaran sebagai berikut:

1. Subtree node ke-4: pertukaran 16 dengan 43

2. Subtree node ke-3: pertukaran 27 dengan 34

3. Subtree node ke-2: pertukaran 8 dengan 25

4. Subtree node ke-1: pertukaran 9 dengan 43, lalu pertukaran 9 dengan 16

5. Subtree node ke-0: pertukaran 11 dengan 43, lalu pertukaran 11 dengan 34, serta akhirnya pertukaran 11 dengan 27 Perubahan-perubahan (pertukaran) tersebut dapat digambarkan sebagai berikut:

 Semua perubahan di atas terjadi dalam array yang bersangkutan, sehingga pada akhirnya diperoleh tree terakhir yang merupakan heap tree. Sementara itu, dalam iterasi yang melakukan/menerapkan algoritma metoda remove( ) dan algoritma metoda reheapify() akan terjadi pemrosesan berikut:

1. Setelah 43 di-remove dan 9 menggantikan posisi yang ditinggalkan oleh 43, maka terjadi reheapify: penukaran 9 dengan 34, 9 dengan 27, dan 9 dengan 13.

dan data yang telah terurut adalah 43.

2. Setelah 34 di-remove dan 11 menggantikan posisi yang ditinggalkan oleh 34, maka terjadi reheapify: penukaran 11 dengan 27, dan 11 dengan 16.

dan data yang telah terurut adalah 34, 43.

3. Setelah 27 di-remove dan 9 menggantikan posisi yang ditinggalkan oleh 27, maka terjadi reheapify: penukaran 9 dengan 25, dan 9 dengan 12.

dan data yang telah terurut adalah 27, 34, 43.

4. Demikian seterusnya dilakukan algoritma metoda remove dan algoritma metoda reheapify hingga tidak ada lagi node yang tersisa. Dan pada akhirnya akan didapatkan hasil data yang telah terurut adalah 8, 9, 11, 12, 13, 16, 25, 27, 34, 43.

Program Heap Sort & Penjelasannya

<#include <>

void restoreHup(int*,int); // pemanggilan fungsi void restoreHup

void restoreHdown(int*,int,int); //pemanggilan fungsi void restoreHdown

void main()

{ // pembuka void main

int a[20],n,i,j,k; // mendeklarasikan bahwa a[20] ,n,i,j,k adalah integer

printf(" Masukkan jumlah element : ");// untuk menampilkan kelayar perintah memasukkan jumlah element

scanf("%d",&n); // untuk mengidentifikasikan nilai yang dimasukkan melalui keyboard

printf(" Masukkan element : "); //untuk menampilkan kelayar perintah untuk memasukkan element

for(i=1;i<=n;i++) //funsi for dimana jika ketentuan untuk i terpenuhi maka progran di bawahnya akan dijalankan

{ // pembuka fungsi for

scanf("%d",&a[i]); // untuk mengidentifikasi array a

restoreHup(a,i); // a , i dalam fungsi restoreHup

} // penutup fungsi for

j=n; // nilai j sama dengan n

for(i=1;i<=j;i++) //funsi for dimana jika ketentuan untuk i terpenuhi maka progran di bawahnya akan dijalankan

{ // pembuka fungsi for

int temp; // temp sebagai integer

temp=a[1]; // temp sama dengan nilai array a yang pertama

a[1]=a[n]; // nilai array a yg ke 1 sama dengan array a yang ke n

a[n]=temp; // nilai array a yang ke n sama dengan nilay temp

n--; // nilai n selalu berkurang 1

restoreHdown(a,1,n); // a , 1, n dalam fungsi restoreHdown

} // penutup fungsi for

n=j; // n sama dengan nilai j

printf(" Here is it... "); // untuk menampilkan perintah ke dalam layar

for(i=1;i<=n;i++) //funsi for dimana jika ketentuan untuk i terpenuhi maka progran di bawahnya akan dijalankan

printf("%4d",a[i]); // untuk menampilkan nilai array ke i ke layar

} // penutup void main

void restoreHup(int *a,int i) // fungsi void restore Hup

{ // pembuka fungsi foid restoreHup

int v=a[i]; // v sama dengan nilai array a yang ke i

while((i>1)&&(a[i/2]

{ // pembuka fungsi while

a[i]=a[i/2]; // nilai array a yang ke i sama dengan nilai array a yang ke i/2

i=i/2; // nilai i sama dengan nilai i/2

} //penutup fungsi while

a[i]=v; // nilai array a yang ke i sama dengan nilai v

} // penutup fungsi while

void restoreHdown(int *a,int i,int n) // fungsi void restoreHdown

{ // pembuka fungsi void restoreHdown

int v=a[i]; // v sama dengan nilai array a yang ke i sebagai integer

int j=i*2;// nilai j sama dengan i kali 2 ialah integer

while(j<=n) // fungsi while akan dijalankan bila ketentuannya terpenuhi

{ // pembuka fungsi while

if((j

j++; // nilai j akan selalu tambah 1

if(a[j]

break;

a[j/2]=a[j]; // nilai array a yang ke j/2 sama dengan nilai array a yang ke j

j=j*2; // nilai j sama dengan nilai j*2

}// penutup fungsi while

a[j/2]=v;// nilai array a yang ke j/2 sama dengan v

}// penutup fungsi void restorehdown

//Suatu program untuk mengimplementasikan Heap Sort>

Hasil Program diatas :

Quick sort

  Quick Sort adalah algoritma sorting yang terkenal yang dirancang oleh C.A.R. Hoare  pada tahun 1960 ketika bekerja untuk perusahaan manufaktur komputer saintifik kecil, Elliott Brothers. Algoritma ini rekursif, dan termasuk paradigma algoritma divide and conquer.

Algoritma Quick Sort 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 digunakansebagai pivot point (poin poros). (Biasanyaelemen yang paling kiri.)  

3.)    Bagi struktur data menjadi dua bagian satudengan elemen-elemen yang lebih  besar daripada pivot point, dan yang lainnya denganelemen-elemen yang lebih kecil dari pada pivot point. 4.

4.)    Ulangi algoritma secara rekursif terhadapkedua paruh struktur data.

Contoh Program Quick Sort :

#include<iostream.h>

 #include<iomanip.h>

void quickSort(int[], int);

void q_sort(int[], int, int);

void main()

{

int NumList[8]={5,34,32,25,75,42,22,2};

int temp;

cout<<"Data Sebelum Diurutkan: \n";

for(int d=0; d<8; d++)

{

cout<<setw(3)<<NumList(d);

}

cout<<"\n\n";

quickSort (NumList,8);

cout<<"Data Setelah Diurutkan: \n";

for (int iii=0; iii<8; iii++)

cout<<"setw(3)"<<NumList[iii]<<endl<<endl;

}

void quickSort(int numbers[], int array_size)

{

q_sort(number, 0, array_size-1);

}

void q_sort(int number[], int left, int right)

{

int pivot, l_hold, r_hold;

 l_hold=left;

r_hold=right;

pivot = numbers[left];

while (left<right)

{

while((numbers[right]>=pivot || (left<right))

right--;

if(left != right)

{

numbers[left]=numbers[right];

left++;

}

while ((numbers[left] <=pivot) && (left<right))

left++;

if (left != right)

{

number[right]=numbers[left];

right--;

}

}

numbers[left]=pivot;

pivot=left;

left=l_hold;

right=r_hold;

if (left<pivot)

q_sort(numbers, left, pivot-1);

if (right>pivot)

q_sort(numbers, pivot+1, right);

}

Script program yang benar :

/*Quick Sort*/

#include<iostream>

#include<iomanip>

#include <conio.h>

using namespace std;

void quickSort(int[], int);

void q_sort(int[], int, int);

int main()

{

 int NumList[8]={5,34,32,25,75,42,22,2};

int temp;

cout<<"Data Sebelum Diurutkan: \n";

for(int d=0; d<8; d++)

{

cout<<setw(3)<<NumList[d];

}

cout<<"\n\n";

quickSort (NumList,8);

cout<<"Data Setelah Diurutkan: \n"; for (int iii=0; iii<8; iii++) cout<<setw(3)<<NumList[iii]<<endl<<endl;

}

void quickSort(int numbers[], int array_size)

{

q_sort(numbers, 0, array_size-1);

}

void q_sort(int numbers[], int left, int right)

{

int pivot, l_hold, r_hold;

l_hold=left;

 r_hold=right;

pivot = numbers[left];

 while (left<right)

{

while((numbers[right]>=pivot) &&(left<right))

right--;

if(left != right)

{

numbers[left]=numbers[right];

left++;

}

while ((numbers[left] <=pivot) && (left<right))

left++;

if (left != right)

{

numbers[right]=numbers[left];

right--;

}

}

numbers[left]=pivot;

pivot=left;

left=l_hold;

right=r_hold;

if (left<pivot)

q_sort(numbers, left, pivot-1);

if (right>pivot)

q_sort(numbers, pivot+1, right);

}

Output Program :

Algoritma :

1.       Mulai.

2.       Membaca file header.

3.       Membaca fungsi metode quick sort.

4.       Membaca fungsi numlist [8], temp.

5.       Membaca perulangan.

6.       Pemanggilan fungsi quicksort.

7.       Cetak hasil.

8.       Tampilan data sebelum diurutkan.

9.       Membaca fungsi quicksort (numlist,8).

10.   Cetak hasil.

11.   Tampilan data setelah diurutkan.

12.   Selesai.

Deskripsi :

Program diatas menggunakan metode quick sort yang sistematika quick sort adalah pertama jika struktur data terdiri dari 1/0 maka kembalikan struktur data apa adanya, jangan diubah. kemudian ambil sebuah elemen yang akan digunakan sebagai pivot biasanya elemen paling kiri. bagi struktur data menjad 2  bagian, satu dengan elemen yang lebih besar daripada pivot, dan lainnya dengan elemen yang lebih kecil dengan pivot. ulangi terus secara rekursif terhadap kedua  pruh struktur tersebut.

4.      Merge Sort

Algoritma Merge Sort ditemukan oleh John vonNeumann di tahun 1945. Merge Sort termasuk paradigma algoritma divide and conquer (kurang lebihberarti: bagi dan atasi). Hal ini dikarenakan algoritma ini melakukan pembagian struktur data sebelumkemudian dioperasi satu per satu. Intinya, algoritma ini menggunakan dua ide utama sebagai berikut :

1.)    Sebuah list yang kecil membutuhkan langkahyang lebih sedikit untuk pengurutan daripadasebuah list yang besar.

2.)    Untuk membentuk sebuah list terurut dari duabuah list terurut membutuhkan langkah yanglebih sedikit daripada membentuk sebuah listterurut dari dua buah list tak terurut. Contoh: hanya diperlukan satu kali traversal untukmasing-masing list  jika keduanya sudah terurut.

Algoritma Merge Sort sederhananya, dapat ditulis berikut:

1.)    Bagi list yang tak terurut menjadi dua samapanjang atau salah satunyalebih  panjang satu elemen.

2.)    Bagi masing-masing dari 2 sub-list secara rekursif sampai didapatkan list dengan ukuran 1.

3.)    Gabung 2 sublist kembali menjadi satu list terurut.

Algoritma :

Algoritma Merge sort sebenarnya sederhana[9]: bagi larik menjadi dua sama besar, urutkan bagian pertama, urutkan bagian kedua, lalu gabungkan.

Sebagai contoh, jika terdapat data berupa 38, 27, 43, 3, 9,82, dan 10 maka ilustrasi pengurutannya adalah sebagai berikut:

Pseudocodeuntuk merge sort[6] adalah sebagai berikut:

mergesort(data)

if data memiliki setidaknya dua

elemen

mergesort (separuh kiri dari data);

mergesort (separuh kanan dari data ;

merge (kedua bagian ke dalam suatu urutan);

Sedangkan pseudocodeuntuk merge itu sendiri adalah:

merge (arrayl, pertama, terakhir)

tengah = (pertama + terakhir) / 2;

il = 0;

i2 = pertama;

i3 = tengah + 1;

while kedua sub larik dari array1 memiliki elemen

if arrayl[i2] < arrayl[i3]

temp[il++] = arrayl[i2++];

else

temp[il++] = arrayl[i3++];

masukkan ke dalam temp sisa elemen dari arrayl;

masukkan ke arrayl isi dari temp;

Contoh program merge sort :

void merge(int kiri,int tengah, int kanan)

{

int h,i,j,b[50],k;

h=kiri;

i=kiri;

j=tengah+1;

while((h<=tengah)&&

(j<=kanan))

{

if(bilangan[h]<=

bilangan[j])

{

b[i]=bilangan[h];

h++;

}

else

{

b[i]=bilangan[j];

j++;

}

i++;

}

if(h>tengah)

{

for(k=j;k<=kanan;k++)

{

b[i]=bilangan[k];

i++;

}

}

else

{

for(k=h;k<=tengah;k++)

{

b[i]=bilangan[k];

i++;

}

}

else

{

for(k=h;k<=tengah;k++)

{

b[i]=bilangan[k];

i++;

}

}

for(k=kiri;k<=kanan;k++)

bilangan[k]=b[k];

}

void merge_sort(int kiri,

int kanan)

{

int tengah;

if(kiri<kanan)

{

tengah=(kiri+kanan)/2;

merge_sort(kiri,tengah);

merge_sort(tengah+1,

kanan);

merge(kiri,tengah,

kanan);

}

}

Output program :

Shell sort (pembagian insertion)

   

Metode ini dikembangkan oleh Donald L. Shell pada tahun 1959. Dalam metode ini  jarak antara dua elemen yang dibandingkan dan ditukarkan tertentu. Secara singkat metode ini dijelaskan sebagai berikut. Pada langkah pertama, kita ambil elemen  pertama dan kita bandingkan dan kita bandingkan dengan elemen pada jarak tertentu dari elemen pertama tersebut. Kemudain elemen kedua kita bandingkan dengan elemen lain dengan jarak yang sama seperti jarak yang sama seperti diatas. Demikianseterusnya sampai seluruh elemen dibandingkan. Pada langkah kedua proses diulang dengan langkah yang lebih kecil, pada langkah ketiga jarak tersebut diperkecil lagi seluruh proses dihentikan jika jarak sudah sama dengan satu.

Contoh dari proses Sorting dengan menggunakan metode Shell Sort :

                      

Program Shell Sort sebagai berikut :

/*shell sort*/

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

}

}

Output program :

 

Algoritma :

1.       Mulai

2.       Membaca file header.

3.       Membaca fungsi main.

4.       Membaca fungsi array yang didalamnya terdpat fungsi panjang.

5.       Membaca perulangan.

6.       Membaca percabangan.

7.       Membaca fungsi temp.

8.       Membaca perulangan.

9.       Pemanggilan array[i].

10.   Cetak hasil.

11.   Selesai.

Deskripsi :

Program diatas menggunakan metode shell short yang sistematika membandingkan elemen pertama dengan elemen lain yang berada dalam jarak yang sama namun yang lingkupnya paling jauh, begitu seterusnya sampai membandingkan elemen pada jarak yang berdekatan satu sama lain. Algroitma  program diatas adalah karena sistematikanya membandingkan antar elemen yang letaknya berjauhan sampai terdekat maka seperti ini ilustrasinya : angka yang diinputkan tergantung pengguna. Misalnya ingin menginputkan 4 data maka aka nada 4 data , misalnya 6 9 7 4 maka sistematika kerjanya adlaah 6 akan dibandingkan dengan 4 , 7, 9 dari jarak terjauh-terdekat. Kemudian tentukan jika ascending atau descending pernyataan bilangannya seperti apa contoh 6<4 dan lain sebagainya.

REFERENSI:

https://siraits.files.wordpress.com/2008/04/algodanstrukturdata8.ppt (Sabtu, 11 April 2015 pukul 12.55 WIB)

http://bekompaa.blogspot.com/2013/04/contoh-laporan-dan-makalah-tentang-heap.html (Senin, 13 April 2015 pukul 11.18 WIB)

http://informatika.org/~rinaldi/Stmik/Makalah/MakalahStmik08.pdf (Senin, 13 April 2015 pukul 11.51 WIB)

http://kael9001.blogspot.com/2013/02/bubble-sort.html (Senin, 13 April 2015 pukul 11.43 WIB)

http://nurjannahfitri.blogspot.com/2015_04_01_archive.html (Senin, 13 April 2015 pukul 12.02 WIB)

Read More

5 Metode dalam Teknik Sorting

1.       Pengurutan berdasarkan penyisipan dan penjagaan terurut (insert and keep sorted method)

·         Insertion sort

Teknik sorting ini dibuat dengan cara menyisipkan atau memasukkan satu-persatu, bila kita akan mengurutkan data, kemudian ingin menyisipkan suatu data maka data tersebut akan otomatis masuk dimana dia berada.Pengurutan dilakukan dengan cara membandingkan data ke – i dengan data berikutnya, (dimana i dimulai dari data di index ke 1 sampai dengan data terakhir). Jika ditemukan data yang lebih kecil maka data tersebut disisipkan ke depan sesuai dengan posisi yang seharusnya, dan saat ada elemen yang disispkan, maka elemen-elemen lainnya akan bergeser kebelakang.

Contoh procedure insertion sort ascending :

Procedure asc_insert;

Var

i, j, temp : byte;

begin

for i := 2 to max do

begin

temp := data [i] ;

j :=i-1;

while (data [j] > temp ) and (j>0) do

begin

data [j+1] := data [j];

dec (j) ;

end;

data [j+1] := temp ;

end;

end;

·         Tree sort

Metode sorting dengan cara membangun pohon biner dengan menampilkan 3 hasil output: PreOrder, InOrder, dan PostOrder.

Konsep dasar dari tree sort adalah sebagaimana sebuah pohon, ada akar, batang, ranting, daun, dan sebagainya. Dalam tree sort ada istilah akar atau root dan daun atau leaf.

2.      Pengurutan berdasarkan perbandingan (compirasion-based sorting)

·         Bubble sort

Teknik ini dilakukan dengan pola membawa nilai terbesar menjadi nilai index terakhir array. Jadi sistem ini melakukan pengecekan nilai 1 dengan 2, lalu 2 dengan 3 sampai dengan data terakhir, bila nilai index yang lebih kecil lebih besar maka akan dilakukan pertukaran. Proses ini dilakukan hingga jumlah data.

Membandingkan elemen yang sekarang dengan elemen yang berikutnya, jika elemen sekarang>elemen berikutnya, maka tukar.

Contoh procedure tukar data:

Procedure asc_buble (var data :array; jmldata:integer);

Var

i,j : integer;

begin

for i := 2 to jmldata do

for j :=jmldata downto i do

if data [j] <  data [j-1] then

tukardata (data[j], data [j-1] ) ;

end;

·         Exchange sort

Teknik sorting ini dibuat dengan cara pola membawa nilai terbesar menjadi nilai index terakhir array. Jadi sistem ini melakukan pengecekan nilai 1 dengan 2, lalu 2 dengan 3 sampai dengan data terakhir, bila nilai index yang lebih kecil lebih besar maka akan dilakukan pertukaran. Proses ini dilakukan hingga jumlah data dikurangi 1 atau sampai program tidak melakukan pertukaran. Jadi waktu untuk melakukan proses sorting lebih cepat. Exchange sort itu sangat mirip dengan buble sort. Bahkan banyak yang mengatakan bahwa exchange sort sama dengan buble sort.

Contoh procedure exchange sort :

Procedure asc_buble (var data :array; jmldata:integer);

Var

i,j : integer;

begin

for i := 2 to jmldata do

for j :=jmldata downto i do

if data [j] <  data [j-1] then

tukardata (data[j], data [j-1] ) ;

end;

perbedaannya terdapat dalam hal bagaimana membandimgkan antar elemen-elemennya:

Exchange sort	Buble sort
·         Membandingkan suatu elemen dengan elemen-elemen yang lainnya dalam array tersebut. ·         Melakukan pertukaran elemen jika perlu. ·         Jadi ada elemen yang selalu menjadi elemen pusat (pivot).	·         Membandingkan elemen pertama atau terakhir dengan elemen sebelumnya/  sesudahnya. ·         Kemudian elemen tersebut akan menjadi pusat (pivot) untuk dibandingkan dengan elemen sebelum/ sesudahnya lagi. ·         Begitu seterusnya

3.      Penguurutan berdasarkan prioritas (priority queue sorting method)

·         Selection sort

Teknik sorting ini dibuat dengan cara melakukan pengecekan satu-persatu, bila kita akan mengurutkan secara ascending maka kita lakukan pengecekan nilai tempat yang pertama (index pertama pada array) kita bandingkan semua nilai yang ada kita cari nilai minimalnya, lalu simpan index/ letak nilai minimum itu ditemukan, setelah pengecekan selesai tukar index awal pengecekan dengan nilai minimum yang telah simpan tadi. Proses ini dilakukan terus-menerus sampai pada pengecekan index terakhir minimal dengan index terakhir, beda dengan streith selection sort adalah dengan teknik ini melakukan pertukaran nilai lebih sedikit, hanya jumlah data-1 pertukaran. Jadi waktu untuk melakukan proses sorting lebih cepat.Membandingkan elemen yang sekarang dengan elemen yang berikutnya sampai dengan elemen yang terakhir. Jika ditemukan elemen yang lebih kecil, maka dicatat posisinya. Namun jika ditemukan elemen terkecil, maka dicatat posisinya dan kemudian di TUKAR dengan elemen sekarang.

Contoh procedure selection sort secara ascending :

Procedure asc_selection;

Var

Min,pos : byte;

Begin

For i:= 1 to max-1 do

Begin

Pos :=i ;

For j := i+1 to max do

If data [j] < data [pos] then pos :=j;

If i <> pos then tukardata (data[i] , data[pos] );

End;

End;

·         Heap sort (menggunakan tree)

Teknik sorting ini dibuat dengan versi yang jauh lebih efisien selection sort. Ia juga bekerja dengan menentukan elemen (atau terkecil) terbesar daftar, menempatkan bahwa pada akhir (atau awal) dari daftar, kemudian melanjutkan dengan sisa daftar tapi menyelesaikan tugas ini secara efisien dengan menggunakan struktur data yang disebut tumpukan, tipe khusus pohon biner. Setelah daftar data telah dibuat menjadi tumpukan, simpul akar dijamin menjadi unsur (atau terkecil) terbesar. Ketika dipindahkan dan ditempatkan di akhir daftar, tumpukan adalah ulang sehingga elemen terbesar yang tersisa bergerak ke akar. Menggunakan heap, menemukan elemen terbesar berikutnya membutuhkan O (log n) waktu, bukan O (n) untuk linear scan di selection sort sederhana. Hal ini memungkinkan heapsort untuk menjalankan dalam O (n log n) waktu, dan ini juga merupakan kompleksitas kasus terburuk.

4.      Pengurutan berdasarkan pembagian dan penguasaan (devide and conquer method)

·         Quick sort

Teknik sorting ini dibuat dengan cara yang menggunakan partisi. Pada teknik ini, data dibagi menjadi dua bagian, yaitu data disebelah kiri partisi selalu lebih kecil dari data disebelah kanan. Namun data pada kedua patisi belum terurut, sehingga untuk mengurutkannya, proses pengurutan dilakukan pada kedua partisi secara terpisah. Selanjutnya, data di sebelah kiri dan kanan dipartisi lagi.Merupakan proses penyusunan elemen yang membandingkan suatu elemen (pivot) denan elemen yang lain, dan menyusunnya sedemikian rupa sehingga elemen –elemen lain yang lebih kecil dari pivot terletak disebelah kiri pivot. Dan elemen yang lebih besar dari pivot terletak disebelah kanan pivot.Dengan demikian akan terbentuk dua sublist, yang terletak disebelah kanan dan kiri pivot.Lalu pada sublist kiri dan kanan itu kita anggap sebuah list baru, dan kita kerjakan proses yang sama seperti yang sebelumnya.Demikian seterusnya sampai tidak terdapat sublist lagi.

Contoh procedure quick sort secara ascending :

Procedure asc_quick (l , r :integer) ;

Var

i, j : integer;

begin

if l < r then

begin

i := l ;    j := r+1;

repeat

repeat inc (i) until data [i] >= data [l] ;

repeat dec (j) until data [j] <= data [l] ;

if i<j then tukardata (data [i], data [j]) ;

until i>j ;

tukardata (data [l], data [j] );

asc_quick (l, j-1);

asc_quick (j+1, r);

end;

end;

·         Merge sort

Teknik sorting ini dibuat dengan cara mengambil keuntungan dari kemudahan penggabungan daftar sudah disortir ke daftar diurutkan baru. Dimulai dengan membandingkan setiap dua elemen (yaitu: 1 dengan 2, kemudian 3 dengan 4) dan swapping mereka jika yang pertama datang setelah kedua. Kemudian masing-masing menggabungkan daftar yang dihasilkan dari dua ke daftar empat, kemudian menggabungkan daftar tersebut empat, dan seterusnya, sampai akhirnya dua daftar digabungkan ke dalam daftar diurutkan akhir.

5.      Pengurutan berkurang menurun (diminishing increment sort method)

·         Shell sort (pengembangan insertion)

Merupakan proses pengurutan data yang sebelumnya acak menjadi data yang terurut dengan cara menentukan jarak antar elemen yang akan dibandingkan.Teknik sorting ini dibuat dengan cara meningkatkan atas bubble sort dan insertion sort dengan menggerakkan keluar dari elemen-elemen memesan lebih dari satu posisi pada suatu waktu. Salah satu implementasi dapat digambarkan sebagai mengatur urutan data dalam array dua dimensi dan kemudian menyortir kolom baru array menggunakan insertion sort.

http://designkeyz.blogspot.com/2011/04/teknik-sorting-dan-searching.html (Rabu, 01 April 2015 pukul 23.55WIB)

http://puguhjayadi.blogspot.com/2013/05/tree-sort-c.html (Rabu, 01 April 2015 pukul 23.55WIB)

https://itprogrammingandlinux.wordpress.com/2011/05/22/buble-insertion-selection-shell-maxmin-quick-merge-sort/ (Rabu, 01 April 2015 pukul 00.01WIB)

Read More

PENGERTIAN STRUKTUR DATA

Dalam istilah ilmu komputer, sebuah struktur data adalah cara penyimpanan, penyusunan dan pengaturan data di dalam media penyimpanan komputer sehingga data tersebut dapat digunakan secara efisien. Sedangkan Data adalah representasi dari fakta dunia nyata. Fakta atau keterangan tentang kenyataan yang disimpan, direkam atau direpresentasikan dalam bentuk tulisan, suara, gambar, sinyal atau simbol.

Konstanta digunakan untuk menyatakan nilai tetap sedangkan variable digunakan dalam program untuk menyatakan nilai yang dapat berubah-ubah selang eksekusi berlangsung.

Ada empat istilah data, yaitu:

1.      Tipe data adalah jenis atau macam data di dalam suatu variable dalam bahasa pemrograman.

2.      Objek data mengacu kumpulan elemen, D (domain).

3.      Representasi data : Suatu mapping dari struktur data ‘d’ ke suatu set ke struktur data ‘e’ (d===e) misal bolean di representasikan dalam 0 dan 1.

4.      Struktur data biasa dipakai untuk mengelompokan beberapa  informasi yang terkait menjadi sebuah kesatuan.

Dalam teknik pemrograman, struktur data berarti tata letak data yang berisi kolom-kolom data, baik itu kolom yang tampak oleh pengguna (user) atau pun kolom yang hanya digunakan untuk keperluan pemrograman yang tidak tampak oleh pengguna.Setiap baris dari kumpulan kolom-kolom tersebut dinamakan catatan (record). Lebar kolom untuk data dapat berubah dan bervariasi. Ada kolom yang lebarnya berubah secara dinamis sesuai masukan dari pengguna, dan juga ada kolom yang lebarnya tetap. Dengan sifatnya ini, sebuah struktur data dapat diterapkan untuk pengolahan database (misalnya untuk keperluan data keuangan) atau untuk pengolah kata (word processor) yang kolomnya berubah secara dinamis. Contoh struktur data dapat dilihat pada berkas-berkas lembar-sebar (spreadsheet), pangkal-data (database), pengolahan kata, citra yang dipampat (dikompres), juga pemampatan berkas dengan teknik tertentu yang memanfaatkan struktur data.

Refrensi :

http://strukturdata18.blogspot.com/2013/05/makalah-struktur-dar.html (diakses pada 27 Februari 2015, pukul 09:31WIB)

Read More

Merindukan Sahabat Sejati

Semua berubah, kini semua telah menjadi harimau ganas yang hanya melihat dengan kasat mata tanpa memikirkan apa yang dia lakukan itu menyakiti hatiku. Aku hanya ingin mempunyai teman yang dapat menerimaku apa adanya, dulu seketika aku belum melakukan hal bodoh itu banyak yang menyegani dan menemaniku tetapi kini berubah ya semua menjauh. Lelaki itu ya lelaki itu pun menjauhiku dan mungkin dia tak mengenal aku, aku tak tahu apa yang dia pikirkan tentang aku mungkin dia membenciku.
Semenjak kejadian itu aku merasa teman teman menjauh dan nmembenci aku, tapi disisi lain aku iri dengan lelaki itu dia mempunyai banyak teman dia bebas dia bisa bersenang-senang dengan sahabatnya sedangkan aku hanya bisa berdiam dan menahan rasa sakit itu sendiri. Ketika dia dan teman-temannya tertawa aku hanya berfikir bahwa "kapan aku bisa tertawa bersama mereka kembali tanpa banayk beban dan menyakiti mereka" aku cuman ingin mereka mengerti dengan perubahanku bukan malah menjauhi aku.
aku juga manusia biasa yang mempunyai hati dan ingin seprti kalian yang dapat tertawa lepas tanpa beban
   Teman maafkan aku jika aku mempunyai salah terhadap kalian

   Teman mengertilah aku dan jangan kau mengecilkan ku diantara kalian

   Teman aku merindukan kalian

Ake merindukan masa masa itu .....

Read More

experience seeker

ketika sesuatu yang indah datang
semuanya terasa begitu bahagia
namun ketika suatu keindahan itu pergi
semuanya terasa sunyi dan hening

entah mengapa ??
tadi yang kukira indah
tapi kini menjadi sebaliknya
semua yang kuharapkan awal dan akhir akan menjadi indah, tapi??

aku tak mengerti
apakah ini takdir, atau karma ??
yang aku tau ini semua terlalu cepat menimpaku
entah aku harus bagaimana ??

yang bisa kulakukan sekarang hanya sabar dan ikhlas kepadanya
dan aku yakin suatu saat kebahagiaan dan keindahan itu pasti ada dan datang padaku ☺

Read More