3 metode sorting [struktur data]

SHELL SORT

Shell sort merupakan suatu bentuk improvisasi dari insertion sort. Metode ini pertama kali di buat oleh seseorang yang bernama Donald L.Shell. Sesuai dengan namanya program sorting tersebut di beri nama shell sort. Metode ini mengurutkan data dengan cara membandingkan suatu data dengan yang lain yang memiliki jarak tertentu, kemudian dilakukan penukaran jika diperlukan.Cara kerja shell sort adalah sebagai berikut :

1. Pertama, metode ini menentukan jarak dari suatu elemen yang akan di tentukan, kemudian di tukarkan. Biasanya jarak elemen yang akan di tentukan, di tentukan dengan cacah data = n di bagi 2. Elemen-elemen yang di pisahkan tersebut di bandingkan kemudian di pisahkan
2. Kedua, setelah Kemudian dilakukan perulangan dari j=1 sampai N/2, pada
3. masing-masing pengulangan dilakukan pembandingan antara data yg ke-j dengan data ke-(j+N/2).
4. Ketiga, Bila data ke-j lebih besar dari data ke (j+n/2), kemudian harus di tukar
5. Keempat, Proses berikutnya sama, gunakan jarak (N/2)/2 atau N/4 dan kemudian N/8 dst, hingga N=1

Analisis shell sort

Pseudo code :

shellsort(itemType a[], int l, int r)

{ int i, j, h; itemType v;

int incs[16] = { 1391376, 463792, 198768, 86961, 33936,

13776, 4592, 1968, 861, 336,

112, 48, 21, 7, 3, 1 };

for ( k = 0; k < 16; k++)

for (h = incs[k], i = l+h; i <= r; i++)

{

v = a[i]; j = i;

while (j > h && a[j-h] > v)

{ a[j] = a[j-h]; j -= h; }

a[j] = v;

}

}

Output {336,861,1968,4592,13776,33936,86961,198768,463792,1391376}

Contoh program  shell sort :

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

void shellsort(int a[],int n)
{
int j,i,k,m,tengah;
for(m = n/2;m>0;m/=2)
{
for(j = m;j< n;j++)
{
for(i=j-m;i>=0;i-=m)
{
if(a[i+m]>=a[i])
break;
else
{
tengah = a[i];
a[i] = a[i+m];
a[i+m] = tengah;
}
}
}
}
}

main()
{
int a[10],i,n;
clrscr();

printf(“Berapa banyak angka yang ingin anda masukkan\t: “);
scanf(“%d”,&n);
for(i=0;i< n;i++)
{
printf(“\nAngka ke %d\t: “,i+1);
scanf(“%d”,&a[i]);
}

printf(“\nAngka sebelum pengurutan: “);
for(i=0;i< n;i++)
printf(“%5d”,a[i]);
shellsort(a,n);

printf(“\nAngka setelah pengurutan: “);
for(i=0;i< n;i++)
printf(“%5d”,a[i]);
getch();
return 0;
}

QUICK SORT

Metode quick sort adalah metode pengurutan yang menggunakan partisi. Quick sort juga banyak di gunaka untuk proses sorting karena lbh mudah dan cepat. Pada metode ini, data dibagi menjadi dua bagian, yaitu data disebelah kiri partisi selalu lebih kecil dari data disebelah kanan. Namun data pada kedua partisi belum terurut, sehingga untuk mengurutkannya, proses pengurutan dilakukan pada kedua partisi secara terpisah. Selanjutnya, data di sebelah kiri dan kanan dipartisi lagi. Berikut adalah rincian mengenai cara kerja dari quick sort :

1. 1. Pilih satu data sebarang sebagai data partisi, misalkan x.
2. 2. Baca data dari ujung kanan ke kiri sampai ditemukan data a[i] sehingga a[i] < x.
3. 3. (partisi kiri).
4. 4. Baca data dari ujung kiri ke kanan sampai ditemukan data a[j] sehingga a[j] >= x.
5. 5. (partisi kanan).
6. 6. Tukar kedua data a[i] dan a[j].
7. 7. Ulangi proses di atas sampai seluruh data terbagi dua bagian kiri yang lebih kecil dari x dan kanan yang lebih besar dari x.

Prinsip dasar dari quicksort adalah melakukan partisi dari data, dalam dua bagian. Kemudian secara rekursif melakukan sorting pada kedua bagian data tersebut. Algoritma quicksort adalah sebagai berikut:

1. 1. Tentukan unsur partisi yang diperlukan (gunakan data tengah sebagai unsure partisi).
2. 2. Partisi data dalam dua bagian yang dipisahkan oleh unsur partisi.
3. 3. Secara rekursif sort terhadap kedua bagian data diatas dengan dengan metode
4. 4. partisi (ulangi langkah 1 dan 2 untuk data sebelah kiri dan kanan).

Analisis dari quicksort

Bahsa manusia	Bahasa Algoritmik
Mendeklarasikan array yang berisi bilangan	Array [1…10] of integer tabint <- {34,67,23,28,98,15,89,67,28,18}
Mendeklarasikan prosedur quicksort i merupakan counter untuk penelusuran kiri dan j merupakan counter untuk penelusuran kanan perulangan proses pengurutan, dilakukan sampai i lebih besar dari j selama nilai penelusuran kiri lebih kecil dari dari nilai penelusuran kanan, penelusuran kiri maju selama nilai penelusuran kanan lebih besar dari nilai penelusuran kiri, penelusuran kanan maju jika i lebih kecil j, maka nilai penelusuran kiri ditukar dengan nilai penelusuran kanan jika subbagian kiri mempunyai elemen, dilakukan pengurutan pada subpohon kiri jika subbagian kanan mempunyai elemen, dilakukan pengurutan pada subbagian kanan	Procedure quicksort(input : integer 1,integer r) Integer i Integer j i <- 1 j <- r repeat while tabInti < tabInt1 do i <- i +1 {end while} While tabintj > tabint1 do j <- j -1 {end while} if i<j then integer temp temp <- tabinti tabinti <- tabintj i <- i + 1 j <- j – 1 {end if} Until (i>j) if 1<j then quicksor(1,j) {end if} if i<r then quicksort(i,r); {end if} {end procedure}
Mendeklarasikan prosedur menulis isi tabInt ke layer	Procedure tulis ( ) integer i for i <- 1 to 10 do write (tabInti) {end for} {end procedure}
Mendeklarasikan program utama yang menampilkan isi tabInt sebelum dan sesudah diurutkan	{program utama} tulis ( ) Quicksort(1,10) tulis ( ) {end program utama}

Contoh program quick sort :

#include<stdio.h>

#include<conio.h>

#include<stdlib.h>

#include<string.h>

//————————————————————————–

void baca_list(int a[],int n)

{

int i;

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

{

printf(“\n\n\t Masukkan angka ke [%d] :: “,i);

scanf(“%d”,&a[i]);

}

}

//————————————————————————–

void cetak_list(int a[],int n)

{

int i;

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

printf(“\n\n\t %d”,a[i]);

}

//————————————————————————–

void quick_sort(int a[],int first,int last)

{

int low,high,temp,pivot;

low=first;

high=last;

pivot=a[(first+last)/2];

do

{

while(a[low]<pivot)

low++;

while(a[high]>pivot)

high–;

if(low<=high)

{

temp=a[low];

a[low]=a[high];

a[high]=temp;

low=low+1;

high=high-1;

}

}while(low<=high);

if(first<high)

quick_sort(a,first,high);

if(low<last)

quick_sort(a,low,last);

}

//————————————————————————–

void main()

{

int a[20],n;

textcolor(10);

clrscr();

printf(“\n\n\t Masukkan berapa angka yg anda mau :: “);

scanf(“%d”,&n);

baca_list(a,n);

printf(“\n\n\t Angka-angka yang anda input :: “);

cetak_list(a,n);

quick_sort(a,0,n-1);

printf(“\n\n\t angka yang sudah di sorting :: “);

cetak_list(a,n);

getch();

}

//————————————————————————–

HEAP SORT

Metode heap sort adalah metode dari pengembangan tree. Heap sort memiliki kecepatan O(NlogN). Heap sort melakukan suatu pengurutan menggunakan suatu struktur data yang di sebut heap. Heap memiliki kompleksitas yang besar dalam pembuatan kodenya, tetapi heap sort mampu mengurutkan data-data yang sangat banyak dengan waktu yang cepat. Dalam sorting biasanya mempunyai sebuah aturan, berikut adalah aturan dari heap sort :

1. 1. Untuk mengisikan heap dimulai dari level 1 sampai ke level dibawahnya, bila dalam level yang sama semua kunci heap belum terisi maka tidak boleh mengisi dibawahnya.
2. 2. Heap dlm kondisi terurut apabila left child <> parent.
3. 3. Penambahan kunci diletakkan pada posisi terakhir dari level dan disebelah kanan child yg terakhir, kemudian diurutkan dengan cara upheap.
4. 4. Bila menghapus heap dgn mengambil kunci pada parent di level 1 kemudian digantikan posisi kunci terakhir, selanjutnya disort kembali metode downheap.

Berikut adalah langkah-langkahnya dari metode heap sort :

Dalam langkah-langkahnya heap sort terbagi menjadi 2 langkah yaitu insert_heap dan build_heap,

Insert_heap :

Pada bagian ini bertujuan untuk penghapusan suatu simpul pada heap tree. pemilihan sebuah simpul untuk ditempatkan di posisi yang lebih atas, dan menjaga tree tersebut tetap sebuah heaptree.

Berikut langkahnya :

1. 1. Setiap simpul yang dihapus(low) dicari anaknya yang memiliki kunci terbesar/terkecil(large)
2. 2. Anak dengan kunci yang lebih besar dipromosikan ke tempat simpul yang di hapus.
3. Langkah 1 dan 2 akan di lakukan berulang kali sampai simpul yang dihapus tidak punya anak lagi atau simpul yang ingin dipromosikan lebih besar/kecil daripada anak dari simpul yang dihapus yang memiliki kunci terbesar/terkecil.

Build Heap :

Pada bagian ini kita akan merapikan data-data yang telah acak tadi, sehingga membentuk heap yang sempurna. kita dapat menggunakan fungsi insert_heap untuk memasukkan setiap masukan ke bagian heap yang terdiri dari semua masukan yang masuk. Sehingga jadilah heap yang sempurna.

Analisis heap sort :

Pseudocode :

Insert heap :

procedure Max-Heapify(A, i)

**turn almost-heap into a heap

**pre-condition: tree rooted at A[i] is almost-heap

**post-condition: tree rooted at A[i] is a heap

lc   leftchild(i)

rc   rightchild(i)

if lc _ heapsize(A) and A[lc] > A[i] then

largest   lc

else

largest   i

if rc _ heapsize(A) and A[rc] > A[largest] then

largest   rc

if largest 6= i then

exchange A[i] $ A[largest]

Max-Heapify(A, largest)

Build heap :

procedure Build-Max-Heapify(A)

**turn an array into a heap

heapsize(A)   length[A]

for i

_length[A]

2

_

downto 1

do Max-Heapify(A, i)

Main heap sort :

procedure Heapsort(A)

**post-condition: sorted array

Build-Max-Heap(A)

for i   length[A] downto 2 do

exchange A[1] $ A[i]

heapsize(A)   heapsize(A) − 1

Max-Heapify(A, 1)

Contoh program heap sort :

#include<stdio.h>

#include<conio.h>

#include<stdlib.h>

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

typedef struct heap

{

int val;

struct heap *left,*right;

}*TR;

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

TR new_node()

{

TR new;

new=malloc(sizeof(struct heap));

new->left=new->right=NULL;

return(new);

}

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

TR get_node()

{

TR new;

new=new_node();

printf(“\n\n\t Masukkan angka :: “);

scanf(“%d”,&new->val);

return(new);

}

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

void insert_node(TR temp,TR new)

{

if(temp->val>new->val)

if(temp->left!=NULL)

insert_node(temp->left,new);

else

temp->left=new;

else

if(temp->right!=NULL)

insert_node(temp->right,new);

else

temp->right=new;

}

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

void heap_sort(TR temp)

{

if(temp!=NULL)

{

heap_sort(temp->left);

printf(“%d\t”,temp->val);

heap_sort(temp->right);

}

}

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

TR create()

{

TR head,new,temp;

char c;

head=new_node();

new=get_node();

head->left=new;

printf(“\n\n\t Tambah angka lainnya (Y/N) :: “);

c=getche();

while(c==’y'||c==’Y')

{

new=get_node();

insert_node(head->left,new);

printf(“\n\n\t Tambah angka lainnya (Y/N) :: “);

c=getche();

}

return(head);

}

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

void main()

{

TR head;

int choice;

textcolor(10);

while(1)

{

clrscr();

printf(“\n\n\t ******* MENU *******”);

printf(“\n\n\t 1> READ LIST”);

printf(“\n\n\t 2> HEAP SORT”);

printf(“\n\n\t 3> KELUAR”);

printf(“\n\n\t PILIH :: “);

scanf(“%d”,&choice);

switch(choice)

{

case 1:head=create();

break;

case 2:printf(“\n\n\t YANG UDAH DI SORTING :: “);

printf(“\n\n\t “);

heap_sort(head->left);

break;

case 3:printf(“\n\n\t TEKAN ESC KEY UNTUK KELUAR”);

if(getch()==27)

exit(0);

break;

}

getch();

}

}

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

Download via word:
 

Ini adalah daftar perbandingan dari beberapa algoritma sorting :

Name	Best	Average	Worst	Memory			Stable	Method		Other notes
HTUBubble sortUTH	O(n)	—	O(nP2P)	O(1)			Yes	Exchanging		Times are for best variant
HTUCocktail sortUTH	O(n)	—	O(nP2P)	O(1)			Yes	Exchanging
HTUComb sortUTH	O(n log n)	—	O(n log n)	O(1)			No	Exchanging
HTUGnome sortUTH	O(n)	—	O(nP2P)	O(1)			Yes	Exchanging
HTUSelection sortUTH	O(nP2P)	O(nP2P)	O(nP2P)	O(1)			No	Selection
HTUInsertion sortUTH	O(n)	—	O(nP2P)	O(1)			Yes	Insertion
HTUShell sortUTH	O(nlog(n))	—	O(nlogP2P(n))	O(1)			No	Insertion	Times are for best variant
HTUBinary tree sortUTH	O(nlog(n))	—	O(nlog(n))	O(1)			Yes	Insertion
HTULibrary sortUTH	O(n)	O(nlog(n))	O(nP2P)	O(n)			Yes	Insertion
HTUMerge sortUTH	O(nlog(n))	—	O(nlog(n))	O(n)			Yes	Merging
In-place HTUmerge sortUTH	O(nlog(n))	—	O(nlog(n))	O(1)			Yes	Merging	Times are for best variant
HTUHeapsortUTH	O(nlog(n))	—	O(nlog(n))	O(1)			No	Selection
HTUSmoothsortUTH	O(n)	—	O(nlog(n))	O(1)			No	Selection
HTUQuicksortUTH	O(nlog(n))	O(nlog(n))	O(nP2P)	O(log n)			No	Partitioning	Naive variants use O(n) space
HTUIntrosortUTH	O(nlog(n))	O(nlog(n))	O(nlog(n))		O(logn)	No		Hybrid