Solved

# Is shell sort faster than qsort?

Posted on 2003-02-24
Medium Priority
320 Views
Hi,
The following version of shell sort performed atleast 5 times faster than qsort with 100000 records. How is that possible?

void shellSort(unsigned long numbers[], unsigned long array_size)
{
unsigned long  i, j, increment, temp;

increment = array_size /2;
while (increment > 0)
{
for (i=0; i < array_size; i++)
{
j = i;
temp = numbers[i];
while ((j >= increment) && (numbers[j-increment] > temp))
{
numbers[j] = numbers[j - increment];
j = j - increment;
}
numbers[j] = temp;
}
increment /= 2;
}
}
0
Question by:nagubala
[X]
###### Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

• Help others & share knowledge
• Earn cash & points
• 9
• 7
• 2
• +1

LVL 8

Expert Comment

ID: 8014391
Actually everything depends on the type of input you are using and how much data is already sorted and size of the data?
And I don't think the function you are using is doing shell sort!!

-Narendra
0

Expert Comment

ID: 8014465
Qsort is a recusive function.  Its not faster just more compact easier to read code.  Shell sort is a good function.
0

LVL 8

Expert Comment

ID: 8014538
>Qsort is a recusive function
It can be implemented as iterative also! You have to leave out the processor times in calling functions, doing recursion etc., while doing algorithm analysis. If you are taking recursion time into account, then the same Qsort implemented with iterative method will run faster than that of recursion. That doesn't mean Qsort is faster than Qsort!!:-)
Take into consideration only the number comparisons done and number of element movements.

-Narendra
0

Author Comment

ID: 8014555
Can someone compare the results of this fn I gave and the fastest qsort whatever available and give me an estimate?
0

Author Comment

ID: 8014583
Can someone compare the results of this fn I gave and the fastest qsort whatever available and give me an estimate?
0

Author Comment

ID: 8014588
Also assume the worst case scenario where the list is completely reversed.
0

LVL 8

Expert Comment

ID: 8014621
First you said, it runs 5 times faster! Then you should have the code for Qsort! And you have to tell us how you did the analysis!:-)

-Narendra
0

Author Comment

ID: 8014857
OK....here is my program and the results...

The program is running under MSVC++ 6.0 on a WinXP with 256MB RAM, P4-1.5 Ghz. I am sorting a list of 1.5 million elements. U can reduce that if ur machine is slower.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define MAX_ITEMS  1500000L

unsigned long  Array1[MAX_ITEMS];
unsigned long  Array2[MAX_ITEMS];
unsigned long  Array3[MAX_ITEMS];
unsigned long  Array4[MAX_ITEMS];
unsigned long  Array5[MAX_ITEMS];
unsigned long  Array6[MAX_ITEMS];

void MyQsort(unsigned long numbers[], unsigned long Size)
{
unsigned long pivot, l_hold, r_hold,left,right;

l_hold = left = 0;
r_hold = right = Size-1;
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)
MyQsort(&numbers[left], pivot-left);
if (right > pivot)
MyQsort(&numbers[pivot+1], right-pivot);
}

void shellSort(unsigned long numbers[], unsigned long array_size)
{
unsigned long  i, j, increment, temp;

increment = array_size /2;
while (increment > 0)
{
for (i=0; i < array_size; i++)
{
j = i;
temp = numbers[i];
while ((j >= increment) && (numbers[j-increment] > temp))
{
numbers[j] = numbers[j - increment];
j = j - increment;
}
numbers[j] = temp;
}
increment /= 2;
}
}

unsigned long Next;

unsigned long GetRandomNo(void)
{
Next = (Next * 1103515245) + 12345;
return (Next);
}

int compare( const void *arg1, const void *arg2 )
{
return ( *( (unsigned long *) arg1) - *( (unsigned long *) arg2) );
}

void main(void)
{

unsigned long i, Time1,Time2;

Next = ( (unsigned)time( NULL ) );

for(i=0; i < MAX_ITEMS; i++)
Array1[i] = Array2[i] =  GetRandomNo();

for(i=0; i < MAX_ITEMS; i++)
Array3[i] = Array4[i] = MAX_ITEMS -i;

for(i=0; i < MAX_ITEMS; i++)
Array5[i] = Array6[i] = i;

Time1 = ( (unsigned)time( NULL ) );
qsort( Array1,MAX_ITEMS, sizeof(Array1[0]), compare);
Time2 = ( (unsigned)time( NULL ) );
printf("QS-Rand Time taken = %ld\n", (Time2-Time1));

Time1 = ( (unsigned)time( NULL ) );
shellSort(Array2,MAX_ITEMS);
Time2 = ( (unsigned)time( NULL ) );
printf("SS-Rand Time taken = %ld\n", (Time2-Time1));

Time1 = ( (unsigned)time( NULL ) );
qsort( Array3,MAX_ITEMS, sizeof(Array3[0]), compare);
Time2 = ( (unsigned)time( NULL ) );
printf("QS-Rev Time taken = %ld\n", (Time2-Time1));

Time1 = ( (unsigned)time( NULL ) );
shellSort(Array4,MAX_ITEMS);
Time2 = ( (unsigned)time( NULL ) );
printf("SS-Rev Time taken = %ld\n", (Time2-Time1));

Time1 = ( (unsigned)time( NULL ) );
qsort( Array5,MAX_ITEMS, sizeof(Array5[0]), compare);
Time2 = ( (unsigned)time( NULL ) );
printf("QS-st Time taken = %ld\n", (Time2-Time1));

Time1 = ( (unsigned)time( NULL ) );
shellSort(Array6,MAX_ITEMS);
Time2 = ( (unsigned)time( NULL ) );
printf("SS-st Time taken = %ld\n", (Time2-Time1));

}

The Results:
**********
QS-Rand Time taken = 4
SS-Rand Time taken = 3
QS-Rev Time taken = 2
SS-Rev Time taken = 1
QS-st Time taken = 2
SS-st Time taken = 1

Ofcourse...I was wrong in calculating the fastness...
But Shell sort is supposed to be O(n^2) and the Qsort is supposed to be O(n Log n).
If u argue that the qsort library fn is slow (since its calling the compare fn so many times) then please provide me an implementation which is faster than that.
Note that I am not using thw MyQSort()...since its much slower than the library version.

Tx.
0

Author Comment

ID: 8014943
If I use the register keyword for the local variables n the shellsort fn then the results are even better.

QS-Rand Time taken = 4
SS-Rand Time taken = 2
QS-Rev Time taken = 2
SS-Rev Time taken = 0
QS-st Time taken = 2
SS-st Time taken = 0
0

LVL 8

Expert Comment

ID: 8014970
I am using Linux on Pentium III processor. I got the following results:

QS-Rand Time taken = 8
SS-Rand Time taken = 8
QS-Rev Time taken = 8
SS-Rev Time taken = 11
QS-st Time taken = 6
SS-st Time taken = 9

See how the result varies from processor to processor. Esp. see the 4th value: It is the least in your system and heighest in my system!!!

So, as I said earlier, you should not take the time it took to complete the function. Because recursion and function calls add considerable time and they change from implementation to implementation. Instead, count the number of comparisons made and number of movements (like exchange) of data you have to make. This is the actual pointer to the speed of an algorithm. If you still have doubts on what I am saying, then please refer any book on algorithm analysis and they show how the analysis has to be done. There are variuous things you will have to consider while doing that.

But, we can conclude atleast this much from your results:
Shell Sort is running faster than Quick sort on your machine with the data you have given and with the implementation you are using. And the result can change when we change the processor or the implementation.

-Narendra
0

Author Comment

ID: 8015028
I hope you have used the linux library call for qsort().
Can u try using the register keyword for the parameters local variables in the shellsort() and get the results?

What's surprising me is that how could I write some thing in C and almost beat the qsort() library fn. Or I think Qsort performs only as good as shellsort for bigger lists.

I don't think between P3 and P4, there is difference in computational methods. Its the compiler which makes a lot of difference. If u use Windows and MCVC++, then you may also get the same type of results.

0

Author Comment

ID: 8015043
Can u post the code for an iterative implementation of
qsort. I would like to compare with the library version.

Tx.
0

LVL 8

Expert Comment

ID: 8015077
It will not be possible for me to convert the whole code into iterative one and test. I can help you, if you start doing it.......
And tell me which variables of which function you converted to register and tried, so that I can try the same on my m/c and you can compare the results.
But, the way of analysis is different as I mentioned before!:-)

-Narendra
0

Author Comment

ID: 8015122
I understand that analysys is different. But I could not understand how an algorithm with O(n^2) can compete with O(n log n) type algo. They are two different catagories and cannot even come closer. Supposedly!!!

Try the following fn with register

void shellSort(register unsigned long numbers[], register unsigned long array_size)
{
register unsigned long  i, j, increment, temp;

increment = array_size /2;
while (increment > 0)
{
for (i=0; i < array_size; i++)
{
j = i;
temp = numbers[i];
while ((j >= increment) && (numbers[j-increment] > temp))
{
numbers[j] = numbers[j - increment];
j = j - increment;
}
numbers[j] = temp;
}
increment /= 2;
}
}
0

LVL 8

Accepted Solution

ssnkumar earned 60 total points
ID: 8015216
I executed your code on 2 m/c with same configuration. The only difference was Linux-1 had more processes running on it than Linux-2!
Results on Linux-1:
QS-Rand Time taken = 27
SS-Rand Time taken = 15
QS-Rev Time taken = 7
SS-Rev Time taken = 11
QS-st Time taken = 12
SS-st Time taken = 17

Results on Linux-2:
QS-Rand Time taken = 1
SS-Rand Time taken = 2
QS-Rev Time taken = 1
SS-Rev Time taken = 0
QS-st Time taken = 1
SS-st Time taken = 0

The above 2 results are when using register variable. I have already posted before the results for Linux-1 with automatic variables. Now here below I post the results for Linux-2 with auto variable:
QS-Rand Time taken = 1
SS-Rand Time taken = 2
QS-Rev Time taken = 0
SS-Rev Time taken = 1
QS-st Time taken = 1
SS-st Time taken = 0

-Narendra
0

Author Comment

ID: 8015258
Thanks...

Would u now say that shellsort() beats the qsort() almost all the times. My question now is "Is this really shellsort or some new algo with O(nLogN) not O(n^2)". Because it almost behaves like O(nLOgN). Am I right?

0

LVL 8

Expert Comment

ID: 8015389
Yes! Looking only at the results we have got on different machines, we can deduce as you said:-)
But, analyzing only the algorithm part may reveal more or something new! And that is the actual result which you must take into consideration.....:-)
And still I am not sure, whether what you are using is shell sort or not!?

-Narendra
0

LVL 3

Expert Comment

ID: 8016633
>>> I understand that analysys is different. But I could not understand how an algorithm with O(n^2) can compete with O(n log n) type algo. They are two different catagories and cannot even come closer.

Quicksort has an AVERAGE complexity of O(n lg n), but it has a WORST CASE complexity of O(n^2).

Depending on the implementation (and there are actually a number of ways to implement the sort) of Shellsort, the WORST CASE complexity can be O(n^1.5).

So, it is possible to find data (and it looks like your data is an example) where Shellsort will outperform Quicksort.  In fact, for mid-sized data sets, Shellsort performs nearly as well if not better than the faster (n log n) sorts.

If you are looking for a sort that consistantly performs at O(n lg n), use Mergesort.

Hope this helps,

Marc
0

LVL 3

Expert Comment

ID: 8016771
Also, as a side note, the C Standard does not specify the algorithm to be used to implement qsort.  As a result, either quicksort or heapsort could be used (or even someting else).

Even if the compiler you use does use quicksort underneath, a  better test would be to use your own implementation. As ssnkumar said, you would be better off counting the actual comparisons and exchanges, as this would give a better comparison of the algorithms.

Marc
0

## Featured Post

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Have you thought about creating an iPhone application (app), but didn't even know where to get started? Here's how: ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ Important pre-programming comments: Iâ€™ve never triâ€¦
Examines three attack vectors, specifically, the different types of malware used in malicious attacks, web application attacks, and finally, network based attacks.  Concludes by examining the means of securing and protecting critical systems and infâ€¦
The goal of this video is to provide viewers with basic examples to understand how to use strings and some functions related to them in the C programming language.
The goal of this video is to provide viewers with basic examples to understand and use switch statements in the C programming language.
###### Suggested Courses
Course of the Month11 days, left to enroll