BUBLE DAN QUICK SHOT

BUBLE DAN QUICK SHOT

QUICk SHOT

       1.      Pengertian Quick Shot

Quick Sort merupakan suatu algoritma pengurutan data yang menggunakan teknik pemecahan data menjadi partisi-partisi, sehingga metode ini disebut juga dengan nama partition exchange sort. Untuk memulai irterasi pengurutan, pertama-tama sebuah elemen dipilih dari data,  kemudian elemen-elemen data akan diurutkan diatur sedemikian rupa.

Algoritma ini mengambil salah satu elemen secara acak (biasanya dari tengah) yang disebut dengan pivot lalu menyimpan semua elemen yang lebih kecil di sebelah kiri pivot dan semua elemen yang lebih besar di sebelah kanan pivot. Hal ini dilakukan secara rekursif terhadap elemen di sebelah kiri dan kanannya sampai semua elemen sudah terurut.

2. Algoritma Quick Sort.

• Pilih satu elemen secara acak sebagai pivot
• Pindahka semua elemen yang lebih kecil ke sebelah kiri pivot dan semua elemen yang lebih besar ke sebelah kanan pivot. Elemen yang nilainya sama bisa disimpan di salah satunya.
• Lakukan sort secara rekursif terhadap sub-array sebelah kiri dan kanan pivot

3. Tips Pemilihan Pivot. 

Dalam algoritma quick sort, pemilihan pivot adalah hal yang menentukan apakah algoritma quick sort tersebut akan memberikan performa terbaik atau terburuk. Berikut beberapa cara pemilihan pivot :

• Pivot adalah elemen pertama, elemen terakhir, atau elemen tengah tabel. Cara ini hanya bagus jika elemen tabel tersusun secara acak, tetapi tidak bagus jika elemen tabel semula sudah terurut. Misalnya, jika elemen tabel semula menurun, maka semua elemen tabel akan terkumpul di upatabel kanan.
• Pivot dipilih secara acak dari salah satu elemen tabel. Cara ini baik, tetapi mahal, sebab memerlukan biaya (cost) untuk pembangkitan prosedur acak. Lagi pula, itu tidak mengurangi kompleksitas waktu algoritma.
• Pivot adalah elemen median tabel. Cara ini paling bagus, karena hasil partisi menghasilkan dua bagian tabel yang berukuran seimbang (masing masing ≈ n/2 elemen). Cara ini memberikan kompleksitas waktu yang minimum. Masalahnya, mencari median dari elemen tabel yang belum terurut adalah persoalan tersendiri. Algoritma Quick Sort terdiri dari dua prosedur, yaitu prosedur PARTISI dan prosedur QUICKSORT

4. Keunggulan Quick sort:

• Secara umum memiliki kompleksitas O(n log n).
• Algoritmanya sederhana dan mudah diterapkan pada berbagai bahasa pemrograman dan arsitektur mesin secara efisien.
• Dalam prakteknya adalah yang tercepat dari berbagai algoritma pengurutan dengan perbandingan, seperti mergesort dan heapsort.
• Melakukan proses langsung pada input (in-place) dengan sedikit tambahan memori.
• Bekerja dengan baik pada berbagai jenis input data (seperti angka dan karakter).

5. Kekurangan Quick short

• Sedikit kesalahan dalam penulisan program membuatnya bekerja tidak beraturan (hasilnya tidak benar atau tidak pernah selesai).
• Memiliki ketergantungan terhadap data yang dimasukkan, yang dalam kasus terburuk memiliki kompleksitas O(n2).
• Secara umum bersifat tidak stable, yaitu mengubah urutan input dalam hasil akhirnya (dalam hal inputnya bernilai sama).
• Pada penerapan secara rekursif (memanggil dirinya sendiri) bila terjadi kasus terburuk dapat menghabiskan stack dan memacetkan program.
• Pada bahasa pemrograman, quicksort ada dalam pustaka stdlib.h untuk bahasa C, dan class TList dan TStringList dalam Delphi (Object Pascal) maupun FreePascal.

6. Contoh Pengurutan Quick Short

dalam hal ini saya punya angka sebagai berikut. 

•  langkah pertama adalah tentukan pivotnya. dalam hal ini adalah saya memilih angka 7

• kemudian buatpartisi buat masing2 angka sebelah kanan dan kiri

• kemudian gunakan algoritma quicksort yang ada diatas. jika angka lebih kecil dari pivot maka akan diletakan sebelah kiri dan jika lebih besar maka letakan disebelah kanan. langkah pertama adalah bandingkan angka 9 dengan pivot apakah lebih kecil atau lebih besar. 

•  karena angka 9 lebih besar maka letakan angka 9 setelah pivot.

• lanjut ke angka 4. bandingkan angka 4 dengan pivot. 

•  karena angka 4 lebih kecil dari 7 maka posisi tetap.

•  lanjut ke angka 2. cek apakah angka 2 lebih kecil atau lebih besar dari pivot. 

• karena angka 2 lebih kecil dari pivot maka letaknya tetap

• bandingkan pivot dengan angka 10. cek angka 10 lebih besar atau lebih kecil dari pivot.

• karena angka 10 lebih besar maka posisi tetap sebelah kanan

• lanjut ke angka 1. cek angka 1 lebih kecil atau lebih besar dari pivot.

• karena lebih kecil maka pindah ke sebelah kiri pivot.

• lanjut ke angka 5. cek apakah angka 5 lebih kecil atau lebih besar dari angka pivot.

• karena angka 5 lebih kecil maka pindah ke sebelah kiri pivot. 

•  setelah itu masuk ke dalam partisi baru. sampai sini proses belum selesai.

•  tentukan pivot untuk masing-masing partisi

• perbandingan untuk pivot pertama. angka 2. cek apakah angka 2 lebih kecil atau lebih besar dari pivot.

• karena angka 2 lebih kecil dari pivot maka pindahkan ke kiri pivot

•  lanjut ke angka 1. cek apakah angka lebih besar atau lebih kecil dari pivot.

• karena angka 1 lebih kecil maka pindahkan disebelah kiri angka pivot.

• lanjut ke angka 5. cek apakah angkanya lebih besar atau lebih kecil dari pivot.

• karena lebih besar maka posisinya tetap. untuk partisi pertama selesai

• ulangi langkah2 seperti sebelumnya untuk pivot partisi ke 2. dan hasil akhir dari quick sort ini adalah seperti ini :

7. Listing Program

using namespace std; void quick_sort(int[],int,int); int partition(int[],int,int); int main() { int n,i; n =7; int a[]={9,4,2,7,10,1,5}; cout<<"\nData sebelum pengurutan:\n"; for(i=0;i<n;i++) cout<<a[i]<<" , "; quick_sort(a,0,n-1); cout<<"\nData setelah dilakukan quick sort:\n"; for(i=0;i<n;i++) cout<<a[i]<<" , "; return 0; } void quick_sort(int a[],int l,int u) {                         int j; if(l<u) { j=partition(a,l,u); quick_sort(a,l,j-1); quick_sort(a,j+1,u); } } int partition(int a[],int l,int u) { int v,i,j,temp; v=a[l]; i=l; j=u+1; do { do i++; while(a[i]<v&&i<=u); do j--; while(v<a[j]); if(i<j) { temp=a[i]; a[i]=a[j]; a[j]=temp; } }while(i<j); a[l]=a[j]; a[j]=v; return(j); }

Hasil running

 

BUBLE SHOT

1. Pengertian Buble Shot

Buble sort adalah teknik mengurutkan data dari yang dilakukan secara berangsur-angsur metode ini seperti gelembung yang keluar dari gelas soda.  Bubble sort mengurutkan data dengan cara membandingkan elemen sekarang dengan elemen berikutnya. 

·         jika elemen sekarang  lebih besar dari elemen berikutnya maka elemen tersebut ditukar (untuk pengurutan ascending) 

·         jika elemen sekarang lebih kecil daripada elemen berikutnya, maka kedua elemen  tersebut ditukar (untuk pengurutan descending). 

algoritma ini seolanh olah menggeser satu per satu elemen dari kenan ke kiri atau kiri ke kanan. tergantung jenis pengurutannya. Ketika suatu proses telah selesai, maka bubble sort akan mengalami proses, demikian seterusnya. Bubble sort berhenti jika seluruh array telah diperiksa dan tidak ada pertukaran lagi yang bisa dilakukan,serta tercapai pengurutan yang telah diinginkan.

2. contoh dari bublle shot

Langkah Bubble Sort secara ascending

5, 12, 3, 19, 1, 47

Iterasi 1:

5, 12, 3, 19, 1, 47 --> Tidak ada pertukaran. (5 < 12 == true)

5, 3, 12, 19, 1, 47 --> Ada pertukaran. (12 < 3 == false)

5, 3, 12, 19, 1, 47 --> Tidak ada pertukaran. (12 < 19 == true)

5, 3, 12, 1, 19, 47 --> Ada pertukaran. (19 < 1 == false)

5, 3, 12, 1, 19, 47 --> Tidak ada pertukaran. (19 < 47 == true)

Iterasi 2:

3, 5, 12, 1, 19, 47 --> Ada petukaran. (5 < 3 == false)

3, 5, 12, 1, 19, 47 --> Tidak ada pertukaran. (5 < 12 == true)

3, 5, 1, 12, 19, 47 --> Ada pertukaran. (12 < 1 == false)

3, 5, 1, 12, 19, 47 --> Tidak ada pertukaran. (12 < 19 == true)

3, 5, 1, 12, 19, 47 --> Tidak ada pertukaran. (19 < 47 == true)

Iterasi 3:

3, 5, 1, 12, 19, 47 --> Tidak ada pertukaran. (3 < 5 == true)

3, 1, 5, 12, 19, 47 --> Ada pertukaran. (5 < 1 == false)

3, 1, 5, 12, 19, 47 --> Tidak ada pertukaran. (5 < 12 == true)

3, 1, 5, 12, 19, 47 --> Tidak ada pertukaran. (12 < 19 == true)

3, 1, 5, 12, 19, 47 --> Tidak ada pertukaran. (19 < 47 == true)

Iterasi 4:

1, 3, 5, 12, 19, 47 --> Ada pertukaran. (3 < 1 == false)

1, 3, 5, 12, 19, 47 --> Tidak ada pertukaran. (3 < 5 == true)

1, 3, 5, 12, 19, 47 --> Tidak ada pertukaran. (5 < 12 == true)

1, 3, 5, 12, 19, 47 --> Tidak ada pertukaran. (12 < 19 == true)

1, 3, 5, 12, 19, 47 --> Tidak ada pertukaran. (19 < 47 == true)

Iterasi 5:

1, 3, 5, 12, 19, 47 --> Tidak ada pertukaran. (1 < 3 == true)

1, 3, 5, 12, 19, 47 --> Tidak ada pertukaran. (3 < 5 == true)

1, 3, 5, 12, 19, 47 --> Tidak ada pertukaran. (5 < 12 == true)

1, 3, 5, 12, 19, 47 --> Tidak ada pertukaran. (12 < 19 == true)

1, 3, 5, 12, 19, 47 --> Tidak ada pertukaran. (19 < 47 == true)

Iterasi 6:

1, 3, 5, 12, 19, 47 --> Tidak ada pertukaran. (1 < 3 == true)

1, 3, 5, 12, 19, 47 --> Tidak ada pertukaran. (3 < 5 == true)

1, 3, 5, 12, 19, 47 --> Tidak ada pertukaran. (5 < 12 == true)

1, 3, 5, 12, 19, 47 --> Tidak ada pertukaran. (12 < 19 == true)

1, 3, 5, 12, 19, 47 --> Tidak ada pertukaran. (19 < 47 == true)

Jadi, hasil akhir deretan bilangan diatas setelah di Bubble Sort secara Ascending ialah

1, 3, 5, 12, 19, 47

Langkah Bubble Sort Secara Descending

 5, 12, 3, 19, 1, 47

Iterasi 1:

12, 5, 3, 19, 1, 47 --> Ada pertukaran. (5 > 12 == false)

12, 5, 3, 19, 1, 47 --> Tidak ada pertukaran. (5 > 3 == true)

12, 5, 19, 3, 1, 47 --> Ada pertukaran. (3 > 19 == false)

12, 5, 19, 3, 1, 47 --> Tidak ada pertukaran. (3 > 1 == true)

12, 5, 19, 3, 47, 1 --> Ada pertukaran. (1 > 47 == false)

Iterasi 2:

12, 5, 19, 3, 47, 1 --> Tidak ada pertukaran. (12 > 5 == true)

12, 19, 5, 3, 47, 1 --> Ada pertukaran. (5 > 19 == false)

12, 19, 5, 3, 47, 1 --> Tidak ada pertukaran. (5 > 3 == true)

12, 19, 5, 47, 3, 1 --> Ada pertukaran. (3 > 47 == false)

12, 19, 5, 47, 3, 1 --> Tidak ada pertukaran. (3 > 1 == true)

Iterasi 3:

19, 12, 5, 47, 3, 1 --> Ada pertukaran. (12 > 19 == false)

19, 12, 5, 47, 3, 1 --> Tidak ada pertukaran. (12 > 5 == true)

19, 12, 47, 5, 3, 1 --> Ada pertukaran. (5 > 47 == false)

19, 12, 47, 5, 3, 1 --> Tidak ada pertukaran. (5 > 3 == true)

19, 12, 47, 5, 3, 1 --> Tidak ada pertukaran. (3 > 1 == true)

Iterasi 4:

19, 12, 47, 5, 3, 1 --> Tidak ada pertukaran. (19 > 12 == true)

19, 47, 12, 5, 3, 1 --> Ada pertukaran. (12 > 47 == false)

19, 47, 12, 5, 3, 1 --> Tidak ada pertukaran. (12 > 5 == true)

19, 47, 12, 5, 3, 1 --> Tidak ada pertukaran. (5 > 3 == true)

19, 47, 12, 5, 3, 1 --> Tidak ada pertukaran. (3 > 1 == true)

Iterasi 5:

47, 19, 12, 5, 3, 1 --> Ada pertukaran. (19 > 47 == false)

47, 19, 12, 5, 3, 1 --> Tidak ada pertukaran. (19 > 12 == true)

47, 19, 12, 5, 3, 1 --> Tidak ada pertukaran. (12 > 5 ==true)

47, 19, 12, 5, 3, 1 --> Tidak ada pertukaran. (5 > 3 == true)

47, 19, 12, 5, 3, 1 --> Tidak ada pertukaran. (3 > 1 == true)

Iterasi 6:

47, 19, 12, 5, 3, 1 --> Tidak ada pertukaran. (47 > 19 == true)

47, 19, 12, 5, 3, 1 --> Tidak ada pertukaran. (19 > 12 == true)

47, 19, 12, 5, 3, 1 --> Tidak ada pertukaran. (12 > 5 == true)

47, 19, 12, 5, 3, 1 --> Tidak ada pertukaran. (5 > 3 == true)

47, 19, 12, 5, 3, 1 --> Tidak ada pertukaran. (3 > 1 == true)

Jadi, hasil akhir deretan bilangan diatas setelah di Bubble Sort secara Descending ialah

47, 19, 12, 5, 3, 1

3. contoh listing progam

#include<iostream> using namespace std; int main(){ int i,a[4],temp,j; cout<<"masukan 4 jumlah array: \n"; for(i=0;i<=3;i++){ cin>>a[i]; } cout<<"\nData sebelum sorting buble sort: "; for(j=0;j<4;j++){ cout<<a[j]; } for(i=0;i<=4;i++){ for(j=0;j<=4-i;j++){ if(a[j]>a[j+1]){ temp=a[j]; a[j]=a[j+1]; a[j+1]=temp; } } } cout<<"\nData Setelah sorting buble sort "; for(j=0;j<4;j++) { cout<<a[j]; } }

Hasil running

 

DAFTAR PUSTAKA

lhttp://onophp.blogspot.com/2018/11/quick-sort-pengertian-agoritma-dan.html https://onophp.blogspot.com/2018/10/algoritma-buble-sort-dan-sourcode.html