Home arrow Practices arrow Page 3 - Sort This Sort That

Inserting Methods - 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

These methods are based on step-by-step array sorting. You have two parts of an array, sorted and unsorted, so you take one element from the unsorted part and put it in the right place of sorted part.

Let's see an example of direct inserting method or insertion-sort algorithm:


INSERTION-SORT
for i
=2 to n do 
 k
=a[i]
 j
=i-1
 
while( j>0) and (a[j]>kdo
  a
[j+1] = a[j]
  j
=j-1
 end_while
 a
[j+1]=k
end_for

This is how this algorithm works. After i iterations of the for loop, our array has sorted and unsorted parts. (See image below.)  In the next iteration we take the first element from the unsorted part and place it in variable k. In the while loop we compare this variable with the last element in the sorted part of our array. 

If the value of the element in the while loop is bigger than the value of the for loop we move it one place above in our array. Now we take the next element from the sorted part and compare it with variable k.  If this element is bigger we move it up one position in the array. 

We repeat this process until we find an element value bigger than the value of variable k. At this moment we stop the while loop, and place our value of variable k one place behind found value. After our while loop is over (when i reaches value n) our array will be sorted. In this case, in ascending order.

sorting

This method is most effective if our array of keys is smaller and almost sorted.  The worst thing about this algorithm is that it requires much record moving. This leads to the conclusion that our array should be organized as a linked-list if our records are big. In this way we can just reconnect pointers.



 
 
>>> 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: