QUICKSORT (HOURS13)

Pada bab sebelumnya telah dibahas mergesort dimana dapat mengurutkan dengan cepat namun memerlukan ruang lebih banyak untuk melakukan pengkopian array-array yang akan diurutkan. Sehingga memerlukan banyak memori. Sementara quicksort sama cepat dengan mergesort hanya keunggulannya memerlukan sedikit memori.

Inti dari quicksort

• data dibagi 2 bagian dengan 1 titik bagi
  
• mengulangi pembagian pada masing masing bagian
  

Proses mengurutkan(mergesort)

• bagi data menjadi 2 dengan jumlah sama
  
• urutkan masing-masing bagian
  
• lakukan penggabungan(merge)
  

Partition

quicksort bekerja dengan membagi data menjadi bagian-bagian(partition) dan proses ini dilakukan berulang-ulang pada masing-masing bagian. Untuk melakukan partition dimulai dengan memilih titik/nilai acuan(pivot) untuk kemudian membandingkan data dengan pivot tersebut sehingga diperoleh 2 bagian data yaitu data yang lebih besar dari pivot dan data yang lebih kecil dari pivot.

Setelah didapat 2 bagian seperti pada gambar diatas maka masing-masing bagian akan dibagi lagi dengan menentukan pivot pada masing masing bagian sehingga data akan terurut.

Proses program dasar quicksort

1. tentukan pivot sebagai index bagain terbesar
   
2. Ki(data bagian terkiri) digeser ke kanan sampai ki > pivot
   
3. Ka(data bagian terkanan) digeser ke kiri sampai ka < pivot
   
4. Jika ka > ki maka nilai di ka dan ki ditukar
   

Proses jalannya quicksort

1. pivot array 70, data dibandingkan
   
2. diambil bagian kiri pivot 50, data dibandingkan
   
3. diambil pivot 40, data dibandingkan
   
4. diambil pivot 20, data dibandingkan
   
5. diambil bagian kanan
   
6. diambil pivot 110, data dibandingkan
   
7. diambil pivot 100, data dibandingkan
   
8. diambil pivot 80, data dibandingkan
   
9. didapatkan array yang terurut
   

listing quicksort

//quickSort1.cpp

//demonstrates simple version of quick sort

#include <iostream>

#include<vector>

#include<cstdlib> //for random numbers

#include<ctime> //for random numbers

using namespace std;

////////////////////////////////////////////////////////////////

class ArrayIns

{

private:

vector<double>(theVect); //vector of doubles

int nElems; //number of data items

public:

//--------------------------------------------------------------

ArrayIns(int max) : nElems(0) //constructor

{

theVect.resize(max); //size the vector

}

//--------------------------------------------------------------

void insert(double value) //put element into array

{

theVect[nElems] = value; //insert it

nElems++; //increment size

}

//--------------------------------------------------------------

void display() //displays array contents

{

cout << "A=";

for(int j=0; j<nElems; j++) //for each element,

cout << theVect[j] << " "; //display it

cout << endl;

}

//--------------------------------------------------------------

void quickSort() //sort array

{

recQuickSort(0, nElems-1); //call recursive sort

}

//-------------------------------------------------------------- void

recQuickSort(int left, int right) //recursive sort

{

if(right-left <= 0) //if size <= 1, return; // already sorted

else //size is 2 or larger

{

double pivot = theVect[right]; //rightmost item

//partition range

int partition = partitionIt(left, right, pivot);

recQuickSort(left, partition-1); //sort left side

recQuickSort(partition+1, right); //sort right side

}

} //end recQuickSort()

//--------------------------------------------------------------

int partitionIt(int left, int right, double pivot)

{

int leftMark = left-1; //left (after ++)

int rightMark = right; //right-1 (after --)

while(true)

{ //find bigger item

while( theVect[++leftMark] < pivot )

; // (nop)

//find smaller item

while(rightMark > 0 && theVect[--rightMark] > pivot)

; // (nop)

if(leftMark >= rightMark) //if pointers cross,

break; // partition done

else //not crossed, so

swap(leftMark, rightMark); // swap elements

} //end while(true)

swap(leftMark, right); //restore pivot

return leftMark; //return pivot location

} //end partitionIt()

//--------------------------------------------------------------

void swap(int dex1, int dex2) //swap two elements

{

double temp = theVect[dex1]; //A into temp

theVect[dex1] = theVect[dex2]; //B into A

theVect[dex2] = temp; //temp into B

} //end swap(

//--------------------------------------------------------------

}; //end class ArrayIns

////////////////////////////////////////////////////////////////

int main()

{

time_t aTime;

int maxSize = 16; //array size

ArrayIns arr(maxSize); //create array

srand( static_cast<unsigned>(time(&aTime)) ); //seed randoms

for(int j=0; j<maxSize; j++) //fill array with{ //random numbers

double n = rand() % 99;

arr.insert(n);

}

arr.display(); //display items

arr.quickSort(); //quicksort them

arr.display(); //display them again

return 0;

} //end main()

Output

A=69 0 70 6 38 38 24 56 44 26 73 77 30 45 97 65

A=0 6 24 26 30 38 38 44 45 56 65 69 70 73 77 97


 
sumber : Kuliah Logika dan Pemrograman Sistem II