Tek-Tips is the largest IT community on the Internet today!
Members share and learn making Tek-Tips Forums the best source of peer-reviewed technical information on the Internet!
-
Congratulations strongm on being selected by the Tek-Tips community for having the most helpful posts in the forums last week. Way to Go!
Sorting
- Thread starter Greeno
- Start date
MichaelRed
Programmer
There are already numerous threads on the topic. Unfortunatly the search part of the site is not currently available, so I cannot point directly to any of them. If you can 'wait', the resources and references are quite extensive and will easily provide the necessary material.
MichaelRed
redmsp@erols.com
There is never time to do it right but there is always time to do it over
MichaelRed
redmsp@erols.com
There is never time to do it right but there is always time to do it over
edwardtisdale
Programmer
This is from the book DATA STRUCTURES USING C AND C++ second edition by Langsam, Augenstein, and Tenenbaum:
1. Bubble Sort: least efficient.
x= array of integers
sorting 1 to n
pass through the file sequentially several times, comparing each element with its successor and interchanging if they are in the wrong order
2. Indentation Sort. did not find. Ask if it is the same as n insertion sort.
3. Shell Sort(or diminishing increment sort):sorts several subfiles of the original file, each containing a Kth element of the original file. K is called increment and there is x[k] from 0 to n.
for two successive files i and j, x[(i-1)*k+j-1]. After the first k subfiles are sorted (usually by insertion) a smaller k is chosen. and shell sorted again. ...
.
.
.
ex:
first iteration: k=5
(x[0],x[5])
(x[1],x[6])
(x[2],x[7])
(x[3])
(x[4])
second iteration: k=3
(x[0],x[3],x[6])
(x[1],x[4],x[7])
(x[2],x[5])
third iteration:k=1
(x[0],x[1],...,x[n=7])
c/c++ code:
void shellsort(int x[], int n, int incrmnts[], int numinc)
{
int incr,j,k,span,y;
for(incr=0;incr<numinc;incr++){
/*span is size of increment*/
span=incrmnts[incr];
for (j=span;j<n;j++){
/*insert element x[j] into its proper position within its subfile*/
y=x[j];
for (k=j-span;k>=0 && y<x[k];k -= span)
x[k+span]=x[k];
x[k+span]=y;
}
}
}
recommended for moderately sized files of several undred elements.
1. Bubble Sort: least efficient.
x= array of integers
sorting 1 to n
pass through the file sequentially several times, comparing each element with its successor and interchanging if they are in the wrong order
2. Indentation Sort. did not find. Ask if it is the same as n insertion sort.
3. Shell Sort(or diminishing increment sort):sorts several subfiles of the original file, each containing a Kth element of the original file. K is called increment and there is x[k] from 0 to n.
for two successive files i and j, x[(i-1)*k+j-1]. After the first k subfiles are sorted (usually by insertion) a smaller k is chosen. and shell sorted again. ...
.
.
.
ex:
first iteration: k=5
(x[0],x[5])
(x[1],x[6])
(x[2],x[7])
(x[3])
(x[4])
second iteration: k=3
(x[0],x[3],x[6])
(x[1],x[4],x[7])
(x[2],x[5])
third iteration:k=1
(x[0],x[1],...,x[n=7])
c/c++ code:
void shellsort(int x[], int n, int incrmnts[], int numinc)
{
int incr,j,k,span,y;
for(incr=0;incr<numinc;incr++){
/*span is size of increment*/
span=incrmnts[incr];
for (j=span;j<n;j++){
/*insert element x[j] into its proper position within its subfile*/
y=x[j];
for (k=j-span;k>=0 && y<x[k];k -= span)
x[k+span]=x[k];
x[k+span]=y;
}
}
}
recommended for moderately sized files of several undred elements.
- Status
Similar threads