Minggu, 19 Oktober 2014

Algoritma Sorting

Nama : Akmal Alfarisi
NPM : 50414710
Kelas : 1IA17
Mata Kuliah : Algoritma & Pemrograman 1A
Dosen : Kunto Bayu A,ST

Sorting adalah proses menyusun elemen – elemen dengan tata urut tertentu dan proses tersebutterimplementasi dalam bermacam aplikasi. Pengaplikasian sorting banyak kita jumpai diberbagai aktifitas, misal mengurutkan NIM, Nama negara, Kota dan Lain sebagainya.

Secara umum, sortir dapat dilakukan terhadap suatu urutan bilangan, ataupun urutan abjad.

 Ada 2 kategori sortir berdasarkan media yang digunakan, yaitu :


 1. Sortir Internal

    Data yang akan disortir kecil, sehingga proses Sortir tidak membutuhkan

    tempat yang besar di memori utama komputer.


2. Sortir Eksternal

    Data yang disortir cukup besar , sehingga membutuhkan media atau alat

    tambahan, seperti Magnetik tape, disket dan sebagainya.

 Dua hal yang sangat mempengaruhi kecepatan Algoritma Sortir, yaitu :
1. Jumlah operasi perbandingan yang dilakukan.
2. Jumlah operasi pemindahan data dilakukan.

Ada beberapa teknik yang dapat dilakukan dalam melakukan Sortir, yaitu :
1. Sortir Penyisipan (Insertion Sort)
2. Sortir Pemilihan (Selection Sort)
3. Sortir Penukaran (Exchange Sort)
4. Merge Sort
5. Heap Sort
6. Quick Sort
7. Bucket Sort
8. Radix Sort
9. Shell Sort
10. Shuffle Sort

Berikut penjelasannya !

1. Sortir Penyisipan (Insertion Sort)

Prinsip dasar metode ini adalah secara berulang-ulang memasukkan setiap data ke dalam tempatnya yang benar.

Algoritmanya :

          For i := 2 to n do
                Begin
                x := a[i]
                Lalu letakkan x pada tempat yang benar dalam urutan a[1] .. a[i]
                End

Untuk memasukkan x ke dalam tempat yang sebenarnya maka harus dilakukan perbandingan-perbandingan dan pemindahan-pemindahan secara bergantian.
Jadi x akan bergeser ke kiri dengan membandingkan  nilai x dengan nilai a[j] berikutnya dan kemudian x di-insert ke dalam tempatnya atau a[j] dipindahkan ke kanan.
Hal ini diteruskan untuk unsur-unsur di sebelah kiri a[j].

Proses ini akan  berhenti bila salah satu dari kedua hal ini berlaku, yaitu :
1. Salah satu unsur a[j] mempunyai key yang lebih kecil dari x.
2. Bagian ujung kiri tabel telah dicapai.

Prosedur Insertion :











Kompleksitas Algoritma Sortir Penyisipan
              C
 (Jumlah Operasi
   Perbandingan)
            M
(Jumlah Pemindahan  
        Data)
Hal Terbaik (Best Case)
n - 1
2 (n -1)
Rata-rata (Average Case)
(n2 + 3n - 4) / 4
(n2 + 7n - 8) / 4
Hal Terburuk (Worst Case)
(n2 + n ) / 2-1
(n2 + 3n - 4) / 2

Keadaan terbaik bila data awal sudah terurut dari kecil ke besar.
Keadaan terburuk terjadi bila data pada saat awal mempunyai urutaan terbalik dari besar ke kecil.

2.  Sortir Pemilihan (Selection Sort)

Algoritma Selection Sort bekerja berdasarkan prinsip berikut :
1. Pilih data dengan key terkecil.
2. Tukarkan data tersebut dengan a[1].
3. Kemudian ulangi hal tersebut dengan n -1 data yang ada kecuali a[1]. lalu dengan n - 2 data kecuali a[1] dan a[2] dan seterusnya.

Algoritmanya :

          for  i := 1 to n - 1
          begin
                   Pilih unsur yang terkecil dari a[i] .. a[n] dengan indeks k
                   Tukarkan a[k] dan a[i]
          end;

Jadi pada setiap langkah ke- i, maka data a[1] sampai dengan a[i], sudah terurut dari data yang yang paling kecil ke besar.
Dengan demikian langkah selanjutnya hanya diperhatikan dat a[i+1] sampai dengan a[n] saja.

Prosedur Selection :








Kompleksitas Algoritma Sortir Pemilihan
              C
 (Jumlah Operasi
   Perbandingan)
            M
(Jumlah Pemindahan  
        Data)
Hal Terbaik (Best Case)
n (n - 1) / 2
3 (n - 1)
Rata-rata (Average Case)
n (n - 1) / 2
O(n log n)
Hal Terburuk (Worst Case)
n (n - 1) / 2
Trunc(n /4) + 3(n-1)




Perbedaan antara Insertion Sort dan Selection Sort
·        Insertion Sort setiap langkah hanya diperhatikan satu data kemudian untuk mencari tempat data diletakkan, dilihat semua data yang akan menjadi tujuan.
·        Selection Sort setiap langkah dipilih data dari semua barisan sumber data kemudian diletakkan sebagai data baru pada array tujuan.

3. Sortir Penukaran (Exchange Sort)

a. Bubble Sort 1 (Sortir Gelembung)

Pensortiran dengan metode Bubble Sort adalah pensortiran tahap pertahap, maksudnya kita harus menyelesaikan 1 posisi terlebih dahulu baru kemudian posisi berikutnya diselesaikan.Misalnya ada n bilangan maka akan dilakukan n - 1 kali letak penyortiran.
Letak pertama menggunakan indeks I=1, letak kedua menggunakan indeks I=2 dan seterusnya sampai letak ke (n-1) yang menggunakan indeks I = n-1.
Pada letak pertama ,digunakan indeks J=1, J=2 sampai J=n.
Pada letak kedua, digunakan indeks J=2, J=3 sampai J=n.
Sampai seterusnya, atau pada umumnya, nilai indeks J bergerak dari J=I sampai ke J=n.
Indeks ini menunjukkan letak pada penyortiran, setiap kali letak berindeks J dibandingkan dengan letak indeks I.
Berdasarkan pembandingan itulah, ditentukan ada tidaknya pertukaran antara letak.

Prosedur Bubblesort1:









b. Bubble Sort 2
Pada algoritma Bubble Sort 2, pada setiap iterasi diperiksa dua data yang bersebelahan.
Bila urutan tidak dipenuhi, kedua data tersebut saling bertukar tempat.
Pada akhir setiap iterasi, data terkecil yang ada pada sisa tabel telah bergeser kebagian kiri dari tabel.

Prosedur Bubblesort2:







Kompleksitas Algoritma Sortir Gelembung
              C
 (Jumlah Operasi
   Perbandingan)
            M
(Jumlah Pemindahan  
        Data)
Hal Terbaik (Best Case)
n (n - 1) / 2
O
Rata-rata (Average Case)
n (n - 1) / 2
3n (n - 1) / 4
Hal Terburuk (Worst Case)
n (n - 1) / 2
3n (n - 1) / 4


4. Merge Sort 
Pengertian : yaitu metode yang 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 hasill penggabungan dari dua buah larik sebelumnya.Menurut keefektifannya, algoritma ini bekerja dengan tingkat keefektifan O(nlog(n)).

Contoh Program Merge Sort :

#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);
}
  Contoh Gambar Merge Sort :



5. Heap Sort
Pengertian : Metode pengurutan data berdasarkan perbandingan.Walaupun metode ini lebih lambat daripada quick sort tapi heap sort memiliki keunggulan tersendiri yaitu pada kasus terburuknya adalah n log n.Heap Sort ini mengurutkan isi suatu larik masukan denganmemandang larik masukan sebagai suatu Complate Binary Tree(CBT).Lalu CBT ini dapat dikonversi menjadi suatu heap tree.Dan akhirnya CBT akan diubah menjadi suatu Priority Queue.

Contoh Program Heap Sort :

#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();
}
Contoh Gambar Heap Sort :


6. Quick Sort
Pengertian : Metode ini dimulai dengan menscan daftar yang disortir untuk nilai median.Nilai ini yang disebut tumpuan atau (pivot), kemudian dipindahkan ke satu sisi pada daftar dan butir-butir yang nilainya lebih besar dari tumpuan di pindahkan ke sisi lain.

Contoh Program Quick Sort :

#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();
}

Contoh Gambar Quick Sort :



7. Bucket Sort
Pengertian : 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 menerapkan algoritma bucket sort.Variasi dari metode ini disebut semacam hitungan tunggal buffered lebih cepat dan membutuhkan waktu sekitar yang sama untuk berjalan pada set data.

Contoh Program Bucket Sort :

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

Contoh Gambar Bucket Sort :
8. Radix Sort
Pengertian : Yaitu merupakan salah satu algoritma Non-Comparasion Sort (pengurutan tanpa pembandingan).Proses yang 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 tersebut digabungkan kembali. Metode ini pertama kalinya mengurutkan nilai-nilai input berdasarkan radix pertamanya,lalu pengurutan dilakukan bersarkan radix keduanya,dan begitu seterusnya. Pada sistem desimal radix adalah digit dalam angka desimal.

Contoh Program Radix Sort :

#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 ();
}
  
Contoh Gambar Radix Sort :
















9. Shell Sort
Pengertian : shell sort mengacu pada algoritma sorting dimana data didistribusikan dari input untuk struktur peralihan beberapa yang kemudian dikumpulkan dan ditempelkan pada output.

Contoh Program Shell Sort :

#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();
}

Contoh Gambar Shell Sort :
















10. Shuffle Sort
Pengertian : shuffle sort memperkirakan distribusi barang yang akan di urutkan dengan memeriksa n/ 8item pertama. Semacam partisi distributif dengan mendekati median dan interpolasi linear dari minimum untuk median dan dari median untuk maksimal.

Contoh Program Shuffle Sort :

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

}

Contoh Gambar Shuffle Sort :





















Sumber : sariny.staff.gunadarma.ac.id/Downloads/files/.../BAB+6+TSORTIR.DOC
                 http://includeryokom.blogspot.com/2012/04/jenis-jenis-penyortiran-beserta.html


0 komentar:

Posting Komentar