1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68
|
int median_partition(int* arr, int start, int end)
{
int x=arr[start],y=arr[(end-start)/2+start],z=arr[end-1],i=start-1,j=end;
if (y>x && y<z || y>z && y<x )
x=y;
else if (z>x && z<y || z>y && z<x )
x=z;
while (1) {
do {j--;count++;} while (arr[j] > x);
do {i++;count++;} while (arr[i] < x);
if (i < j) swap(&arr[i],&arr[j]);
else return j+1;
}
}
int main()
{
ifstream fin1("test_1.txt", ios::binary);
for (long i = 0; i < 5; i++)
{
fin1.read((char*)&test_1[i], sizeof(int));
}
ifstream fin2("test_2.txt", ios::binary);
for (long j = 0; j < 18; j++)
{
fin2.read((char*)&test_2[j], sizeof(int));
}
ifstream fin3("InputArray.txt", ios::binary);
for (long k = 0; k < 100000; k++)
{
fin3.read((char*)&inputarray[k], sizeof(int));
}
cout << "First number in array is the pivot.";
cout << endl << "test_1.txt: ";
first_element_quicksort(test_1, 0,5);
cout << endl << "test_2.txt: ";
first_element_quicksort(test_2, 0,18);
cout << endl << "InputArray.txt: ";
first_element_quicksort(inputarray, 0,100000);
cout << endl << endl;
cout << "Median of three random numbers in array is pivot.";
cout << endl << "test_1.txt: ";
median_quicksort(test_1, 0,5);
cout << endl << "test_2.txt: ";
median_quicksort(test_2, 0,18);
cout << endl << "InputArray.txt: ";
median_quicksort(inputarray, 0,100000);
cout << endl << endl;
cout << "Random number in array is pivot.";
cout << endl << "test_1.txt: ";
random_quick_sort(test_1, 0,5);
cout << endl << "test_2.txt: ";
random_quick_sort(test_2, 0,18);
cout << endl << "InputArray.txt: ";
random_quick_sort(inputarray, 0,100000);
cout << endl << endl;
fin1.close();
fin2.colse();
fin3.close();
return 0;
}
|