for(;
Quick Sort
quote:Original post by omegasyphon
what does this do
for(;
It is an infinite loop. It is the same as
while(1){ //do stuff here}
Magmai - if you always use the first element as the pivot, then yes, quicksort -> O(n2). That is why we don''t use the first element as the pivot 
void quicksort(int *sort_array, int size) {
quicksort2(sort_array, 0, size - 1); // "almost" sort the array.
insertion_sort(sort_array, size);
}
void quicksort2(int *sort_array, int lo, int hi) {
if((hi - lo) <= 4) return; // the insertion sort copes with this.
int med = (lo + hi) >> 1;
if(sort_array[lo] > sort_array[hi]) swap(lo, hi);
if(sort_array[lo] > sort_array[med]) swap(lo, med);
if(sort_array[med] > sort_array[hi]) swap(med, hi);
// now use "med" as the pivot.
...there are other ways to do it, but this is a start.
void quicksort(int *sort_array, int size) {
quicksort2(sort_array, 0, size - 1); // "almost" sort the array.
insertion_sort(sort_array, size);
}
void quicksort2(int *sort_array, int lo, int hi) {
if((hi - lo) <= 4) return; // the insertion sort copes with this.
int med = (lo + hi) >> 1;
if(sort_array[lo] > sort_array[hi]) swap(lo, hi);
if(sort_array[lo] > sort_array[med]) swap(lo, med);
if(sort_array[med] > sort_array[hi]) swap(med, hi);
// now use "med" as the pivot.
...there are other ways to do it, but this is a start.
If the data is nearly sorted, then using
Insertion Sort is close to O(n).
Steven Borkman
Home Page: http://www.acsu.buffalo.edu
Video Game Page: http://www-student.cse.buffalo.edu/~borkman/projects/game/index.php
Insertion Sort is close to O(n).
Steven Borkman
Home Page: http://www.acsu.buffalo.edu
Video Game Page: http://www-student.cse.buffalo.edu/~borkman/projects/game/index.php
for(; {} and while(1) {} aren''t the same. Most compilers will optimize them to be the same, but you shouldn''t always count on your compiler to do something. The difference is the latter loop still has to evaluate "1" before looping. The former loop will result in just a goto statement. Most compilers will optimize them to equivalent code, but its good to know the difference.
{} and while(1) {} aren''t the same. Most compilers will optimize them to be the same, but you shouldn''t always count on your compiler to do something. The difference is the latter loop still has to evaluate "1" before looping. The former loop will result in just a goto statement. Most compilers will optimize them to equivalent code, but its good to know the difference.
quote:Original post by Anonymous Poster
for(;
Regardless of how the compiler compiles the code, isn''t their behaviour identical (i.e. an infinite loop)? isn''t that what really matters?
From a high level point of view the behavior is similar, but technically different. There is a difference between having to evaluate an expression that is always true and then looping as opposed to just having a goto instruction in your assembly code.
while(1) looks nicer
---------------
I finally got it all together...
...and then forgot where I put it.
---------------
I finally got it all together...
...and then forgot where I put it.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
