Saya sedang melakukan proyek untuk membandingkan algoritma Bubblesort dan Quicksort. Semuanya berfungsi dengan baik sampai saya ingin mengurutkan data yang sudah diurutkan dengan metode Quicksort. Itu mogok pada array besar (50k, 100k).
Dalam kasus saya, pertama-tama saya mengurutkan data dalam urutan menurun dan kemudian saya mencoba mengurutkan dalam urutan menaik dan kemudian macet.
read(); // just creates an array with random integers
quickSortDSC(0, length - 1); //Here is the problem! (works if commented)
t1 = clock();
quickSortASC(0, length - 1);
t2 = clock();
cout << "Quick Sort\t: " << (t2 - t1)/CLK_TCK << " sec\n";
Kode lengkap:
#include <iostream>
#include <fstream>
#include <cstdlib>
#include <ctime>
using namespace std;
long length = 1000;
const long max_length = 100000;
int list[max_length];
void read()
{
ifstream fin("random.dat", ios::binary);
for (long i = 0; i < length; i++)
{
fin.read((char*)&list[i], sizeof(int));
}
fin.close();
}
void bubbleSort()
{
int temp;
for(long i = 0; i < length; i++)
{
for(long j = 0; j < length-i-1; j++)
{
if (list[j] > list[j+1])
{
temp = list[j];
list[j] = list[j+1];
list[j+1] = temp;
}
}
}
}
long partitionASC(long left, long right)
{
int pivot_element = list[left];
int lb = left, ub = right;
int temp;
while (left < right)
{
while(list[left] <= pivot_element)
left++;
while(list[right] > pivot_element)
right--;
if (left < right)
{
temp = list[left];
list[left] = list[right];
list[right] = temp;
}
}
list[lb] = list[right];
list[right] = pivot_element;
return right;
}
long partitionDSC(long left, long right)
{
int pivot_element = list[left];
int lb = left, ub = right;
int temp;
while (left < right)
{
while(list[left] >= pivot_element)
left++;
while(list[right] < pivot_element)
right--;
if (left < right)
{
temp = list[left];
list[left] = list[right];
list[right] = temp;
}
}
list[lb] = list[right];
list[right] = pivot_element;
return right;
}
//ascending order
void quickSortASC(long left, long right)
{
long pivot;
if (left < right)
{
pivot = partitionASC(left, right);
quickSortASC(left, pivot-1);
quickSortASC(pivot+1, right);
}
}
//descending order
void quickSortDSC(long left, long right)
{
long pivot;
if (left < right)
{
pivot = partitionDSC(left, right);
quickSortDSC(left, pivot-1);
quickSortDSC(pivot+1, right);
}
}
int main()
{
double t1, t2;
for (length = 1000; length <= max_length; )
{
cout << "\nLength\t: " << length << '\n';
read();
t1 = clock();
bubbleSort();
t2 = clock();
cout << "Bubble Sort\t: " << (t2 - t1)/CLK_TCK << " sec\n";
read();
quickSortDSC(0, length - 1); //Here is the problem!
t1 = clock();
quickSortASC(0, length - 1);
t2 = clock();
cout << "Quick Sort\t: " << (t2 - t1)/CLK_TCK << " sec\n";
if(length == max_length)
break;
switch (length)
{
case 1000 :
length = 10000;
break;
case 10000 :
length = 50000;
break;
case 50000 :
length = 100000;
break;
}
}
return 0;
}