Materi Shorting, Bubble Short, Quick Short, dan Marge Short.

SORTING

Pengertian Sorting

Pengurutan (Sorting) merupakan proses pengurutan sekumpulan data dalam suatu    urutan tertentu.

Sorting dipakai untuk:
1.Membantu proses pencarian (searching)
2.Menyelesaikan masalah-masalah kompleks seperti penjadwalan (scheduling), pengolahan basis data, riset operasi, dsb.

Jenis-jenis Shorting :

1. Metode Pemograman Bubble Sort dengan C++

Metode bubble sort, merupakan metode tersederhana untuk melakukan pengurutan data, tetapi memiliki kinerja yang terburuk untuk data yang besar. Pengurutan dilakukan dengan membandingkan sebuah bilangan dengan seluruh bilangan yang terletak sesudah bilangan tersebut. Penukaran dilakukan kalau suatu kriteria dipenuhi.

Sebagai contoh, terdapat kumpulan seperti berikut.
25 57 48 37 12 92 80 33
Contoh proses pengurutan dengan urut naik ditunjukkan pada gambar





Pengurutan tahap pertama




Pengurutan tahap kedua

Jika jumlah data adalah n, maka terjadi n-1 tahap pengurutan. Berarti pada contoh di di atas diperlukan 7 tahap pengurutan. Gambar 11.4 memperlihatkan setelah 7 tahap pengurutan dilakukan.




Keadaan di setiap tahap pengurutan

Implementasikan pengurutan dengan metode buble sort baik dalam algoritma maupun program

Algoritma :
SUBRUTIN bubble_sort(L,n)
      Untuk tahap = 1 s/d n-1
        Untuk j← 0 s/d n-tahap-1
          Jika L[j] > L[j+1] MAKA
            // Lakukan penukaran
            tmp ←L[j]
            L[j] ←L[j+1]
            L[j+1] ←tmp
          AKHIR – JIKA
        AKHIR – UNTUK
      AKHIR – UNTUK
    AKHIR – SUBRUTIN

Implementasi dalam bahasa pemograman C++

#include <iostream.h>
#include <conio.h>
void tampilkan_larik(int data[], int n)
{
int i;
for(i=0;i<n;i++)
cout<<data[i]<<" ";
cout<<"\n";
}

void buble_sort(int data[],int n)
{
int tahap,j,tmp;
for (tahap=1;tahap<n;tahap++)
{
for (j=0;j<n-tahap;j++)
if (data[j]>data[j+1])
{
//tukarkan
tmp=data[j];
data[j]=data[j+1];
data[j+1]=tmp;
}
cout<<"hasil tahap "<<tahap<<" : ";
tampilkan_larik (data,n);
}
}

int main()
{
const jum_data=8;
int i;
int data[]={25,57,48,37,12,92,80,33};

buble_sort(data, jum_data);

//hasil pengurutan
cout<<endl;
cout<<"Hasil Pengurutan: \n";
tampilkan_larik(data,jum_data);
getch();
}

Gambar Program Setelah Dieksekusi :

2. Quick Sort dan Contoh

Quick Sort merupakan salah satu algoritma pengurutan data yang menggunakan teknik membagi  data menjadi partisi-partisi. Metode Quick Sort disebut juga dengan nama partition exchange sort.

Untuk memulai proses pengurutan, pertama-tama sebuah data dipilih dari kelompok data sebagai data pivot. Posisi data pivot dapat dicari dengan menggunakan rumus :

    i  = (indeks awal + indeks akhir) div 2

Kemudian elemen-elemen data akan diatur, sehingga nilai data pivot yang terletak di posisi ke I memenuhi kondisi sebagai berikut :

Semua data di posisi ke 1 sampai dengan ke I-1  lebih kecil atau sama dengan pivot atau data[i]<=pivot.

Semua data di posisi ke I+1 sampai dengan ke N  lebih besar atau sama dengan pivot atau data[i]>=pivot.

Contoh  :

Ada  12 data  sebagai berikut :

indeks     1      2      3    4   5     6     7      8     9    10   11   12

Data        33   99   18    7   5    45   57    25   55   10   40   50

Pos = (1+12) div 2 = 6

Pivot = data[ pos]  = 45

Data 45 terpilih sebagai data pivot. Setelah diatur, maka posisi urutan data sebagai berikut :

indeks     1      2      3    4   5     6     7      8     9    10   11   12

Data        33   25    18   7   5    10   40     45  55   50   57   99

Dimana :

Semua elemen di posisi ke 1 sampai dengan posisi ke 8   lebih kecil atau sama dengan nilai 45.

Semua elemen di posisi ke 9  lebih besar atau sama dengan 45.

Dengan demikian, data tersebut akan terpecah menjadi 2 partisi, satu partisi di sisi kiri 57 dan satu partisi di sisi kanan 57 sebagai berikut :  

                                      [33   25    18   7   5    10   40   ]    45     [55   50   57   99]

Dengan cara yang sama, proses  partisi diulangi lagi untuk masing-masing partisi  baik  di sisi kanan maupun di sisi kanan. Jadi setiap partisi yang diperoleh akan dipartisi lagi hingga diperoleh hasil pengurutan data.

Dalam proses partisi dengan metode quick sort dapat selesaikan  dengan menggunakan prosedur rekursi. Karena proses partisi dengan cara sama selalu diulangi. Proses partisi dibentuk dalam sebuah prosedur atau fungsi dan akan memanggil dirinya sendiri.

Animasi dari proses Quick sort seperti pada gambar dibawah ini :

Kode program pascal untuk mengurutkan data dengan metode quick sort adalah sebagai berikut :

program quicksorting;

uses

crt;

type

Matrix = array[1..100] of integer;

Procedure input(var d:matrix;var n :integer);

var

code,k :integer;

i:string;

begin

  randomize;

  write(' Jumlah data  = ');readln(n);

  for k:=1 to n do

    Begin

      d[k]:=random(100);

      write(d[k], '  ');

    End; writeln;

end;

Procedure tukardata(var a,b : integer);

var t :integer;

begin

    t:=a;a:=b;b:=t;

end;

Procedure cetak(d:matrix;c:integer);

var

i:integer;

begin

   for i:=1 to c do

   write(d[i]:5);

   writeln;

end;

procedure quicksort(var d:matrix; a,b:integer);

var

a1,b1,pivot: integer;

begin

   a1:=a; b1:=b;

   pivot:=d[(a+b) div 2];

   repeat

     while(d[a1]     while(d[b1]>pivot) do dec(b1);

     if (a1<=b1) then

        begin

          tukardata(d[a1],d[b1]);

          inc(a1);

          dec(b1);

        end;

   until (a1>b1);

   cetak(d,b);

   if (a < b1) then quicksort(d, a, b1);

   if (a1 < b ) then quicksort(d,a1, b);

end;

{Program Utama}

var

data :matrix;

n:integer;

begin

clrscr;

  input(data,n);

  writeln('Proses Sorting Data');

  cetak(data,n);

  quicksort(data,1,n);

  writeln;

  writeln('Hasil Sorting Data ');

  cetak(data,n);

  readkey;

end.

Output  program :

3. Marge Short

Algoritma lain yang menggunakan Divide and Conquer dalam pengurutan adalah Merge Sort.

Secara   konseptual,  untuk  sebuah array  berukuran  n,
Merge Sort bekerja sebagai berikut:
1.  Jika  bernilai  0   atau   1,   maka  array  sudah   terurut.

2.   Jika Array tidak terurut, bagi menjadi 2 sub-array dengan ukuran n/2

3. Urutkan setiap sub array. Jika sub array tidak cukup kecil lakukan langkah kedua dengan rekursif

4. Menggabungkan sub array menjadi satu array

Berikut ini implementasi sederhana dari Algoritma Merge Sort dengan C++ dan Tool yang digunakan Code Block 8.02

#include <iostream>

using namespace std;
void merge(int low, int mid, int up);
void mergeSort(int low, int up);
int a[50];
int main()
{
int jumlahBil,i;
cout<<"Masukkan Jumlah element Array"<< endl;
cin>>jumlahBil;
for(int i=0; i<jumlahBil;i++)
{
cout<<"Bilangan ke-"<< i+1 << endl;
cin>>a[i];
}
mergeSort(1,jumlahBil);
for(i=1;i<=jumlahBil;i++)
cout<<a[i]<<"    ";
cout<<endl;
return 0;
}
void merge(int low, int mid, int up)
{
int h, i,j,k;
int b[50];
h = low;
i = low;
j = mid+1;
while((h<=mid)&&(j<=up))
{
if(a[h] < a[j])
{
b[i]=a[h];
h++;
}
else
{
b[i]=a[j];
j++;
}
i++;
}
if(h>mid)
{
for(k=j;k<=up;k++){
b[i]=a[k];
i++;
}
}
else
{
for(k=h;k<=mid;k++)
{
b[i]=a[k];
i++;
}
}
for(k=low;k<=up;k++) a[k]=b[k];
}
void mergeSort(int low, int up)
{

int mid;
if(low<up)
{
mid=(low+up)/2;
mergeSort(low,mid);
mergeSort(mid+1,up);
merge(low,mid,up);
}
}




Sumber : https://7seasons.wordpress.com/tag/merge-sort-bubble-short-quick short/