E
Exekute
Someone help! my quicksort isn't very quick. It's only like 25%
faster than selection sort (or insertion sort). This is also like 100
times slower than my merge sort. If it's supposed to be that slow
then someone tell me. Otherwise someone that's good at algorithm
analysis help me out. I know it's hard to trus people, but it's not a
noob mistake somewhere else in the program (teacher wrote everything
else). I'll give my quicksort and partition code. Pre condition:
array of ints, it's first element is given by l, and it's last is
given by r. Post condition: The array is sorted.
void quick_sort(int *A,int l,int r)
{
int middle;
if ( l < r )
{
middle = partition(A, l, r);
quick_sort(A, l, middle);
quick_sort(A, middle+1, r);
}
}
/-----------------------------------PARTITION
int partition(int *A, int l, int r)
{
int p = A[l];
int tmp;
int i = l;
int j = r + 1;
for (int x = 0; x == 0; x = 0)
{
do
{
i++;
} while ( p > A );
do
{
j--;
} while ( p < A[j] );
if (i < j)
{
tmp = A[j];
A[j] = A;
A = tmp;
}
else
{
return j;
}
}
}
faster than selection sort (or insertion sort). This is also like 100
times slower than my merge sort. If it's supposed to be that slow
then someone tell me. Otherwise someone that's good at algorithm
analysis help me out. I know it's hard to trus people, but it's not a
noob mistake somewhere else in the program (teacher wrote everything
else). I'll give my quicksort and partition code. Pre condition:
array of ints, it's first element is given by l, and it's last is
given by r. Post condition: The array is sorted.
void quick_sort(int *A,int l,int r)
{
int middle;
if ( l < r )
{
middle = partition(A, l, r);
quick_sort(A, l, middle);
quick_sort(A, middle+1, r);
}
}
/-----------------------------------PARTITION
int partition(int *A, int l, int r)
{
int p = A[l];
int tmp;
int i = l;
int j = r + 1;
for (int x = 0; x == 0; x = 0)
{
do
{
i++;
} while ( p > A );
do
{
j--;
} while ( p < A[j] );
if (i < j)
{
tmp = A[j];
A[j] = A;
A = tmp;
}
else
{
return j;
}
}
}