Social Icons

Tuesday, April 3, 2012

Jenis-Jenis Penyortiran

1.  BUBBLE SORT
Pengertian “Bubble sort”      
Bubble sort (metode gelembung) adalah metode/algoritma pengurutan dengan dengan cara melakukan penukaran data dengan tepat disebelahnya secara terus menerus sampai bisa dipastikan dalam satu iterasi tertentu tidak ada lagi perubahan. Jika tidak ada perubahan berarti data sudah terurut. Disebut pengurutan gelembung karena masing-masing kunci akan dengan lambat menggelembung ke posisinya yang tepat.
Kelebihan “Bubble sort”
* Metode Buble Sort merupakan metode yang paling simpel
* Metode Buble Sort mudah dipahami algoritmanya

ALGORTIMA BUBBLE SORT
1.      Membandingkan data ke-i dengan data ke-(i+1) (tepat bersebelahan). Jika tidak sesuai maka tukar (data ke-i = data ke-(i+1) dan data ke-(i+1) = data ke-i). Apa maksudnya tidak sesuai? Jika kita menginginkan algoritme menghasilkan data dengan urutan ascending (A-Z) kondisi tidak sesuai adalah data ke-i > data ke-i+1, dan sebaliknya untuk urutan descending (A-Z).
2.      Membandingkan data ke-(i+1) dengan data ke-(i+2). Kita melakukan pembandingan ini sampai data terakhir. Contoh: 1 dgn 2; 2 dgn 3; 3 dgn 4; 4 dgn 5 … ; n-1 dgn n.
3.      Selesai satu iterasi, adalah jika kita sudah selesai membandingkan antara (n-1) dgn n. Setelah selesai satu iterasi kita lanjutkan lagi iterasi berikutnya sesuai dengan aturan ke-1. mulai dari data ke-1 dgn data ke-2, dst.
4. Proses akan berhenti jika tidak ada pertukaran dalam satu iterasi.

Contoh program :
#include<iostream.h>
#include<conio.h>
void Selsort(int X[], int SIZE)
{
int pos,small,temp;
for (int i=0; i<SIZE-1; i++) {
small=X[i];
for (int j=i+1; j<SIZE; j++)
{
if (X[j]<small)
{small=X[j];
    pos=j;}
    }
    temp=X[i];
    X[i]=X[pos];
    X[pos]=temp;
    } }
    void main(void)
    { clrscr();
    int A[10];
    int size;
    cout<<"\n Enter array size :";
    cin>>size;
    cout<<"\n Enter array elements :";
    for (int i=0; i<size; i++)
    {
    cin>>A[i];
    }
    Selsort(A,size);
    cout<<"\n The sorted array is as shown below :";
    for (int l=0; l<size; l++)
    {cout<<A[l];}
    getch();
    }
2.  INSERTION SORT
insertion sort ini memiliki waktu penyelesaian yang lebih cepat di bandingkan selection sort dan buble sort
sedangkan cara kerjanya adalah seperti metode sorting yang lain, yaitu melakukan literasi (pengulangan) hingga hasil yang sesuai ditemukan, namun insertion sort ini akan menginsert atau menyisipkan setiap elemen ketempat yang sesuai (setelah dibandingkan dengan elemen kiri dan kanannya)
atau simpelnya, kita bisa mengumpamakan metode ini seperti orang yang sedang mengurutkan kartu, maka dia akan mengambilnya, satu demi satu dan akan menginsertnya ketempat yang sesuai.

Contoh program :
#include <iostream.h>
#include <conio.h>

#define ELEMENTS 6
void insertion_sort(int x[], int length){
    int key, i;
   for(int j=0; j<length;j++){
            key=x[j];
            i=j-1;
            while(x[i]>key&&i>=0){
                x[i+1]=x[i];
                i--;
            }
            x[i+1]=key;
   }

}

int main(){
    int A[ELEMENTS]={9,2,7,5,4,3};
   int x;
   cout<<"array yang belum di sort:";
   for(x=0;x<ELEMENTS;x++){
           cout<<A[x];
   }
   cout<<endl;
   insertion_sort(A,ELEMENTS);
   cout<<"Array yang sudah di sort:";
   for(x=0;x<ELEMENTS;x++){
           cout<<A[x];
   }
   getch();
   return 0;
}

3.  SELECTION SORT
Pengertian tentang selection sort adalah Algoritma insertion sort pada dasarnya memilah data yang akan diurutkan menjadi dua bagian, yang belum diurutkan (meja pertama), dan yang telah diurutkan (meja kedua). Elemen pertama yang diambil dari bagian array yang belum diurutkan dan kemudian diletakkan pada posisinya sesuai dengan bagian lain dari array yang telah diurutkan. langkah ini dilakukan secara berulang hingga tidak ada lagi elemen yang tersisa pada bagian array yang belum diurutkan.

Contoh program :
#include <conio.h>
#include <stdio.h>
void tampilkan_larik(int data[], int n)
{
int i;
for (i=0;i<n;i++)
cout<<data[i]<<"  ";
cout<<endl<<endl;
}


void selection_sort(int data[], int n)
{
int posmin, posawal, j, tmp;

for(posawal=0;posawal<n-1;posawal++)
    {
   posmin=posawal;
   for (j=posawal+1;j<n;j++)
       if(data[posmin]>data[j])
          posmin=j;

         //tukarkan
           tmp=data[posawal];
         data[posawal]=data[posmin];
         data[posmin]=tmp;

      cout<<"\n Hasil ketika Posawal = "<<posawal<<" : ";
      tampilkan_larik(data,n);

   }
}

int main ()
{
int data[50], i,n;
cout<<"\n@ SIMULASI SELECTION SORT @\n\n\n";
cout<<"=========================================\n";
cout<<"      masukkan banyak data : ";
cin>>n;


clrscr();
for (int a=0;a<n;a++)
    {
   cout<<"\n   masukkan data ke "<<a<<" : ";
   cin>>data[a];
   }
selection_sort(data,n);

//hasil pengurutan

cout<<"\n\n  hasil pengurutan : \n\n";
cout<<"  "; tampilkan_larik(data,n);
cout<<"\n SORTING SELESAI...................";
getch();
clrscr();
cout<<"-----------------------";
cout<<"by: adi wazkitoe, 2010";
cout<<"-----------------------";
getch();
return 0;
}

4.  MERGE SORT
Prinsip utama yang diimplementasikan pada algoritma merge-sort seringkali disebut sebagai pecah-belah dan taklukkan (bahasa Inggris: divide and conquer). Cara kerja algoritma merge sort adalah membagi larik data yang diberikan menjadi dua bagian yang lebih kecil. Kedua larik yang baru tersebut kemudian akan diurutkan secara terpisah. Setelah kedua buah list tersusun, maka akan dibentuk larik baru sebagai hasil penggabungan dari dua buah larik sebelumnya. Menurut keefektifannya, alogaritma ini bekerja dengan tingkat keefektifan O(nlog(n)). Dalam bentuk pseudocode sederhana algoritma ini dapat dijabarkan sebagai berikut.

Contoh program :
#include <iostream.h>
#include <stdio.h>
#include <conio.h>

int data[100];
int d,e;

void mergeSort(int awal, int mid, int akhir)
{
    cout<<endl;
    int temp[100], tempAwal = awal, tempMid = mid, i = 0;
    while(tempAwal < mid && tempMid < akhir)
    {
        if(data[tempAwal] < data[tempMid])
            temp[i] = data[tempAwal],tempAwal++;
        else
            temp[i] = data[tempMid],tempMid++;
        i++;
    }
    while(tempAwal < mid)
        temp[i] = data[tempAwal],tempAwal++,i++;
    while(tempMid < akhir)
        temp[i] = data[tempMid],tempMid++,i++;
    for(int j=0,k=awal;j<i,k<akhir;j++,k++)
        cout<<data[k]<<' '<<temp[j]<<endl, data[k] = temp[j];
}

void merge(int awal, int akhir)
{
    if(akhir-awal != 1)
    {
        int mid = (awal+akhir)/2;
        merge(awal, mid);
        merge(mid, akhir);
        mergeSort(awal, mid, akhir);
    }
}

int main()
{
    int d,e;
    int n;
    cout<<"Masukan banya data = ";cin>>n;
    cout<<"Masukan data yang akan di susun = ";
    for(int i=0;i<n;i++)
        cin>>data[i];
    merge(0,n);
    for(int i=0;i<n;i++)
        cout<<data[i]<<' ';
    getch();
    return 0;
    scanf("%d", d,e);
}


5.  HEAP SORT
HeapSort adalah algoritma pengurutan data berdasarkan perbandingan, dan termasuk golongan selection sort.

Walaupun lebih lambat daripada quick sort pada kebanyakan mesin , tetapi heap sort mempunyai keunggulan yaitu kompleksitas algoritma pada kasus terburuk adalah n log n.

Algoritma pengurutan heap sort ini mengurutkan isi suatu larik masukan dengan memandang larik masukan sebagai suatu Complete Binary Tree (CBT).
Setelah itu Complete Binary Tree (CBT) ini dapat dikonversi menjadi suatu heap tree. Setelah itu Complete Binary Tree (CBT) diubah menjadi suatu priority queue.
Contoh program :
#include <iostream.h>
#include <stdio.h>
#include <conio.h>
void read(int a[10],int n)
{
    cout<<"reading\n";
    for(int i=0;i<n;i++)
        cin>>a[i];
}
void display(int a[10],int n)
{
    for(int i=0;i<n;i++)
        cout<<a[i]<<"\t";
}
void shellsort(int a[10],int n)
{
    int gap=n/2;
    do
    {
        int swap;
        do

        {
            swap=0;
            for(int i=0;i<n-gap;i++)
                if(a[i]>a[i+gap])
                {
                    int t=a[i];
                    a[i]=a[i+gap];
                    a[i+gap]=t;
                    swap=1;
                }
        }
        while(swap);
    }
    while(gap=gap/2);
}
void main()
{
    int a[10];
    int n;
    clrscr();
    cout<<"enter n\n";
    cin>>n;
    read(a,n);
    cout<<"before sorting\n";
    display(a,n);
    shellsort(a,n);
    cout<<"\nafter sorting\n";
    display(a,n);
    getch();
}




6.  QUICK SORT
Algoritma sortir yang efisien yang ditulis oleh C.A.R. Hoare pada 1962. Dasar strateginya adalah “memecah dan menguasai”. Quicksort dimulai dengan menscan daftar yang disortir untuk nilai median. Nilai ini, yang disebut tumpuan (pivot), kemudian dipindahkan ke satu sisi pada daftar dan butir-butir yang nilainya lebih besar dari tumpuan di pindahkan ke sisi lain.
Contoh program :
#include <iostream.h>
#include <conio.h>
#define max 20

void quick_sort(int darr[max], int lb, int ub)
{
  int a;
   int up,down;
   int temp;

   if (lb>=ub)
    return;
   a=darr[lb];
   up=ub;
   down=lb;

   while (down < up)
   {
     while (darr[down] <= a)
       down++;
      while (darr[up]>a)
       up--;
      if(down<up)
      {
        temp=darr[down];
         darr[down]=darr[up];
         darr[up]=temp;
      }
   }
   darr[lb]=darr[up];
   darr[up]=a;

   quick_sort(darr,lb,up-1);
   quick_sort(darr,up+1,ub);
}

void main()
{
  int arr[max];
   int i,n,lb,ub;
   lb=0;

   cout<<"Masukkan banyak data yang ingin diurut: ";
   cin>>n;

   ub=n;
   cout<<"Masukkan data-datanya: \n\n";
   for(i=1;i<=n;i++)
   {
     cout<<"\tdata ke- "<<i<<" : "; cin>>arr[i];
   }

   quick_sort(arr,lb,ub);
   cout<<"\nHasil pengurutan data: ";
   for(i=0; i<n;i++)
    cout<<" "<<arr[i];

   cout<<"\n\nTekan sembarang tombol untuk keluar ";
   getch();
}


7.  BUCKET SORT
Bucket sort adalah algoritma sorting yang bekerja dengan partisi array ke dalam jumlah terbatas sort. Setiap kotak ini kemudian diurutkan secara individual, baik menggunakan algoritma sorting yang berbeda, atau dengan rekursif menerapkan algoritma bucket sort. Sebuah variasi dari metode ini disebut semacam hitungan tunggal buffered lebih cepat dari jenis cepat dan membutuhkan waktu sekitar waktu yang sama untuk berjalan pada set data.
Contoh program :
#define NUMELTS 100
#include <stdio.h>
#include <iostream.h>

class element
{
public:
    int value;
    element *next;
    element()
    {
    value=NULL;
    next=NULL;
    }
};

class bucket
{
public:
element *firstElement;
bucket()
{
firstElement = NULL;
}
};

void main()
{
    int lowend=0;
    int highend=100;
    int interval=10;
    const int noBuckets=(highend-lowend)/interval;
    bucket *buckets=new bucket[noBuckets];
    bucket *temp;

    for(int a=0;a<noBuckets;a++)
    {
        temp=new bucket;
        buckets[a]=*temp;
    }

    cout<<"--------The Elements to be Sorted using Bucket sort are ------------------\n";
    int array[]={12,2,22,33,44,55,66,77,85,87,81,83,89,82,88,86,84,88,99};

    for(int j=0;j<19;j++)
    {
    cout<<array[j]<<endl;
    element *temp,*pre;
    temp=buckets[array[j]/interval].firstElement;
        if(temp==NULL)
        {
            temp=new element;
            buckets[array[j]/interval].firstElement=temp;
            temp->value=array[j];
        }
        else
        {
            pre=NULL;
                while(temp!=NULL)
                   {
               if(temp->value>array[j])
                   break;
                   pre=temp;
                   temp=temp->next;
                   }
                if(temp->value>array[j])
                {
                    if(pre==NULL)
                    {
                        element *firstNode;
                        firstNode=new element();
                        firstNode->value=array[j];
                        firstNode->next=temp;
                        buckets[array[j]/interval].firstElement=firstNode;
                    }
                    else
                    {
                        element *firstNode;
                        firstNode=new element();
                        firstNode->value=array[j];
                        firstNode->next=temp;
                        pre->next=firstNode;
                    }
                }
                else
                {
                    temp=new element;
                    pre->next=temp;
                    temp->value=array[j];
                }

        }
 }

    cout<<"------------------------The Sorted Elements Are---------------\n";
    for(int jk=0;jk<10;jk++)
    {
        element *temp;
        temp= buckets[jk].firstElement;
            while(temp!=NULL)
            {
                cout<<"*"<<temp->value<<endl;
                temp=temp->next;
            }
    }
    cout<<"--------------------------------END--------------------------------\n";

}



8.  RADIX SORT
Radix Sort merupakan salah satu algoritma Non-Comparasion Sort (pengurutan tanpa pembandingan). Proses ynang dilakukan dalam metode ini adalah mengklasifikasikan data sesuai dengan kategori terurut yang tertentu, dan tiap kategori dilakukan pengklasifikasian lagi, dan seterusnya sesuai kebutuhan, lalu subkategori-kategori tersebut digabungkan kembali. 
Secara harfiah Radix dapat diartikan sebagai posisi dalam angka, karena metode ini pertamakalinya mengurutkan nilai-nilai input berdasarkan radix pertamanya, lalu pengurutan dilakukan berdasarkan radix keduanya, dan begitu seterusnya. Pada system decimal, radix adalah digit dalam angka decimal.
Berikut ini adalah contoh penggunaan algoritma radix sort untuk pengurutan sebuah kumpulan bilangan bulat positif.
Contoh program :
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
kekosongan radix (int a [], int n, int m){

typedef struct simpul
{
int data;
struct simpul * berikutnya;
NODE};

Node * ptr, * awal, * prev;
Node * depan [10], * belakang [10];
int k = 1, i, j, y, p;;
/ * Membuat linked list awal * /
mulai = NULL;
for (i = 0; i <n; + + i)
{
ptr = (Node *) malloc (sizeof (NODE));
ptr-> data = a [i];
ptr-> next = NULL;
if (mulai == NULL)
start = ptr;
lain
prev-> next = ptr;
prev = ptr;
}

/ * Radix sort * /

for (i = 1; i <= m; + + i)
{
for (j = 0; j <10; + + j)
depan [j] = NULL;
/ * Menempatkan elemen ke antrian * /
ptr = mulai;
sementara (ptr! = NULL)
{Y = ptr-> data / k% 10 ;/ * y adalah angka * /
jika (depan [y] == NULL)
{
depan [y] = ptr;
belakang [y] = ptr;
}
lain
{
belakang [y] -> next = ptr;
belakang [y] = ptr;
}

ptr = ptr-> next;
}

mulai = NULL;
for (j = 0; j <10; + + j)
jika (depan [j] = NULL!)
{
if (mulai == NULL)
start = depan [j];
lain belakang [p] -> next = depan [j];
p = j;
}
belakang [p] -> next = NULL;
k = k * 10;
}
/ * Menyalin kembali ke array * /
ptr = mulai;
for (i = 0; i <n; + + i, ptr = ptr-> berikutnya)
a [i] = ptr-> data;

}

void main ()
{
int a [100], n, i, m;
suhu arang;
melakukan
{
clrscr ();
printf ("=========================== RADIX SORT ================== ========================= \ n ");
printf ("ENTER JUMLAH ANGKA DAN JUMLAH DIGIT \ n");
scanf ("% d% d", & n, & m);
printf ("ENTER UNSUR \ n");
for (i = 0; i <n; + + i)
scanf ("% d", & a [i]);
radix (a, n, m);
printf ("daftar diurutkan \ n");
for (i = 0; i <n; + + i)
printf ("% d", a [i]);
printf ("\ nAnda ingin melanjutkan [y / n]? \ n");
scanf ("% c", & temp);


} Sementara (temp == 'y' | | temporer == 'Y');
printf ("\ n --------------------------------------------- ------------------------------------ \ n ");
getch ();
}




9.  SHELL  SORT
Distribusi sort mengacu pada algoritma sorting dimana data didistribusikan dari input untuk struktur peralihan beberapa yang kemudian dikumpulkan dan ditempatkan pada output.

Contoh Source Codenya :
#include<conio.h>
#include<iostream.h>
#define n 10

class shellsort{
  static int A[n];
public:
  void InsSort(int start, int step);
  void ShellSort();
  void tampil();
};

int shellsort::A[n]={20,23,120,56,78,50,12,89,10,12};

void shellsort::InsSort(int start, int step)
{
  int i,j,y;
  bool ketemu;

  i=start+step;
  while(i<=n)
  {
     y=A[i];
     j=i-step;
     ketemu=false;
     while((j>=0)&&(!ketemu))
     {
        if(y<A[j])
        {
           A[j+step]=A[j];
           j=j-step;
        }
        else
           ketemu=true;
     }
     A[j+step]=y;
     i=i+step;
  }

}

void shellsort::ShellSort()
{
   int step,start;
   step=n;
   while(step>1)
   {
      step=step/3+1;
      for(start=1;start<=step;start++)
             shellsort::InsSort(start,step);
   }
}

void shellsort::tampil(){
for(int a=0;a<10;a++)
    {
       cout<<A[a]<<" ";
    }
    cout<<endl<<endl;
}

void main()
{
    shellsort x;
    cout<<"PENGURUTAN SHELL"<<endl<<endl;
    cout<<"Sebelum diurut : "<<endl<<"A = ";
    x.tampil();
    x.ShellSort();
    cout<<"Setelah diurut : "<<endl<<"A = ";
    x.tampil();
    getch();
}




10.SHUFFLE SORT
Shuffle sort dapat dianggap sebagai pembentukan pohon yang sangat luas, seperti B-tree dengan m = n / 8, untuk memilah efisien dalam banyak kasus.

Shuffle sort  memperkirakan distribusi barang yang akan diurutkan dengan memeriksa n / 8 item pertama. Semacam partisi distributif memperkirakan distribusi dengan mendekati median dan interpolasi linear dari minimum untuk median dan dari median untuk maksimal.

Contoh Source Codenya  :
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int main ()
{
  int iSecret, iGuess;

  /* initialize random seed: */
  srand ( time(NULL) );

  /* generate secret number: */
  iSecret = rand() % 10 + 1;

  do {
    printf ("Guess the number (1 to 10): ");
    scanf ("%d",&iGuess);
    if (iSecret<iGuess) puts ("The secret number is lower");
    else if (iSecret>iGuess) puts ("The secret number is higher");
  } while (iSecret!=iGuess);

  puts ("Congratulations!");
  return 0;

}
readmore...
Subscribe to: Posts (Atom)