Ad:

C Discussion Thread
Unsolved
Views: 11348

Page 1
2
Next

You are currently viewing page 1 of this multi-page discussion thread

Oct 15th, 2004

Quicksort/Insertion sort Hyrbid?

Expand Post »

Recently we have been asked to create a hybrid sort based upon quicksorting down to a certain point and insertion sorting from then on. We are to calculate the efficency based upon previous tests. I had very little problems implementing a quicksort algorithm, but for the life of me, I can't get anything to work on the hybrid version. Can anyone help, provide tips or pointers?

Jpowers22

Reputation Points: 12

Solved Threads: 0

Newbie Poster

Offline

5 posts
since Oct 2004

Permalink

Oct 15th, 2004

Re: Quicksort/Insertion sort Hyrbid?

Quote originally posted by Jpowers22 ...

Recently we have been asked to create a hybrid sort based upon quicksorting down to a certain point and insertion sorting from then on. We are to calculate the efficency based upon previous tests. I had very little problems implementing a quicksort algorithm, but for the life of me, I can't get anything to work on the hybrid version. Can anyone help, provide tips or pointers?

I'd love to help but could you please be more informative? What do you mean by "I can't get anything to work"? How many passes of quicksort do you do before you do insertion sort?

C Syntax (Toggle Plain Text)
data := "5 2 4 7 3 1 6 8"
left := 0
right := 7
pivot := data[0] = 5
 
partition(data, left, right, pivot)
 
data := "2 4 3 1 5 7 6 8"
left := 0
right := 7
pivot : = data[4] = 5
 
quick_sort(data, left, right, pivot) {
  if left < right { 
    if(threshold(...)) {
      insertion_sort(data)  
    } else {
      pivot := partition(data, left, right, pivot)
      quicksort(data, left, pivot - 1)
      quicksort(data, pivot + 1, right)
    }
  }
}
 
insertion_sort(reference pointer to data) {
 ....
}
data := "5 2 4 7 3 1 6 8"
left := 0
right := 7
pivot := data[0] = 5

partition(data, left, right, pivot)

data := "2 4 3 1 5 7 6 8"
left := 0
right := 7
pivot : = data[4] = 5

quick_sort(data, left, right, pivot) {
  if left < right { 
    if(threshold(...)) {
      insertion_sort(data)  
    } else {
      pivot := partition(data, left, right, pivot)
      quicksort(data, left, pivot - 1)
      quicksort(data, pivot + 1, right)
    }
  }
}

insertion_sort(reference pointer to data) {
 ....
}

Sorry, I have to get back to work. If you could please post code, I can take a look later and help you out more.

subtronic

Reputation Points: 44

Solved Threads: 1

Junior Poster

Offline

117 posts
since Aug 2003

Permalink

Oct 15th, 2004

Re: Quicksort/Insertion sort Hyrbid?

I always find it instructive to see what others have done, and then apply my own style and ideas to the problem. In the case of a Quicksort/Insertion sort hybrid, you could look in Google for some other folk's source code, or if you have VC++, you can look at the source code for their 'qsort()' function. It is not recursive and therefore a bit ugly, but it works great. They've got tuning variables in there for figuring out at what point the insertion sort kicks in.

Like I say, don't copy their code but learn from it.

Chainsaw

Reputation Points: 36

Solved Threads: 11

Posting Pro in Training

Offline

436 posts
since Jun 2004

Permalink

Oct 15th, 2004

Re: Quicksort/Insertion sort Hyrbid?

void quickSort(int numbers[], int array_size)
{
q_sort(numbers, 0, array_size - 1);
}

void q_sort(int numbers[], int left, int right)
{
int pivot, l_hold, r_hold;

l_hold = left;
r_hold = right;
pivot = numbers[left];
while (left < right)
{
while ((numbers[right] >= pivot) && (left < right))
right--;
if (left != right)
{
numbers[left] = numbers[right];
left++;
}
while ((numbers[left] <= pivot) && (left < right))
left++;
if (left != right)
{
numbers[right] = numbers[left];
right--;
}
}
numbers[left] = pivot;
pivot = left;
left = l_hold;
right = r_hold;
if (left < pivot)
q_sort(numbers, left, pivot-1);
if (right > pivot)
q_sort(numbers, pivot+1, right);
}

This is code I used for Left most sorting an array of randomly generated data integer elements.

Basically I want, the program to recurse to the point where insertion sort is more optimal than quicksort...and I honestly don't even have a clue where to start.

Jpowers22

Reputation Points: 12

Solved Threads: 0

Newbie Poster

Offline

5 posts
since Oct 2004

Permalink

Oct 15th, 2004

Re: Quicksort/Insertion sort Hyrbid?

Assuming you have an insertion sort routine, try this modification to your code:

C Syntax (Toggle Plain Text)
void q_sort(int numbers[], int left, int right)
{
    int pivot, l_hold, r_hold;
 
        // If there are few records left to look at, use an insertion sort
        //   because it is faster.
    if ((right - left) < INSERTION_SORT_THRESHOLD)
    {    
        InsertionSort( numbers, left, right );
        return;
    }
    l_hold = left;
    r_hold = right;
. . .
void q_sort(int numbers[], int left, int right)
{
    int pivot, l_hold, r_hold;

        // If there are few records left to look at, use an insertion sort
        //   because it is faster.
    if ((right - left) < INSERTION_SORT_THRESHOLD)
    {    
        InsertionSort( numbers, left, right );
        return;
    }
    l_hold = left;
    r_hold = right;
. . .

and then just tinker with INSERTION_SORT_THRESHOLD's value to see what happens. For example, make it zero to disable the insertion sort, make it huge to ONLY do an insertion sort, and then try something like 5 or 10.

On Windows, you can use GetTickCount() to return the time since boot in miliseconds (mod 32 bits), and that can make for a simple elapsed time counter:

C Syntax (Toggle Plain Text)
void quickSort(int numbers[], int array_size)
{
    DWORD startTime = GetTickCount();
    q_sort(numbers, 0, array_size - 1);
    printf( "Elapsed time:%d ms\n", GetTickCount() - startTime );
}
void quickSort(int numbers[], int array_size)
{
    DWORD startTime = GetTickCount();
    q_sort(numbers, 0, array_size - 1);
    printf( "Elapsed time:%d ms\n", GetTickCount() - startTime );
}

This isn't perfect for production code because the tick count will flip over eventually, but for your testing on where to put the insertion sort threshold this should do fine.

Chainsaw

Reputation Points: 36

Solved Threads: 11

Posting Pro in Training

Offline

436 posts
since Jun 2004

Permalink

Oct 15th, 2004

Re: Quicksort/Insertion sort Hyrbid?

>I can't get anything to work on the hybrid version. Can anyone help, provide tips or pointers?
Oddly enough, I posted the full implementation for an optimized quicksort in the code snippets on this site. One of the optimizations is terminating recursion on small subfiles and then calling insertion sort on the "almost" sorted file. An alternative is to use insertion sort during recursion, but that typically has less desirable properties than waiting until after the recursive steps. Because you're testing performance, it couldn't hurt to implement both and see what you get.

I also give examples of two other improvements to the basic algorithm, one common and the other not so common because it's rather difficult and not well known.

>to recurse to the point where insertion sort is more optimal than quicksort
This really needs to be tweaked by the implementor, but a cutoff somewhere between 5 and 25 will work nicely in general and that's where you usually find yourself setting it.

Narue

Administrator

Reputation Points: 6442

Solved Threads: 1393

Bad Cop

Offline

11,807 posts
since Sep 2004

Permalink

Oct 16th, 2004

Re: Quicksort/Insertion sort Hyrbid?

One interesting way to figure out optimizations is through experimentation. You can time each pass for each implementation, record results and then plot them side by side on a graph. You can make adjustments accordingly to the insertion sort version's threshold to see if there's improvements.

subtronic

Reputation Points: 44

Solved Threads: 1

Junior Poster

Offline

117 posts
since Aug 2003

Permalink

Oct 17th, 2004

Re: Quicksort/Insertion sort Hyrbid?

Quote originally posted by subtronic ...

One interesting way to figure out optimizations is through experimentation. You can time each pass for each implementation, record results and then plot them side by side on a graph. You can make adjustments accordingly to the insertion sort version's threshold to see if there's improvements.

Thats what I did, I found that the threshold value for the size of arrays I was dealing with would show increased efficiency at around 25 and lower.

Jpowers22

Reputation Points: 12

Solved Threads: 0

Newbie Poster

Offline

5 posts
since Oct 2004

Permalink

Oct 17th, 2004

Re: Quicksort/Insertion sort Hyrbid?

Quote originally posted by Narue ...

>I can't get anything to work on the hybrid version. Can anyone help, provide tips or pointers?
Oddly enough, I posted the full implementation for an optimized quicksort in the code snippets on this site. One of the optimizations is terminating recursion on small subfiles and then calling insertion sort on the "almost" sorted file. An alternative is to use insertion sort during recursion, but that typically has less desirable properties than waiting until after the recursive steps. Because you're testing performance, it couldn't hurt to implement both and see what you get.

I also give examples of two other improvements to the basic algorithm, one common and the other not so common because it's rather difficult and not well known.

>to recurse to the point where insertion sort is more optimal than quicksort
This really needs to be tweaked by the implementor, but a cutoff somewhere between 5 and 25 will work nicely in general and that's where you usually find yourself setting it.

Narue,
I checked your excellent sorting snippet, and have a question. Is there a way to time this, milliseconds is much to slow? I know one could increase the size of the array, but that's not challenging. Something like a microsecond or nanosecond timer would help.

vegaseat

Moderator

Reputation Points: 1333

Solved Threads: 1404

DaniWeb's Hypocrite

Offline

5,792 posts
since Oct 2004

Permalink

Oct 17th, 2004

Re: Quicksort/Insertion sort Hyrbid?

Quote originally posted by vegaseat ...

Narue,
I checked your excellent sorting snippet, and have a question. Is there a way to time this, milliseconds is much to slow? I know one could increase the size of the array, but that's not challenging. Something like a microsecond or nanosecond timer would help.

struct timeval

subtronic

Reputation Points: 44

Solved Threads: 1

Junior Poster

Offline

117 posts
since Aug 2003

Page 1
2
Next

This thread is more than three months old

No one has posted to this discussion for at least three months. Please let old threads die and do not reply to them unless you feel you have something new and valuable to contribute that absolutely must be added to make the discussion complete. Otherwise, please start a new thread in this forum instead.

Previous Thread in C Forum Timeline: 6 Line class -> Me pounding head into wall

Next Thread in C Forum Timeline: Func like getlastkey() or something like that?

DaniWeb Message

Cancel Changes

User Name
Password