Senin, 03 Oktober 2016

SORTING

SORTING

I. Pengertian Sorting
   Sorting adalah proses menyusun elemen – elemen dengan tata urut tertentu dan proses tersebut terimplementasi dalam bermacam aplikasi.Sebagai contohnya aplikasi perpustakaan, apliaksi tersebut dapat melakukan sorting secara ascending agar pengguna dapat mencari buku dengan mudah. Dengan banyaknya penggunaan sorting dan sangan mendasarnya proses sorting, maka beberapa macam algoritma sorting telah dibuat dan dikembangkan sebagai berikut :

      1. Bubble Sort
          Bubble Sort di sini menggunakan konsep gelembung sabun yang ada di permukaan air. Karena berat jenis air lebih berat daripada berat jenis gelembung sabun maka gelembung sabun akan terapung keatas permukaan. 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.

Dengan Contoh Algoritma :

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.


Dalam contoh Program C :

#include
#include
#include
bubble_acak()
{
clrscr();
int arr[1000];
int x, i; //untuk array
int s, t, temp; //untuk sorting
//input jumlah data yang diproses
cout<<"angka yang akan dimasukkan : "; cin>>x;
//input nilai masing" array
srand(time(NULL));
for (i=0; i
arr[i] = rand() %1000;
//output nilai" array
clrscr();
cout<<"====== array ======"<
cout<<"angka angkanya :"<
for (i=0; i
cout<
//sorting
cout<
cout<<"====== sorting ======"<
s = 0;
for (s=0; s
{
for (t = s+1; t
{
if (arr[s]>arr[t])
{
temp = arr[s];
arr[s] = arr[t];
arr[t] = temp;
}
}
}
cout<<"setelah sorting :"<
for (i=0; i
cout<
getch();
}
bubble_manual()
{
clrscr();
int arr[1000];
int x, i; //untuk array
int s, t, temp; //untuk sorting
//input jumlah data yang diproses
cout<<"angka yang akan dimasukkan : "; cin>>x;
//input nilai masing" array
for (i=0; i
{
cout<<"masukkan angka ke-"<
cin>>arr[i];
}
//output nilai" array
clrscr();
cout<<"====== array ======"<
cout<<"angka angkanya :"<
for (i=0; i
cout<
//sorting
cout<
cout<<"====== sorting ======"<
s = 0;
for (s=0; s
{
for (t = s+1; t
{
if (arr[s]>arr[t])
{
temp = arr[s];
arr[s] = arr[t];
arr[t] = temp;
}
}
}
cout<<"setelah sorting :"<
for (i=0; i
cout<
//mission complete
getch();
}
main ()
{
int pilih;
char ulang;
do
{
clrscr ();
cout<<"tekan 1 : bilangan yang disorting dimasukan secara acak"<
cout<<"tekan 2 : bilangan yang disorting dimasukan secara manual"<
cout<<"masukkan pilihan : "; cin>>pilih;
switch (pilih)
{
case 1:
bubble_acak();
break;
case 2:
bubble_manual();
break;
default:
clrscr();
cout<<"\"maaf\""<
cout<<"\"pilihan yang dimasukkan salah\"";
break;
}
cout< "; cin>>ulang;
}

Kelebihan Bubble Sort :

– Metode Buble Sort Merupakan Metode Yang Paling Simpel

– Metode Buble Sort Mudah Dipahami Algoritmanya

– Mudah Untuk Diubah Menjadi Kode.

– Definisi Terurut Terdapat Dengan Jelas Dalam Algoritma.

– Cocok Untuk Pengurutan Data Dengan Elemen Kecil Telah Terurut

 Kelemahan Bubble Sort :

       Meskipun Simpel Metode Bubble Sort Merupakan Metode Pengurutan Yang Paling Tidak Efisien. Kelemahan Buble Sort Adalah Pada Saat Mengurutkan Data Yang Sangat Besar Akan Mengalami Kelambatan Luar Biasa, Atau Dengan Kata Lain Kinerja Memburuk Cukup Signifikan Ketika Data Yang Diolah Jika Data Cukup Banyak. Kelemahan Lain Adalah Jumlah Pengulangan Akan Tetap Sama Jumlahnya Walaupun Data Sesungguhnya Sudah Cukup Terurut. Hal Ini Disebabkan Setiap Data Dibandingkan Dengan Setiap Data Yang Lain Untuk Menentukan Posisinya.


            2.Selection Sort
    Pengurutan dilakukan dengan memilih elemen terbesar dan menempatkan pada posisinya,kemudian mencari element terbesar berikutnya dan menempatkan pada tempatnya, dan
seterusnya.  Pengertian dari selection sort adalah mencari elemen yang tepat untuk diletakkan di posisi yang telah diketahui, dan meletakkannya di posisi tersebut setelah data tersebut ditemukan,
Selection Sort Membandingkan elemen yang sekarang dengan elemen yang berikutnya sampai dengan elemen yang terakhir. Jika ditemukan elemen lain yang lebih kecil dari elemen sekarang 
maka dicatat posisinya dan kemudian ditukar.
Pengurutan data dalam struktur data sangat penting untuk data yang beripe data numerik ataupun karakter.Pengurutan dapat dilakukan secara ascending (urut naik) dan descending (urut turun) Pengurutan (Sorting) adalah proses menyusun kembali data yang sebelumnya telah disusun dengan suatu pola tertentu, sehingga tersusun secara teratur menurut aturan tertentu.Metode ini memiliki konsep memilih data yang maksimum/minimum dari suatu kumpulan data larik L, lalu menempatkan data tersebut ke elemen paling akhir atau paling awal sesuai pengurutan yang diinginkan. Data maksimum/minimum yang diperoleh, diasingkan ke tempat lain, dan tidak diikutsertakan pada proses pencarian data maksimum/minimum berikutnya. 

Algoritma pengurutan dengan metode selection sort adalah sebagai berikut :
  1. Cari data terkecil dalam interval j = 0 sampai dengan j = N-1
  2. Jika pada posisi pos ditemukan data yang terkecil, tukarkan data diposisi pos dengan data di posisi i jika k.
  3. Ulangi langkah 1 dan 2 dengan j = j + i sampai dengan j = N-1, dan seterusnya sampai j = N - 1.

Program C :

void selectionsort(int arr[ ]) {
   int i,j;
   for (i = 0; i < N; i++) {
      int min = arr[i];
      int pos = i;
      for (j = i; j < N; j++) {
 
           /* Cari nilai yang terkecil */
           if (arr[j] < min) {
           min = arr[j];
           pos = j;
        }
      }
      
      /* Tukar nilai terkecil ke arr[i] jika pos tdk sama i */
      if(i!=pos) {
         int temp = arr[i];
         arr[i] = arr[pos];
         arr[pos] = temp;
       }
    }
} 





Kelebihan dari selection sort :

1. Algoritma ini sangat rapat dan mudah untuk diimplementasikan.
2. Operasi pertukarannya hanya dilakukan sekali saja.
3. Waktu pengurutan dapat lebih ditekan.
4. Mudah menggabungkannya kembali.
5. Kompleksitas selection sort relatif lebih kecil.

Kekurangan dari selectiion sort :

1. Membutuhkan method tambahan.
Diposting oleh di

Tidak ada komentar:

Posting Komentar

Langganan: Posting Komentar (Atom)