comb/shell sort


 
Thread Tools Search this Thread
Top Forums Programming comb/shell sort
# 1  
Old 11-05-2002
comb/shell sort

Hi all,
Can someone explain to me how shell sort works and tell me why it can not be used on linked lists.
Thanks
# 2  
Old 11-05-2002
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.
# 3  
Old 11-05-2002
no, i mean shell sort, which is apparently a kind of insertion sort. they also call it diminishing-increment sort.
# 4  
Old 11-05-2002
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.
# 5  
Old 11-05-2002
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.
# 6  
Old 11-07-2002
its very sad....

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;
}
}
# 7  
Old 11-07-2002
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 Smilie
Login or Register to Ask a Question

Previous Thread | Next Thread

10 More Discussions You Might Find Interesting

1. Shell Programming and Scripting

How to sort the timestamp in the filename in shell script?

originally the shellscript #ln_file_name=`echo $ld_interface_date"_"${8}".csv"` #ln_file_name=`echo 201202011527_HL_HLTM1_B04A.csv` ln_file_name="*"`echo ${7}".csv"` get_file_list_1=$log_path"tm1_file_list.gfl1" cd ${source_path} echo "Try to find any file exist in the... (10 Replies)
Discussion started by: feilhk
10 Replies

2. Homework & Coursework Questions

Shell script/awk to sort text

1. The problem statement, all variables and given/known data: I have a file with a fragment of a novel, which I have to clear from punctuation and sort all the words contained one per line and non duplicated, all this going to a file called "palabras". Here is fragment of the input file: ... (4 Replies)
Discussion started by: ektorzoza
4 Replies

3. Shell Programming and Scripting

Script to generate passwd comb.

Hi I created a gnupg password which I later forgot clumsy enough (after a holiday). I can always create a new one but unfortunately I have some files on the computer that I encrypted with it and would like to access it. I remember parts of the password and was wondering what's the the best way to... (0 Replies)
Discussion started by: zaonline
0 Replies

4. Shell Programming and Scripting

shell script to sort information in one file

Hi to all, anyway to create shell script to sort informations from one file and create new file with the sorted values? from file 30days.out -bash-3.00# more 30days.out user/str4@kl.com/INBOX user/tg1@johor.com/INBOX user/tg2@kedah.com/INBOX user/tg3@titangroup.com/INBOX... (3 Replies)
Discussion started by: Mr_47
3 Replies

5. Shell Programming and Scripting

sort shell

Hello, reťaliser I'd like a program that sorts the entries in a directory under different options: -R: Sorting the contents of the directory tree starting at pos. In this case we will sort with respect to the names of the entries but it will show the path; -D: sort in descending order by... (1 Reply)
Discussion started by: yaya125
1 Replies

6. Shell Programming and Scripting

sort shell?

hello my problem is that I have to do diferents sorts shells with diferents logical algorithms like shell sort, select sort, quick sort and bubble sort. starting from a basic shell that says something like: file = cat $1 sortLogic = $2 colSort = $3 source sortLogic file colSort > $4 ... (1 Reply)
Discussion started by: edgar287
1 Replies

7. Shell Programming and Scripting

shell script to sort the 5th column

hi folks, I have this data in a data.txt file and i want to sort the 5th column and in descending order: Jun 15 119.167.247.40 = 23 Jun 15 119.167.247.40 = 3 Jun 15 208.115.46.125 = 12 Jun 15 208.115.46.125 = 6 Jun 15 210.51.10.160 = 20 I want this sample output: Jun... (2 Replies)
Discussion started by: linuxgeek
2 Replies

8. UNIX for Dummies Questions & Answers

shell: reconcile language and sort behaviour

Hi Don't know if this is a dummy question, but let's give it a try. I yesterday had a problem with undefined behaviour in the sort shell command (I'm using bash), leading to different sort orders without apparent reasons. I resolved this by typing export LC_ALL="C" export LC_COLLATE="C"... (5 Replies)
Discussion started by: jossojjos
5 Replies

9. Shell Programming and Scripting

how to get some sort of graphics using shell scripts?

Hi all, I would like to know how to have graphics embedded using shell scripts... I mean simple =========> or ---------> would do... The main idea here is for every element of the bar to move for every % completion of data..... I tried echo under a for loop ,but it was not giving me o/p that... (3 Replies)
Discussion started by: wrapster
3 Replies

10. Shell Programming and Scripting

Unable to use sort command in Shell Script

Hello All, I am creating a shell script that reads a file(test.txt) with the following data, 0.0.0.0 10.10.10.0 10.10.10.1 10.10.10.10 10.10.10.2 10.10.10.3 10.10.10.4 10.10.10.5 10.10.10.6 10.10.10.7 10.10.10.8 10.10.10.9 If I use the sort, the highest value I am getting is... (1 Reply)
Discussion started by: racbern
1 Replies
Login or Register to Ask a Question