Home arrow Practices arrow Page 5 - Sort This Sort That

Selection 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

The main strategy for the selection methods is to find, in each step, smaller or greater elements in unsorted arrays. Then place these elements as the first elements of sorted arrays. This strategy assumes that our array will have two parts: sorted and unsorted.

First method from this group is selection-sort:


SELECTION-SORT:
for i
=1 to n-1 do
 min
=a[i]
 pos
=i
 
for j=i+1 to n do 
  
if(a[j]<minthen
   min
=a[j]
   pos
=j
  end_if
 end_for
 a
[pos]=a[i]
 a
[i]=min
end_for

Here we have, just like in the insertion-sort method, sorted and unsorted parts of our array. In the beginning the whole array is unsorted so we find the smallest value in our array and exchange it for the first element in the array.

After i-1 iterations we have the sorted part (a[1], ... , a[i-1]) and the unsorted part (a[i], ... , a[n]). In the next iteration we find the smallest value in the unsorted part and change its place with the first element from the sorted part, in that way this element becomes a part of the sorted part.

A critical part of this algorithm is that in each step it needs to find the smallest value from the unsorted part of our array.  This can be accomplished by splitting the unsorted part in groups and finding the smallest value in each group, termed the "local minimum". Now finding the smallest value of the whole unsorted part is finding the smallest value of all local minimums. In the next step we just need to find one local minimum.



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