Thursday, October 26, 2017

Pembahasan Lengkap Delapan Shorting Arry

Sorting atau pengurutan data adalah proses yang sering harus dilakukan dalam pengolahan data. Sort dalam hal ini diartikan mengurutkan data yang berada dalam suatu tempat penyimpanan, dengan urutan tertentu baik urut menaik (ascending) dari nilai terkecil sampai dengan nilai terbesar, atau urut menurun (descending) dari nilai terbesar sampai dengan nilai terkecil.

Sorting adalah proses pengurutan data yang memiliki dua macam metode dalam proses pengurutan:

  1. Pengurutan internal (internal sort), yaitu pengurutan terhadap sekumpulan data yang disimpan dalam media internal komputer yang dapat diakses setiap elemennya secara langsung. Dapat dikatakan sebagai pengurutan tabel
  2. Pengurutan eksternal (external sort), yaitu pengurutan data yang disimpan dalam memori sekunder, biasanya data bervolume besar sehingga tidak mampu untuk dimuat semuanya dalam memori.
Dalam courseware ini, hanya akan dibahas algoritma pengurutan internal, dengan data berada dalam array satu dimensi.

Algoritma pengurutan internal yang utama ada sekitar delapan diantaranya:

  • Bubble Sort
  • Selection Sort
  • Insertion Sort
  • Shell Sort
  • Merge Sort
  • Radix Sort
  • Quick Sort
  • Heap Sort
Dalam courseware ini kita hanya akan membahas dua metode sort yang dianggap paling sederhana dan mudah, yaitu: Bubble Sort dan Insertion Sort.

Bubble Sort

Bubble sort adalah proses pengurutan sederhana yang bekerja dengan cara berulang kali membandingkan dua elemen data pada suatu saat dan menukar elemen data yang urutannya salah. Ide dari Bubble sort adalah gelembung air yang akan "mengapung" untuk table yang terurut menaik (ascending). Elemen bernilai kecil akan "diapungkan" (ke indeks terkecil), artinya diangkat ke "atas" (indeks terkecil) melalui pertukaran. Karena algoritma ini melakukan pengurutan dengan cara membandingkan elemenelemen data satu sama lain, maka bubble sort termasuk ke dalam jenis algoritma comparison-based sorting.

Proses dalam Bubble sort dilakukan sebanyak N-1 langkah (pass) dengan N adalah ukuran array. Pada akhir setiap langkah ke – I , array L[0..N] akan terdiri atas dua bagian, yaitu bagian yang sudah terurut L[0..I] dan bagian yang belum terurut L[I+1..N-1]. Setelah langkah terakhir, diperoleh array L[0..N-1] yang terurut menaik.

Contoh:

#include <iostream.h>
#include <iomanip.h>
void main ()
{
     int nilai[8];
     int temp;
     cout<<"Data sebelum diurutkan"<<endl;
     for (int ctr=1;ctr<=8;ctr++)
     {
          cout<<"Masukkan Data ke "<<ctr<<" : ";
        cin>>nilai[ctr];
     }
     cout<<endl;
    cout<<endl;
     for (int i=0;i<=8;i++)
    {
          for (int ii=0;ii<=8;ii++)
        {
            if (nilai[ii]>nilai[ii+1])
                {
                     temp=nilai[ii];
                     nilai[ii]=nilai[ii+1];
                     nilai[ii+1]=temp;
                }
          }
     }
     cout<<"Data setelah diurutkan"<<endl;
          for (int iii=0;iii<8;iii++)
          {
                cout<<setw(3)<<nilai[iii];
          }
}


Insertion Sort

Insertion sort adalah sebuah algoritma pengurutan yang membandingkan dua elemen data pertama, mengurutkannya, kemudian mengecek elemen data berikutnya satu persatu dan membandingkannya dengan elemen data yang telah diurutkan. Karena algoritma ini bekerja dengan membandingkan elemen-elemen data yang akan diurutkan, algoritma ini termasuk pula dalam comparison-based sort. Ide dasar dari algoritma Insertion Sort ini adalah mencari tempat yang "tepat" untuk setiap elemen array, dengan cara sequential search. Proses ini kemudian menyisipkan sebuah elemen array yang diproses ke tempatnya ang seharusnya. Proses dilakukan sebanyak N-1 tahapan (dalam sorting
disebut sebagai "pass"), dengan indeks dimulai dari 0.

Proses pengurutan dengan menggunakan algoritma Insertion Sort dilakukan dengan cara membandingkan data ke-i (dimana i dimulai dari data ke-2 sampai dengan data terakhir) dengan data berikutnya. Jika ditemukan data yang lebih kecil maka data tersebut disisipkan ke depan sesuai dengan posisi yang seharusnya.

contoh:
#include <iostream.h>
#include <conio.h>
int data[10],data2[10];
int n;
void tukar(int a, int b)
{
    int t;
    t = data[b];
    data[b] = data[a];
    data[a] = t;
}
void insertion_sort()
{
    int temp,i,j;
    for(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;
    }
}
void main()
{
    cout<<"  PROGRAM INSERTION SORT"<<endl;
    cout<<"Masukkan Jumlah Data : ";    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cout<<"Masukkan data ke "<<i<<"   : ";    cin>>data[i];
        data2[i]=data[i];
    }
    insertion_sort();
    cout<<"Data Setelah di Sort : ";
    for(i=1; i<=n; i++)
    {
        cout<<" "<<data[i];
    }
}


EmoticonEmoticon