Sortir Penyisipan (Insertion Sort)

Nama : Rayhan Fadhillah

NPM  : 45118943

Kelas : 1DC02

Mata Kuliah : Algoritma & Pemrograman A

Dosen : Kunto Bayu A, ST

Sorting adalah proses menyusun elemen – elemen dengan tata urut tertentu dan proses tersebut terimplementasi 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 Sortf

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.

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

Sortir Pemilihan (Selection Sort)

Nama : Rayhan Fadhillah 

NPM  : 45119843

Kelas : 1DC02

Mata Kuliah : Algoritma & Pemrograman A

Dosen : Kunto Bayu A, ST

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.



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

Sortir Penukaran (Exchange Sort)

Nama : Rayhan Fadhillah

NPM  : 45118943

Kelas : 1DC02

Mata Kuliah : Algoritma & Pemrograman A

Dosen : Kunto Bayu A, ST

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

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

Merge Sort

Nama : Rayhan Fadhillah

NPM  : 45118943

Kelas : 1DC02

Mata Kuliah : Algoritma & Pemrograman A

Dosen : Kunto Bayu A, ST

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 :

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

Heap Sort

Nama : Rayhan Fadhillah

NPM  : 45118943

Kelas : 1DC02

Mata Kuliah : Algoritma & Pemrograman A

Dosen : Kunto Bayu A, ST

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 :

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

Quick Sort

Nama : Rayhan Fadhillah

NPM  : 45118943

Kelas : 1DC02

Mata Kuliah : Algoritma & Pemrograman A

Dosen : Kunto Bayu A, ST

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 :

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