IMPROVING QUICKSORT(HOURS 14)

Quicksort emang dapat mengurutkan data dengan cepat namun quicksort akan kurang efisien jika dihadapkan pada data yang ter-invers(terbalik) ataupun dengan data yang jumlahnya sedikit, karena itu diperlukan peningkatan kinerja dari quicksort agar dapat menangani masalah tersebut serta mempercepat kinerja quicksort.

Data terbalik

Masalah pada data terbalik adalah pada pivot. Pada bab sebelumnya pivot yang dipilih adalah indeks terbesar dari array data, masalah ini dapat ditangani dengan memilih pivot pada median(tengah) data. Sehingga diperoleh 2 bagian yang lebih mudah dalam pembagian selanjutnya.

Median-of-Three Partitioning

• Pilih nilai indeks awal, tengah, dan akhir
  
• Urutkan ketiga nilai tersebut
  
• Pilih median dari 3 nilai tersebut sebagai pivot
  
• Lakukan quicksort

Implementasinya dalam c++

//quickSort2.cpp

//demonstrates quick sort with median-of-three partitioning

#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

{

int size = right-left+1;

if(size <= 3) //manual sort if smallmanualSort(left, right);

else //quicksort if large

{

double median = medianOf3(left, right);

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

recQuickSort(left, partition-1);

recQuickSort(partition+1, right);

}

} //end recQuickSort()

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

double medianOf3(int left, int right)

{

int center = (left+right)/2;

//order left & center

if( theVect[left] > theVect[center] )

swap(left, center);

//order left & right

if( theVect[left] > theVect[right] )

swap(left, right);

//order center & right

if( theVect[center] > theVect[right] )

swap(center, right);

swap(center, right-1); //put pivot on right

return theVect[right-1]; //return median value

} //end medianOf3()

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

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(

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

//partition a range

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

{

int leftMark = left; //right of first elem

int rightMark = right - 1; //left of pivot

while(true)

{

while( theVect[++leftMark] < pivot ) //find bigger

; // (nop)

while( theVect[--rightMark] > pivot ) //find smaller

; // (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-1); //restore pivot

return leftMark; //return pivot location

} //end partitionIt()

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

void manualSort(int left, int right)

{

int size = right-left+1;

if(size <= 1)

return; //no sort necessary

if(size == 2)

if( theVect[left] > theVect[right] )

swap(left, right);

return;

}

else //size==3, so 3-sort left, center (right-1) & right

{

if( theVect[left] > theVect[right-1] )

swap(left, right-1); //left, center

if( theVect[left] > theVect[right] )

swap(left, right); //left, right

if( theVect[right-1] > theVect[right] )

swap(right-1, right); //center, right

}

} //end manualSort()

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

}; //end class ArrayIns

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

int main()

{

time_t aTime;

int maxSize = 16; //array size

ArrayIns arr(maxSize); //create the 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()

Handling Small Partitions

Algoritma quicksort standar tidak dapat bekerja mengurutkan bagian dengan 3 data atau lebih sedikit dari itu. Dalam hal ini jumlah tersebut disebut dengan cutoff point

Menggunakan insertion sort untuk bagian data yang kecil

Insertion sort dapat dipakai untuk menangani bagian data yang kecil dimana insertion sort akan dipakai saat bertemu dengan cutoff point.

• Insertion sort dilakukan sebagai bagian dari quicksort setelah mencapai data sedikit(cutoff point)
  
• Metode:
  

1. Quicksort dilanjutkan insertion sort untuk data sedikit
   
2. Quicksort kemudian sort dihentikan untuk data sedikit( mencapai cutoff point). Lalu dilakukan insertion sort secara keseluruhan
   

Listing untuk mengangani data kecil

//quickSort3.cpp

//demonstrates quick sort; uses insertion sort for cleanup

#include <iostream>

#include <vector>

#include <cstdlib> //for rand()

#include <ctime> //for rand()

using namespace std;

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

class ArrayIns

{

private:

vector<double> theArray; //array theArray

int nElems; //number of data items

public:

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

ArrayIns(int max) //constructor

{

theArray.reserve(max); //change size of vector

nElems = 0; //no items yet

}

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

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

{

theArray[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 << theArray[j] << " "; //display it

cout << endl;

}

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

void quickSort() //sort the array

{

recQuickSort(0, nElems-1);

// insertionSort(0, nElems-1); //(another option)

}

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

void recQuickSort(int left, int right) //recursive quicksort

{

int size = right-left+1;

if(size < 10) //insertion sort if small

insertionSort(left, right);

else //quicksort if large

{

double median = medianOf3(left, right);

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

recQuickSort(left, partition-1);

recQuickSort(partition+1, right);

}

} //end recQuickSort()

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

double medianOf3(int left, int right)

{

int center = (left+right)/2;

//order left & center

if( theArray[left] > theArray[center] )

swap(left, center);

//order left & right

if( theArray[left] > theArray[right] )

swap(left, right);

//order center & right

if( theArray[center] > theArray[right] )

swap(center, right);

swap(center, right-1); //put pivot on right

return theArray[right-1]; //return median value

} //end medianOf3()

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

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

{

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

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

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

} //end swap(

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

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

{

int leftMark = left; //right of first elem

int rightMark = right - 1; //left of pivot

while(true)

{

while( theArray[++leftMark] < pivot ) //find bigger

; // (nop)

while( theArray[--rightMark] > pivot ) //find smaller; // (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-1); //restore pivot

return leftMark; //return pivot location

} //end partitionIt()

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

void insertionSort(int left, int right) //insertion sort

{

int in, out;

//sorted on left of out

for(out=left+1; out<=right; out++)

{

double temp = theArray[out]; //remove marked item

in = out; //start shifts at out

//until one is smaller,

while(in>left && theArray[in-1] >= temp)

{

theArray[in] = theArray[in-1]; //shift item to right

--in; //go left one position

}

theArray[in] = temp; //insert marked item

} //end for

} //end insertionSort()

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

}; //end class ArrayIns

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

int main()

{

int maxSize = 16; //array size

ArrayIns arr(maxSize); //create array

time_t aTime; //seed random numbers

srand(static_cast<unsigned>( time(&aTime) ));

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() 


Sumber : Kuliah Logika dan Pemrograman Sistem II