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;
}
}
10 More Discussions You Might Find Interesting
1. Shell Programming and Scripting
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
2. Shell Programming and Scripting
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
3. UNIX for Dummies Questions & Answers
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
4. Shell Programming and Scripting
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
5. Shell Programming and Scripting
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
6. Shell Programming and Scripting
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
7. Shell Programming and Scripting
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
8. Shell Programming and Scripting
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
9. Homework & Coursework Questions
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
10. Shell Programming and Scripting
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
LEARN ABOUT CENTOS
wrap-and-sort
WRAP-AND-SORT(1) General Commands Manual WRAP-AND-SORT(1)
NAME
wrap-and-sort - wrap long lines and sort items in Debian packaging files
SYNOPSIS
wrap-and-sort [options]
DESCRIPTION
wrap-and-sort wraps the package lists in Debian control files. By default the lists will only split into multiple lines if the entries are
longer than 80 characters. wrap-and-sort sorts the package lists in Debian control files and all .install files. Beside that wrap-and-sort
removes trailing spaces in these files.
This script should be run in the root of a Debian package tree. It searches for control, control.in, copyright, copyright.in, install, and
*.install in the debian directory.
OPTIONS
-h, --help
Show this help message and exit.
-a, --wrap-always
Wrap all package lists in the Debian control file even if the entries are shorter than 80 characters and could fit in one line line.
-s, --short-indent
Only indent wrapped lines by one space (default is in-line with the field name).
-b, --sort-binary-packages
Sort binary package paragraphs by name.
-k, --keep-first
When sorting binary package paragraphs, leave the first one at the top. Unqualified debhelper(7) configuration files are applied to
the first package.
-n, --no-cleanup
Do not remove trailing whitespaces.
-d path, --debian-directory=path
Location of the debian directory (default: ./debian).
-f file, --file=file
Wrap and sort only the specified file. You can specify this parameter multiple times. All supported files will be processed if no
files are specified.
-v, --verbose
Print all files that are touched.
AUTHORS
wrap-and-sort and this manpage have been written by Benjamin Drung <bdrung@debian.org>.
Both are released under the ISC license.
DEBIAN
Debian Utilities WRAP-AND-SORT(1)