Home arrow Practices arrow Page 4 - Sort This Sort That

Decrementing Increment or Just Shell-Sort - Practices

One of the main activities in algorithms and programs, whose purpose is manipulating data, is sorting. So if you write these kinds of programs-what kind of method for sorting data is best? In this article I will present some algorithms for sorting and their advantages and weaknesses.

TABLE OF CONTENTS:
  1. Sort This Sort That
  2. Sorting
  3. Inserting Methods
  4. Decrementing Increment or Just Shell-Sort
  5. Selection Methods
  6. Sorting with Binary Tree
  7. Left(node) and Right(node)
By: Djordje Popovic
Rating: starstarstarstarstar / 21
February 25, 2004

print this article
SEARCH DEV SHED

TOOLS YOU CAN USE

advertisement

Shell-sorting is a better solution than insertion-sort, but it also contains insertion-sorting. First it splits our unsorted array into groups. In each group are elements whose positions in the array are on equidistant positions.

The number of spaces between elements in groups is called increment h1. Tbe number of groups, naturally, suits the value of increment. Now each group is sorted by insertion-sort method, after that our array is h1-sorted.

In our next step our increment is decremented and its value is h2.  Then we form smaller numbers of groups with more elements per group. Our algorithm ends when our increment reaches value one. This means that now we just use insertion-sort on the whole array, after that our array is completely sorted.
 
Letís see what this algorithm looks like:


SHELL-SORT:
for i 
=1 to n do 
inc
=h[i]
 
for j=inc+1 to n do
  y
=a[j]
  k
=j-inc
  
while ((k>=1) and (y<=a[k])) do
   a
[k+inc] = a[k]
   k
=k-inc
  end_while
 end_for
end_for

In this algorithm we assume that we have our increments in an array h[1:t]. Notice that everything inside the second for loop is just insertion-sort method used on groups.

It's not obvious that this method has better performances than insertion-sort, but it does. In the beginning our increment h is big so groups are smaller, that means that speed increases on each group using insertion-sort. Each consecutive step our groups are bigger, but now those groups are sorted, facilitating insertion-sort on remaining groups. See step-by-step how this works below:

sorting

 



 
 
>>> More Practices Articles          >>> More By Djordje Popovic
 

blog comments powered by Disqus
escort Bursa Bursa escort Antalya eskort
   

PRACTICES ARTICLES

- Calculating Development Project Costs
- More Techniques for Finding Things
- Finding Things
- Finishing the System`s Outlines
- The System in So Many Words
- Basic Data Types and Calculations
- What`s the Address? Pointers
- Design with ArgoUML
- Pragmatic Guidelines: Diagrams That Work
- Five-Step UML: OOAD for Short Attention Span...
- Five-Step UML: OOAD for Short Attention Span...
- Introducing UML: Object-Oriented Analysis an...
- Class and Object Diagrams
- Class Relationships
- Classes

Developer Shed Affiliates

 


Dev Shed Tutorial Topics: