Sorting Array

Pengertian Sorting Array

Sorting (pengurutan) didefinisikan:

– proses menyusun elemen – elemen dengan tata urut tertentu dan proses tersebut terimplementasi dalam bermacam aplikasi.

– proses menyusun kembali data yang sebelumnya telah disusun dengan suatu pola tertentu, sehingga tersusun secara teratur menurut aturan tertentu.

Kita ambil contoh pada aplikasi perbankan. Aplikasi tersebut mampu menampilkan daftar account yang aktif. Hampir seluruh pengguna pada sistem akan memilih tampilan daftar berurutan secara ascending demi kenyamanan dalam penelusuran data.

Macam algoritma sorting telah dibuat karena proses tersebut sangat mendasar dan sering digunakan. Oleh karena itu, pemahaman atas algoritma-algoritma yang ada sangatlah berguna.

Metoda Pengurutan

Buble Sort

Buble Sort merupakan metode sorting termudah. Di beri nama “Buble” karena prose pengurutan secara berangsur-angsur bergerak/ berpindah ke posisinya yang tepat, seperti gelembung yang keluar dari sebuah gelas bersoda. Buble sort mengurutkan data dengan cara membandingkan elemen sekarang dengan elemen berikutnya.

Program di bawah ini untuk mengurutkan data dari data terbesar yang sudah teridentifikasi!!!#include <iostream.h>#include <stdlib.h>

void bubbleSort(int arr[]);

int main()

{

int nums[] = { 5, 7, 8, 3, 20, 11, 90, 17, 21, 19 };

int k;

cout << ” BEFORE SORT: “;

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

cout << nums[k] << ” “;

bubbleSort(nums);

cout << endl << endl;

cout << ” AFTER SORT: “;

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

cout << nums[k] << ” “;

cout << endl << endl << endl;

system(” PAUSE”);

}// end main()

void bubbleSort(int a[])

{

int last =8;

int temp;

while (last >= 0)

{

for (int k = 0; k <= last; k++)

if (a[k] < a[k+1])

{

temp=a[k];

a[k]=a[k+1];

a[k+1]=temp;

}

last–;

}

}// end bubbleSort()

Exchange Sort

Exchange Sort sangat mirip dengan Bubble Sort. Perbedaan antara mereka berdua terletak pada bagaimana mereka membandingkan antar elemen.

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 sebelum/ sesudahnyaitu akan menjadi pusat (pivot) untuk dibandingkan dengan elemen sebelumnya/ sesudahnya lagi, begitu seterusnya.

Program di bawah ini untuk mengurutkan data dari data terbesar yang sudah teridentifikasi!!!#include <stdlib.h>#include <iostream.h>

main()

{

int data[]={1,8,49,5,7,8,5,2,3,0};

int temp,i,j;

cout<<” BEFORE SORT: “;

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

cout<<data[i]<<” “;

cout<<endl<<endl;

cout<<” AFTER SORT: “;

for (i=0; i<10-1; i++)

{

for(j = (i+1); j<10; j++)

{

if (data [i] < data[j])

{

temp=data[i];

data[i]=data[j];

data[j]=temp;

}

}

}

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

{

cout<<data[i]<<” “;

}

cout<<endl<<endl;

system(” PAUSE”);

Selection Array

Selection Sort merupakan kombinasi antara sorting dan searching. Dimana dalam setiap proses, akan di cari elemen-elemen yang belum di urutkan yang memiliki nilai terkeil atau terbesar akan dipertukarkan ke posisi yang tepat di dalam array.

Program di bawah ini untuk mengurutkan data dari data terkecil sampai terbesar!!!#include <stdlib.h>#include <iostream.h>

main()

{

int data[100];

int temp,i,j,n,pos;

cout<<” Berapa data yang ingin anda urutkan!!! “;

cin>>n;

cout<<endl;

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

{

cout<<” Bilangan ke-“<<(i+1)<<” : “;

cin>>data[i];

}

cout<<endl<<” BEFORE SORT: “;

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

cout<<data[i]<<” “;

cout<<endl<<endl;

cout<<” AFTER SORT: “;

for(int i=0;i<n-1;i++)

{

pos = i;

for(int j=i+1;j<n;j++)

{

if(data[j] < data[pos])

pos = j; //ascending

}

if(pos != i)

{

temp=data[i];

data[i]=data[pos];

data[pos]=temp;

}

}

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

{

cout<<data[i]<<” “;

}

cout<<endl<<endl;

system(” PAUSE”);

}

Heap Sort

Karakteristik dari algoritma pengurutan heap sort adalah bahwa dalam implementasinya heap sort menggunakan heap tree agar dapat diselesaikan secara

heapsort. Oleh karena itu, untuk mengimplementasikan algoritma pengurutan heap sort dalam suatu program aplikasi, dibutuhkan adanya alokasi dinamis dengan menggunakan struktur data tree (pohon).

Insertion Sort

Merupakan sorting yang paling sederhana yang mirip dengan cara orang mengurutkan kartu. Selembar demi selembar kartu di ambil dan disisipkan (insert) ke tempay yang seharusnya. Pengurutan Pengurutan dimulai dari data ke-2 sampai dengan data terakhir, jika ditemukan data yang lebih kecil, maka akan ditempatkan (diinsert) diposisi yang seharusnya.

Program di bawah ini untuk mengurutkan data dari data terkecil sampai terbesar!!!#include <stdlib.h>#include <iostream.h>

main()

{ int data[100];

int temp,i,j,n,pos;

cout<<” Berapa data yang ingin anda urutkan!!! “;

cin>>n;

cout<<endl;

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

{

cout<<” Bilangan ke-“<<(i+1)<<” : “;

cin>>data[i];

}

cout<<endl<<” BEFORE SORT: “;

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

cout<<data[i]<<” “;

cout<<endl<<endl;

cout<<” AFTER SORT: “;

for(int i=1;i<n;i++)

{

temp = data[i];

j = i -1;

while(data[j]>temp && j>=0)

{

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

j–;

}

data[j+1] = temp;

}

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

{

cout<<data[i]<<” “;

}

cout<<endl<<endl;

system(” PAUSE”);

}

Merge Sort

Merge Sort mengadaptasi dari pola divide and Conquer. Dimana pada tiap rekursi, pola tersebut terdiri atas 3 langkah; divide yaitu memilah masalah menjadi sub masalah; conquer yaitu menyelesaikan sub masalah dengan rekursif. Jika sub-masalah tersebut cukup ringkas dan sederhana, pendekatan penyelesaian secara langsung akan lebih efektif; kombinasi yaitu mengkombinasikan dari sub-masalah yang akan membimbing menuju penyelesaian atas permasalahn utama.

Program di bawah ini untuk mengurutkan data dari data terkecil sampai terbesar yang sudah teridentfikasi!!!#include <iostream.h>#include <stdlib.h>

void mergeSort(int arr1[], int arr2[], int arr3[], int size1, int size2, int& size3);

void swap(int& x, int& y);

int main()

{

int nums1[] = { 3, 7, 9, 15, 19, 23 };

int nums2[] = { 1, 5, 11, 17, 21, 25, 29, 31 };

int nums3[15];

int size1 = 6;

int size2 = 8;

int size3;

int k;

cout << “ARRAY 1: “;

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

cout << nums1[k] << ” “;

cout << endl << endl;

cout << “ARRAY 2: “;

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

cout << nums2[k] << ” “;

mergeSort(nums1, nums2, nums3, size1, size2, size3);

cout << endl << endl;

cout << “MERGED ARRAY 3: “;

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

cout << nums3[k] << ” “;

system(“PAUSE”);

return 0;

}// end main()

void mergeSort(int arr1[], int arr2[], int arr3[], int size1, int size2, int& size3)

{

int pos1 = 0, pos2 = 0, pos3 = 0;

while (pos1 < size1 && pos2 < size2)

if (arr1[pos1] < arr2[pos2])

arr3[pos3++] = arr1[pos1++];

else

arr3[pos3++] = arr2[pos2++];

if (pos1 < size1)

while (pos1 < size1)

arr3[pos3++] = arr1[pos1++];

else

while (pos2 < size2)

arr3[pos3++] = arr2[pos2++];

size3 = size1 + size2;

}// end mergeSort()

void swap(int& x, int& y)

{

int temp;

temp = x;

x = y;

y = temp;

}// end swap()

Quick Sort

Quick Sort bersifat divide&conquer yang erupakan metode pencarian yang sangat cepat (saat ini tercepat)

Shell Sort

Shell sort merupakan metode pertambahan menurun yang dikembangkan oleh Donald L. Shell (1959). Shell sort mengurutkan data dengan cara membandingkan suatu data dengan data lain yang memiliki jarak tertentu sehingga dibentuk sub-list, kemudian dilakukan pertukaran jika diperlukan.

Program di bawah ini untuk mengurutkan data dari data terkecil sampai terbesar yang sudah teridentifikasi!!#include <conio.h>#include <iostream.h>

void tukar (int *a, int *b)

{

int t = *a;

*a = *b;

*b=t;

}

void shell_sort(int a[], int size)

{

int jarak=size;

int did_swap;

int j;

while (jarak>0)

{

jarak=jarak/2;

do

{

did_swap=1;

for(j=0;j<size-jarak;j++)

{

if (a[j]>a[j+jarak])

{

tukar(&a[j],&a[j+jarak]);

did_swap=0;

}

}

}

while (did_swap==0);

}

}

void main()

{

int i;

int n=9;

int data[9]={12,35,9,11,3,7,23,15,31};

cout<<endl;

cout<<” BEFORE SORT “<<endl;

cout<<”    “;

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

{

cout<<” “<<data[i];

}

cout<<endl<<endl;

cout<<” AFTER SORT “<<endl<<”    “;

shell_sort(data,n);

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

{

cout<<” “<<data[i];

}

getche();

}

Sumber :

http://lecturer.ukdw.ac.id/anton/download/TIstrukdat3.pdf.

http://webmail.informatika.org/~rinaldi/Stmik/Makalah/MakalahStmik08.pdf.

http://poss.ipb.ac.id/files/JENI-Intro2-Bab06-Algoritma%20Sorting.pdf.

http://202.148.14.148/dedy/SP.doc.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s