Struktur Data – Implementasi Quick Sort Menggunakan C/C++


Bahan Ajar/modul matakuliah Struktur Data ini membahas konsep tentang salah satu metode pengurutan  Quick Sort. Materi membahas mulai dari pengertian Quick Sort, pseudocode Quick Sort, analisis algoritma Quick Sort dan dDiakhir sesi dapat dilihat implemetasi Quick Sort Menggunakan C/C++.

Pengertian Quick Sort

Algoritma sortir yang efisien yang ditulis oleh C.A.R. Hoare pada 1962. Dasar strateginya adalah “memecah dan menguasai”. Quicksort dimulai dengan menscan daftar yang disortir untuk nilai median. Nilai ini, yang disebut tumpuan (pivot), kemudian dipindahkan ke satu sisi pada daftar dan butir-butir yang nilainya lebih besar dari tumpuan di pindahkan ke sisi lain.

Algoritma Quick Sort

Divide

Memilah rangkaian data menjadi dua sub-rangkaian A[p…q-1] dan A[q+1…r]  dimana setiap elemen A[p…q-1] adalah kurang dari atau sama dengan A[q]  dan  setiap   elemen  pada A[q+1…r]   adalah  lebih  besar   atau  sama  dengan elemen  pada  A[q].  A[q]   disebut   sebagai   elemen   pivot.   Perhitungan  pada elemen q merupakan salah satu bagian dari prosedur pemisahan.

Conquer

Mengurutkan elemen pada sub-rangkaian secara rekursif  Pada algoritma quick sort, langkah ”kombinasi” tidak di lakukan karena telah terjadi  pengurutan elemen – elemen pada sub array.

Pseudocode Quick Sort

Pseudocode Quicksort

Contoh Quick Sort

Analisis Algoritma QuickSort

Setiap elemen yang akan disort selalu diperlakukan secara sama di sini, diambil salah satu elemen, dibagi
menjadi  3 list, lalu ketiga list tersebut disort dan digabung kembali. Contoh kode di atas menggunakan
3 buah list, yaitu yang lebih besar, sama dan lebih  kecil nilainya dari pivot. Untuk membuat lebih efisien,
bisa digunakan 2 buah list dengan mengeliminasi yang  nilainya sama (bisa digabung ke salah satu dari 2 list
yang lain).  Kasus terburuk dari algoritma ini adalah saat dibagi menjadi 2 list, satu list hanya terdiri dari 1 elemen dan yang lain terdiri dari n-2 elemen. Untuk kasus terburuk dan kasus rata-rata, algoritma ini memiliki kompleksitas sebesar O(n log n). Jumlah rata-rata perbandingan untuk quick sort berdasarkan permutasinya dengan asumsi bahwa nilai pivot diambil secara random adalah :

Lalu bagaimana cara menentukan pivot sendiri? Kasus terbaik yang diharapkan diilustrasikan sebagai berikut:

Bagi sebuah list menjadi 4 buah. Lalu pilih 2 buah list sedemikian rupa sehingga setiap elemennya lebih besar dari 25 % elemen terkecil dan lebih kecil dari 25% elemen  terbesar. Bila nilai pivot yang dipilih secara konstan terambil dari nilai ini maka hanya diperlukan pembagian list sebanyak 2log2n kali.Biladibandingkan dengan merge sort, quick sort memiliki keuntungan di kompleksitas waktu sebesar Θ(log  n), dibanding dengan merge sort sebesar  Θ(n). namun quick sort tidak mampu membandingkan  linked list sebaik merge sort, karena ada kemungkinan pemilihan pivot yang buruk. Selain itu pada   linked list merge sort memerlukan ruang yang lebih sedikit. Berdasarkan analisis tersebut quick sort termasuk algoritma sorting yang cukup baik, namun kita pun harus bisa memilih nilai pivot yang baik agar penggunaannya bisa optmal.

Implementasi Quic Sort Menggunakan C/C++

Partition(A, p, r)
x = A[p]; //pivot=elemen posisi pertama
i = p ; //inisialisasi
j = r ;
repeat
  while(A[j] > x)
    j--;
    while(A[i] < x)
       i++;
   if (i < j){
     Swap(A, i, j);
     j--;
     i++
    }
  else
    return j;
until i >= j
About these ads

15 gagasan untuk “Struktur Data – Implementasi Quick Sort Menggunakan C/C++

  1. Ping-balik: STRUKTUR DATA « Armasyarifudin's Blog

  2. posting terus brow yang banyak,,postinganmu merupakan wujud mencerdaskan umat dan kehidupan bangsa secara tidak langsug,,amal saudara akan senantiasa mengalir selama ilmu ini selama banyak orang yang memanfaatkan ilmu anda dengan benar,,,,semangat brow….the best bgt

  3. Ping-balik: MAKALAH STRUKTUR DATA QUICK SORT | DjongPra

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Logout / Ubah )

Twitter picture

You are commenting using your Twitter account. Logout / Ubah )

Facebook photo

You are commenting using your Facebook account. Logout / Ubah )

Google+ photo

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s