Programming

Hi all,
Can someone explain to me how shell sort works and tell me why it can not be used on linked lists.
Thanks

Do you mean the sort command? There is a man page on it. Type "man sort". It reads its input from stdin and the input must be text data of some kind.

no, i mean shell sort, which is apparently a kind of insertion sort. they also call it diminishing-increment sort.

the best way to learn is by going thru "The Stuff"...

not the least of which is a simple search on google...

here is what I got for "shell sort".. you may get better...

http://linux.wku.edu/~lamonml/algor/sort/shell.html

also you can refer standard books on Algorithms and DataStructures by people like Tanenbaum etc. in your local library...

Cheers!
Vishnu.

You know, this certainly seems like a homework question. Looking over the other questions that you've asked, I have to say they all do. Did you miss our rules? If so, please read them and especially note:

(6) Do not post classroom or homework problems.

Hi all...

Please be sure while u give the solution to others, if u dont know the answer please dont give some dummy answers,

I have seen in this page, there is some replies which is absolutely away from the question... common guys this is a very good chance to share our knowledge and learn more...

fine here is my answer for the shell sort...


the shell sort is also the most complex of the O(n2) algorithms.

The shell sort is a "diminishing increment sort", better known as a "comb sort" to the unwashed programming masses. The algorithm makes multiple passes through the list, and each time sorts a number of equally sized sets using the insertion sort. The size of the set to be sorted gets larger with each pass through the list, until the set consists of the entire list. (Note that as the size of the set increases, the number of sets to be sorted decreases.) This sets the insertion sort up for an almost-best case run each iteration with a complexity that approaches O(n).

The items contained in each set are not contiguous - rather, if there are i sets then a set is composed of every i-th element. For example, if there are 3 sets then the first set would contain the elements located at positions 1, 4, 7 and so on. The second set would contain the elements located at positions 2, 5, 8, and so on; while the third set would contain the items located at positions 3, 6, 9, and so on.

The size of the sets used for each iteration has a major impact on the efficiency of the sort. Several Heroes Of Computer ScienceTM, including Donald Knuth and Robert Sedgewick, have come up with more complicated versions of the shell sort that improve efficiency by carefully calculating the best sized sets to use for a given list.

Pros: Efficient for medium-size lists.
Cons: Somewhat complex algorithm, not nearly as efficient as the merge, heap, and quick sorts.

Empirical Analysis
=============

Shell Sort Efficiency
==============

The shell sort is by far the fastest of the N2 class of sorting algorithms. It's more than 5 times faster than the bubble sort and a little over twice as fast as the insertion sort, its closest competitor.

The shell sort is still significantly slower than the merge, heap, and quick sorts, but its relatively simple algorithm makes it a good choice for sorting lists of less than 5000 items unless speed is hyper-critical. It's also an excellent choice for repetitive sorting of smaller lists.

Source Code
Below is the basic shell sort algorithm.


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

increment = 3;
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;
}
if (increment/2 != 0)
increment = increment/2;
else if (increment == 1)
increment = 0;
else
increment = 1;
}
}

krishna,

It is not a matter of any of us not wanting to help someone. It is a matter of Ethics and following respecting the Creator of this website. The rules of this forum strictly forbid posting of homework. We are not here to do other people's homework. They will not learn it as well unless they do the research on their own.

I don't mind advising those folks who are in a work environment and need help with real world problems, but, I do mind giving away free answers to folks who are doing this for a grade. It is unethical to seek answers from other people when they are doing the work for a reward such as a diploma or degree.

My philosophy is this: " If I do the work, I get credit for it. If someone else does my work, THEY should get credit and I should fail that course."

All of us that patronize this site have a responsibility to follow its rules. And all of us have a responsibility to enforce it rules.

Thanks for your effort to be helpful, but please use good judgement when posting answers to queries.

thanks and keep on posting