I'm looking to review as many sort tutorials I can find. I'm familar with a few beginner level sorts. Please post sites you have found on sorts. Thank you.
Printable View
I'm looking to review as many sort tutorials I can find. I'm familar with a few beginner level sorts. Please post sites you have found on sorts. Thank you.
http://en.wikipedia.org/wiki/Sort_algorithm
and my favorite :: BogoSort!!! :D :D :D
question on the sorts.
I'm looking to show the efficiency difference in the different sorts.
I have taken the algorithms and placed them in my own Java program.
http://thedigitalevolution.com/program4.txt
I'm trying to place a counter in the different sorts to prove one is more efficient then the other. My results have been unexpected. My teacher said to place the counters in the locations were the comparisons are made. I did this, but it keeps giving me unexpected results. For instance lets look at the quick sort. The sorts work. So the code was transposed correctly.
(1)Are the incrementations placed in the best logical location to track efficiency?
This code is primarily non-language specific
I thought the best location would be the swap location, and not the comparisons.Code:void QuickSort(int a[], int lo0, int hi0)
{
int lo = lo0;
int hi = hi0;
if (lo >= hi)
{
return;
}
else if( lo == hi - 1 )
{
if (a[lo] > a[hi])
{
int T = a[lo];
a[lo] = a[hi]; //I believe this should be 1 of 2 spots that increment
a[hi] = T;
comparison++;
}
return;
}
int pivot = a[(lo + hi) / 2];
a[(lo + hi) / 2] = a[hi];
a[hi] = pivot;
while( lo < hi )
{
while (a[lo] <= pivot && lo < hi)
{ //i do not believe this to be a valid increment
comparison++;
lo++;
}
while (pivot <= a[hi] && lo < hi )
{ // i do not believe this is a valid increment
comparison++;
hi--;
}
if ( lo < hi )
{
int T = a[lo];
a[lo] = a[hi]; //this is 2 of 2 spots i feel should be incremented
a[hi] = T;
comparison++;
}
}
a[hi0] = a[hi];
a[hi] = pivot;
QuickSort(a, lo0, lo-1);
QuickSort(a, hi+1, hi0);
}
The locations highlighted in red are compared shortly prior to the incrementation noted by green. The quick sort with using the comparisons type of tracking has in some cases shown me more comparisions then the other sorts. From the prior posted website I read that the quick sort is the fastest, therefore should always produce the smallest amount of comparisons? Is this a valid and logical thought?
>I thought the best location would be the swap location, and not the comparisons.
It depends on the metric you're testing. Both comparisons and swaps are important test measures for a sorting algorithm, and an inefficiency with one of them can result in using a quadratic sort instead of an nlogn sort because (for example) the nlogn sort performed too many swaps or too many comparisons and the items being sorted are compared very slowly or they are HUGE.
Prelude,
So you feel it is better to test for comparisons and swaps for a judge of efficiency.
This sounds very logical to me.
So given the code above would you say that if I was to check for comparisons only they are in the correct spots? the concern I have is that my attempt to place the incrementation in the actual test area has hailed. This makes the possibility that a false result on a test will not be regestered as a comparison. any suggestions to make sure the reading are as accurate as possible. on the if statements, i could place an else, but on the other loops i.e. do while, while, etc. if the comparison is false, it will not execute the loop, but will be an unrecorded comparisons.
sorry about not having executable code for you to run, my work has issues with uploading files from their network. but if anyone has time, they could cut and paste the prior linked code.