Talk:Insertion sort

From Wikipedia, the free encyclopedia

Question: Which language is the example implementation written in?

The example is written in Python. I'm planning on simplifying it a bit, in particular to remove the cmp function being passed as a parameter:

• A built-in function cmp() already exists, and means something different (-ve if ab);
• IMO, Python's lambda notation and default arguments are not appropriate for near pseudo-code;
• "a > b" is much better for trying to understand an algorithm than a function call.
• Custom Python types can define their own comparisons anyway, so a comparator parameter is unnecessary.

--Carey Evans

Should heapsort be listed as type of insertion sort ? --Taw

No. Heapsort is more closely related to selection sort. --Damian Yerrick

Actually heapsort and insertion sort have a pretty close relation. In both, you are taking the elements of the list and successively inserting them into a data structure from which you can, at the end, extract the sorted sequence. In selection sort you actually search the unsorted elements; in these sorts you simply present the unsorted elements sequentially. Deco 05:54, 29 Mar 2005 (UTC)

Contents 1 Removed mergesort statement 2 Implementations 3 Implementations 3.1 Java 3.2 C 3.3 Pascal And PYTHON 3.4 Standard ML (SML) 3.5 LISP 3.6 Haskell 3.7 Visual Basic .NET (Visual Basic .NET)

[edit] Removed mergesort statement

I removed this statement:

This is even less than Merge sort for finite n, though both do O(n log n) comparisons.

Not only is this silly (you can't sort infinite lists in finite time, especially not with this sort) but it assumes that merge sort runs in exactly n log n time, rather than just Θ(n log n) time. The truth is that:

Now, we can bound it on both sides with integrals:

So in fact log n! is Θ(nlogn), no different from mergesort (if we could somehow avoid the time for the swaps.) Deco 05:54, 29 Mar 2005 (UTC)

[edit] Implementations

I removed the following from the article, as most (if not all) are listed on the wikibook page. They can be added back if desired --DevastatorIIC 14:00, 31 May 2006 (UTC)

I've fixed the C example of insertionSort, now works properly without memory underflow, if the unsorted element shoul dbe inserted on the first position, the algorithm could insert the number on address *(array - 1).

Also i've changed the a[] variable for array[] for more readability. This example may be more suitable for understanding because no sub-functions are used.

17:35, 16 Sep 2006

[edit] Implementations

[edit] Java

 void insertSort(int vector[]) {
     int indPost, indAnt, nextElement;
 
     for(indPost = 1; indPost < vector.length; indPost++) {
         nextElement = vector[indPost];
         for (indAnt = indPost  - 1; indAnt  >= 0 && vector[indAnt] > nextElement; --indAnt) {
             vector[indAnt  + 1] = vector[indAnt];
         }
         vector[indAnt  + 1] = nextElement ;
     }
 }

[edit] C

void insertSort(int array[], size_t length)
{
     int i, j, value;
 
     for(i = 1; i < length; ++i)
     {
         value = array[i];
         for (j = i - 1; j >= 0 && array[j] > value; j--) 
         {
             array[j + 1] = array[j];
         }
         array[j + 1] = value;
     }
 }

[edit] Pascal And PYTHON

        procedure InsertSort(var v:InArray ; EndArray:integer);
        var j, k, swp: integer;
        begin
              for j := 1 to EndArray do
                 begin
                    swp := v[j] ;
                    k := j - 1 ;
                    while (k >= 1 ) and (swp < InArray[k]) do
                         begin
                             v[k + 1] := v[k];
                             k := k - 1;
                         end;
                     v[k + 1] := swp;
                 end;
        end;
## PYTHON
def InsertionSort(list):
  
  n=len(list)

    for i in range (1,n):

        swp=list[i]

        j=i-1

        while j>=0 and swp<list[j]:

                list[j+1]=list[j]

                j=j-1

        list[j+1]=swp

    print list
###

[edit] Standard ML (SML)

 fun insert(i, []) = [i]
   | insert(i, x::xs) = 
       if i < x then i::x::xs
       else x::insert(i, xs);
 
 fun insertsort([]) = []
   | insertsort(x::xs) = insert(x, insertsort(xs));

[edit] LISP

 (defun insert (x l)
    (cond ((null l) (list x))
          ((< x (first l)) (cons x l))
          (t (cons (first l) (insert x (rest l))))))
 
 (defun insertsort (l)
    (cond ((null l) ())
          (t (insert (first l) (insertsort (rest l))))))

[edit] Haskell

 -- Insert an item into the correct position in a sorted list.
 insert :: Ord a => a -> [a] -> [a]
 insert x [] = [x]
 insert x (y:ys) | x <= y    = x:y:ys
                 | otherwise = y:(insert x ys)
 
 -- Sort a list by inserting its elements into an empty one.
 insertionSort :: Ord a => [a] -> [a]
 insertionSort = foldr insert []

[edit] Visual Basic .NET (Visual Basic .NET)

       Dim j As Integer

       For i As Integer = 1 To Array.GetUpperBound(0)
           j = i - 1
           Dim Value As Integer = Array(i)
           While j >= 0 And Array(j) > Value
               Array(j + 1) = Array(j)
               j -= 1
           End While
           Array(j + 1) = Value
       Next