Talk:Insertion sort

human sorting

the article says

Most humans when sorting—ordering a deck of cards, for example—use a method that is similar to insertion sort.[1]

I beg to differ. Almost all people I know when sorting a deck of cards use something like intro sort. That is, they divide the deck into four decks, like a step of quick sort would do, and then they either sort insertion sort like the single decks, or some people sort the single decks into "Numbers" and "pictures" and then sort them as insertion sort. that is more like intro sort.

Also when people sort lego bricks, I saw mostly things like sorting colors first, then all one-row and all two-row on a pile, then divide them into long and short piles and so on. When doing a jigsaw puzzle, I saw a lot of people to make little piles that seem to belong together. This all resembles more algorithms like quicksort, introsort and radixsort... —Preceding unsigned comment added by 213.61.9.75 (talk) 14:22, 13 May 2011 (UTC)

Standardization

Shouldn't this article be more structurally similar to the Merge Sort article? --Guugolpl0x (talk) 03:58, 6 September 2010 (UTC)

improvement

This sample code is simple but is not efficient.

insertionSort(array A)
begin
    for i := 1 to length[A]-1 do
    begin
        value := A[i];
        j := i - 1;
        while j >= 0 and A[j] > value do
        begin
            A[j + 1] := A[j];
            j := j - 1;
        end;
        A[j + 1] := value;
    end;
end;

I would like to draw your attention to the end of for loop. 'A[j + 1]' is ALWAYS written back by 'value'. In addition, 'j' is also modified even insertion is not needed. This is waste of time.

In optimization-based point of view, 'j' is written by 'i - 1'; however, 'j' should be written by 'i'. 'j + 1' also should be replaced by 'j' and 'j' should be replaced by 'j - 1'. This change will help compilers to be able to generate good codes. 'j >= 0' is not needed in the first time.

Yaneurao shows an improved insertion sort implementation.

// yaneurao's insertion sort
for (int i = 1; i < MAX; i++) 
{
	int tmp = t[i];
	if (t[i-1] > tmp)
	{
		int j = i;
		do {
			t[j] = t[j-1];
			--j;
		} while ( j > 0 && t[j-1] > tmp);
		t[j] = tmp;
	}
}

This implementation will produce about 30% faster code than the original example.

Yaneurao says insertion sort is very useful when the size of array is small or the array is partially organized, therefore an improvement of insertion sort is very important. Surely, the original example is simple; however, it lacks essence of insertion sort. If you are not interested in performance, you can just use qsort which is usually provided by standard libraries.

You can find a similar sort code in famous Shogi program named Bonanza. That is, a insertion sort is often used by board game programs which need speed.

// Bonanza's descending order insertion sort
psortv[n] = INT_MIN; // put a delimiter in the last element.
for ( i = n-2; i >= 0; i-- )
{
	// If you regard 'sortv' and 'move' as 'tmp' variable
	// this is a normal insertion sort but loop variable moves descending order.
	sortv = psortv[i];  move = pmove[i];
	for ( j = i+1; psortv[j] > sortv; j++ )
	{
		// move one by one because of descending order
		psortv[j-1] = psortv[j];  pmove[j-1] = pmove[j];
	}
	psortv[j-1] = sortv;  pmove[j-1] = move;
}

Bonanza's insertion sort code is not optimized enough; however, Bonanza's source code offers a useful example that typical insertion sort codes can be modified to descending order insertion sort codes and delimiter is used.

--59.146.253.157 (talk) 05:08, 28 November 2009 (UTC)

---I was also going to complain about this and other factors, a being it is not pseudocode, it is code. And unless you feel like looking up how to write Pascal it is almost incomprehensible(eg what is value? should be temp or something more explanatory), I guess the same can be said for the selection sort wiki page that has examples of java and c, however I know these two so not so bad for me, But I'm guessing others would have this problem. A nice "ENGLISH" like example should replace this code. eg.

  for each element in the array(traverse ascending)    do
  element i = 1
  temp = Array[i] 
  if Array[i - 1] > temp 
     element j = i
     do 
        Array[j] = Array[j-1] 
        j = j - 1
     while  j > 0 && Array[j-1] > temp
     Array[j] = temp
  end if
  i = i + 1

end for DONE

or something like that ^^ something more universal(preferably a bit better than my example), rather than a random language or additionally include examples for each of the top 10 languages. 124.171.188.197 (talk) 13:44, 7 December 2009 (UTC)

---

on the other hand I was still able to read and interpret, I just think these examples should not be included or if included then as english like as possible 124.171.188.197 (talk) 14:03, 7 December 2009 (UTC)

sort

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 a<b, 0 if a=b, +ve if a>b);
• 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

Could the example semi-pseudocode on the main page please be cleaned so that it looks like one language, rather than C with a dab of Eiffel? 193.203.149.227 18:34, 28 May 2007 (UTC)

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)

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:

$\log n!=\log \prod _{i=1}^{n}i=\sum _{i=1}^{n}\log i.$

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

$n\log n-n+1=\int _{x=1}^{n}\log x<\sum _{i=1}^{n}\log i<\int _{x=1}^{n+1}\log x=(n+1)\log(n+1)-n$

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

Erm...what? XreDuex (talk) 17:50, 13 March 2008 (UTC)

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

DELETED THE IMPLIMENTATIONS FROM THE TALK PAGE ::

Since they've been deleted for more than a year, they're just clutter. Fresheneesz (talk) 09:43, 5 December 2007 (UTC)

More implementations

For some reason, people feel compelled to add implementations to this page. Here are some I just removed from the page:

c++ Example:

#include <iostream>
#include <cstdio>

//Originally Compiled tested with g++ on Linux
using namespace std;

bool swap(int&, int&); //Swaps Two Ints
void print_array(int* ar, int); //Nothing Just Shows The Array Visually
int ins_sort(int*, int); //The Insertion Sort Function

int main()
{
	int array[9] = {4, 3, 5, 1, 2, 0, 7, 9, 6}; //The Original Array
	desc(array, 9);
	*array = ins_sort(array, 9);
	cout << "Array Sorted Press Enter To Continue and See the Resultant Array" << endl
  	     << "-----------------8<-------------------------------->8--------------";
	getchar();
        desc(array, 9);
        getchar();
	return 0;
}
int ins_sort(int* array, int len)
{
	for (int i = 0; i < len; i++)
        {
		int val = array[i];
		int key = i;
		cout << "key(Key) = " << key << "\tval(Value) = " << val << endl;
		for (; key >= 1 && array[key-1] >= val; --key)
                {
			cout << "Swapping Backward\tfrom (key) " << key << " of (Value) " << array[key] << "\tto (key) " << key-1
                             << " of (Value) " << array[key-1];
			cout << "\n\t" << key << " <----> " << key-1 << "\t( " << array[key] << "<----> " << array[key-1] << " )";
			swap(array[key], array[key-1]);
			desc(array, 9);
		}
	}
	return *array;
}
bool swap(int& pos1, int& pos2)
{
	int tmp = pos1;
	pos1 = pos2;
	pos2 = tmp;
	return true;
}
void print_array(int* ar, int len)
{
	cout << endl << "Describing The Given Array" << endl;
	for (int i = 0; i < len; i++)
                cout << "_______" << "\t";
        cout << endl;
	for (int i = 0; i < len; i++)
                cout << " | " << i << " | " << "\t";
        cout << endl;
	for (int i = 0; i < len; i++)
                cout << " ( " << ar[i] << " ) " << "\t";
        cout<<endl;
	for (int i = 0; i < len; i++)
                cout << "-------" << "\t";
        getchar();
}

picture requires explanation

What does that "Example of insertion sort" show exactly? What do the x and y coordinates represent? Without this kind of explanation it isn't helpful at all! Fresheneesz (talk) 09:41, 5 December 2007 (UTC)

Removed claim about real-time apps

I removed this:

It can be seen as an advantage for some real-time applications that selection sort will perform identically regardless of the order of the array, while insertion sort's running time can vary considerably.

This seems silly. Not only is it false, since caches could disrupt the running time of selection sort; if it's truly important to make insertion sort as uniformly slow as selection sort, one could always add delay loops or useless array accesses. --Doradus (talk) 17:58, 5 February 2008 (UTC)

No argument from me. The runtime of selection sort is more predictable, but for real-time applications it suffices to determine a reasonable upper bound on runtime, which can be done by sorting a reversed list, and my expectation is that insertion sort is faster in the worst case than selection sort is in the best case. Dcoetzee 20:35, 6 February 2008 (UTC)

insertion sort psudocode

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void insertionSort1(int *A, int length) {
	int i, j, value; /* This is from the psudocode */
	for (i = 1; i < length-1; i++) {
		value = A[i];
		j = i - 1;
		while (j >= 0 && A[j] > value) {
			A[j + 1] = A[j];
			j = j-1;
		}
		A[j+1] = value;
	}
}

void insertionSort2(int *A, int length) {
	int i, j, value; /* Corrected psudocode */
	for (i = 1; i < length; i++) {
		value = A[i];
		j = i - 1;
		while (j >= 0 && A[j] > value) {
			A[j + 1] = A[j];
			j = j-1;
		}
		A[j+1] = value;
	}
}

int main() {
	int length = 10;
	int array1[length];
	int array2[length];
	int i;
	srand(time(NULL));
	printf("Original array:\n");
	for (i = 0; i < length; i++) {
		array1[i] = array2[i] = random() % (2 * length);
		printf("\tarray[%d]: %d\n", i, array1[i]);
	}
	insertionSort1(array1, length);
	insertionSort2(array2, length);
	printf("Output of insertion sort 1 (from psudocode):\n");
	for (i = 0; i < length; i++)
		printf("\tarray1[%d] = %d\n", i, array1[i]);
	printf("Output of insertion sort 2 (corrected psudocode):\n");
	for (i = 0; i < length; i++)
		printf("\tarray2[%d] = %d\n", i, array2[i]);
	return 0;
}

/* OUTPUT: 
Original array:
        array[0]: 1
        array[1]: 16
        array[2]: 19
        array[3]: 5
        array[4]: 12
        array[5]: 4
        array[6]: 17
        array[7]: 10
        array[8]: 11
        array[9]: 13
Output of insertion sort 1 (from psudocode):
        array1[0] = 1
        array1[1] = 4
        array1[2] = 5
        array1[3] = 10
        array1[4] = 11
        array1[5] = 12
        array1[6] = 16
        array1[7] = 17
        array1[8] = 19
        array1[9] = 13
Output of insertion sort 2 (corrected psudocode):
        array2[0] = 1
        array2[1] = 4
        array2[2] = 5
        array2[3] = 10
        array2[4] = 11
        array2[5] = 12
        array2[6] = 13
        array2[7] = 16
        array2[8] = 17
        array2[9] = 19
*/

I do understand that the psudocode is zero-indexed (despite the i = 1 in the loop), however if you look closely at the code, A[length-1] (the last element in the array) will never be touched, much less sorted. —Preceding unsigned comment added by Jordanbray (talk • contribs) 19:00, 16 February 2008 (UTC)

It looks to me like the original worked fine and the revision is broken. Please can you double-check? OoS (talk) 18:47, 17 February 2008 (UTC)

Yes, the revision is broken. On the final pass through the outer loop, i=length(A) followed by value=A[i] generates an array index out of bounds exception. Silly rabbit (talk) 19:29, 17 February 2008 (UTC)

I think Jordan does not understand that the pseudocode notation "for i = 1 to length(A)-1" includes length(A)-1. The problem is in how the pseudocode was translated into the C code above, not in the pseudocode itself. Silly rabbit (talk) 19:32, 17 February 2008 (UTC)

Pseudocode fix

As you will learn in very Computer Science class pseudocode is not intended to be implementable. Also expressions like "count++" or operators like "&&" are frowned upon because the may be ambigous between languages. — Preceding unsigned comment added by 78.55.242.110 (talk) 16:14, 5 February 2014 (UTC)

Implemented the pseudocode in Java today (Eclipse is my SDK). It does not sort the last index. Removing the -1 after array.length[A] (or length[A] if you prefer the pseudocode) sorts the last variable and does not throw an exception. I haven't traced the code yet to find out why, but I figured I'd fix the implementation on the article first. XreDuex (talk) 18:12, 13 March 2008 (UTC)

Please see the discussion of the preceding section. In the last loop, setting value = A[length(A)] will give an index out of bounds exception. It's likely that your Java implementation made the same error as the C implementation given above. I have reverted your erroneous correction to the pseudocode. silly rabbit (talk) 18:23, 13 March 2008 (UTC)

Instead of correcting a supposed "erroneous" error, you could try implementing it in Eclipse. No exception is thrown with or without the -1 after array.length, but with it the final index is not sorted. It also seems as if you don't understand which "-1" I am referring to (although my crappy wording in my original post probably didn't help). I am talking about the "-1" in the for loop's conditions.

public static void insSort(int[] a)
{
	for (int count = 1; count < a.length; count++)
	{
		int value = a[count];
		int temp = count-1;
		while (temp >= 0 && a[temp] > value)
		{
			a[temp + 1] = a[temp];
			temp = temp-1;
		}
		a[temp+1] = value;
	}
}

I also do not see how the discussion on the C implentation is relevant at all, as no error results. XreDuex (talk) 17:54, 14 March 2008 (UTC)

He's right - you did make the same error as the C program above. The upper bound in the pseudocode is inclusive, while the upper bound in your for loop is exclusive. This requires an adjustment of the loop bound by 1. I suppose the pseudocode could be clarified, but this is a minor detail that would distract from the topic at hand if given too much attention. Dcoetzee 00:31, 15 March 2008 (UTC)

Pseudocode error

The pseudocode example contains an indexing error!!

I'm pretty sure you cannot have a zero-based index run from 1 to N, and then attempt to get a value for a[i] - this element cannot EXIST! 12.27.253.143 (talk) 21:09, 29 July 2014 (UTC)

This is true. I have change the pseudocode so that i ranges from 1 to length(A)-1. 124.148.192.50 (talk) 03:06, 21 May 2016 (UTC)

Code block templates

Hi all. A while ago I began an experiment with a new method for discouraging incorrect good-faith changes to code and pseudocode called "code block templates" on the articles quicksort and binary search algorithm. So far there haven't been any incorrect new changes to those code block templates, but very few changes have been made, so I'd like to expand the scope of this experiment to see how effective it is. This is one of the articles I'm targeting for this second phase. Please let me know on my talk page if you have any questions or concerns. Thanks! Dcoetzee 21:37, 7 December 2008 (UTC)

The C++ code is broken. Try sorting a list of length 1. You will get index-out-of-bounds error. —Preceding unsigned comment added by 207.67.97.194 (talk) 13:30, 13 August 2009 (UTC)

Linked Lists and O(n log n)

In college I was taught to use insertion sort on Linked Lists, not on arrays. A static array does indeed require that you shift all the existing elements down in order to make room for the new inserted item. Using doubly linked lists does not require a shift to make room. The item is actually inserted into your growing sorted list. After all insertions are performed you delete the old list out of memory. This type of algorithm actually gives you a O(n log n) time. Before I came to this article, I was totally unaware that Insertion Sorts were ever used on arrays, as this seems hopelessly cumbersome to me. paros (talk) 07:09, 20 December 2008 (UTC)

To the contrary, it has similar performance on linked lists, because it still requires linear time to find the correct place in the list in which to insert each new item. This variant uses less writes, but the same number of reads and comparisons. You could build a binary tree on top of the linked list, but then you're talking about binary tree sort. Dcoetzee 07:26, 20 December 2008 (UTC)

An example to use?

Personally I've been confused on how the Insertion Sort works, and I found a website that explained it well with an example. Insertion Sort example

Here is the example used on the website:

5|7034261(0)
57|034261(0)
057|34261(2)
0357|4261(2)
03457|261(2)
023457|61(4)
0234567|1(1)
01234567|(6)

Avaviel (talk) 16:51, 18 March 2009 (UTC)

Pseudocode bug

10 Oct 2009: I think the for-loop in the pseudo-code is wrong: If the array is zero-based and the for-loop includes the top index (as stated above the pseudo code), the access to A[i] goes beyond the upper bound of the array in the last execution of the loop. The third line should be

for i := 1 to length[A]-1 do

4 Nov 2009: I agree with the above remark. —Preceding unsigned comment added by 193.32.3.83 (talk) 11:14, 4 November 2009 (UTC)

11 Nov 2009: Yes, the pseudo-code definitely needs fixing. —Preceding unsigned comment added by 89.132.46.212 (talk) 08:52, 11 November 2009 (UTC)

Replaced average running time claims with big O complexity

In the listing of the advantages of insertion sort, it says that the average running time is n²/4. I thought running time was measured in seconds, or have I missed anything? How does this notation better describe the behaviour of the algorithm than normal ordo (big O) notation? If this actually is the average number of comparisons of elements, or swaps or anything, I think the article should say that instead of using the somewhat misleading expression running time. --Kri (talk) 21:41, 28 November 2009 (UTC)

I agree - it most likely is referring here to comparisons, or comparisons plus exchanges, but we really need a proper reference for this. Dcoetzee 07:53, 29 November 2009 (UTC)

Absolutely. I've replaced this:

the average running time is n²/4, and the running time is linear in the best case

with this:

the best case (nearly sorted input) is O(n)

I've also changed the title of this talk section from "What does running time in this context mean?" to "Replaced average running time claims with big O complexity" Alex.mccarthy (talk) 18:22, 21 May 2010 (UTC)

Pseudocode problem

I have a conceptual problem with the pseudocode. Let me give some background first. This is a bit long, so please bear with me :-)

I need to use Insertion sort in VBScript. I initially expected to perform a non-trivial translation, of the pseudocode, into VBScript. However, I soon realized that the translation is quite trivial.

VBScript already has 0-based arrays, and endpoint-inclusive FOR loops. I had to change the pseudocode WHILE DO WEND, into a VBScript DO WHILE LOOP, but those two constructs have precisely the same semantics. The only other changes were trivial syntax changes such as := to =, and [] to ().

Here's the result:

SUB INSERTION_SORT (A)
dim i, j, value
    for i = 1 to ubound (A)
        value = A (i)
        j = i - 1
        DO while j >= 0 and A (j) > value
            A (j + 1) = A (j)
            j = j - 1
        LOOP
        A (j + 1) = value
    next
END SUB

This code dies immediately with an array bounds error. I initially thought that I'd copied it wrongly. However, the problem is in the WHILE expression 'j>=0 and A(j)>value'. VBScript does not "short circuit" boolean expressions when it evaluates them. So it always tries to evaluate A(j), even when j<0. This is an array bounds error, and VBScript quite rightly complains.

So what?

I fully understand that there is a difference between (a) the pseudocode describing an algorithym, and (b) an implementation of that pseudocde in some particular programming language. Clearly, a developer can introduce errors when producing (b) from (a). That's his fault, you can't blame (a) for that.

However, in this example, I'm effectively "running the pseudocode itself, directly in VBScript" - and it does not work! I can't see this as anything other-than a deficiency in the pseudocode. The VBScript implementation has exposed the fact that the pseudocode performs an illogical operation, namely, testing an array element that does not exist.

You could say: "But the pseudocode assumes short-circuit expression evaluation!". I'd reply: "Who says? How would any reader know that? Short-circuiting is an implementation language issue. Why is such an issue relied-on in the pseudocode? That's the tail, wagging the dog!"

The real problem

The pseudocode expresses the requirement wrongly. Logically, the actual requirement is to FIRST check if j<0, THEN, if and only if it isn't, check the value of A[j]. The pseudocode incorrectly suggests that you can do both checks at the same time. That is simply not correct from a logical viewpoint.

This exact problem is a very common programming problem. Different people solve it differently. Some people use flags. Some add extra tests inside the loop. And others use short-circuiting, if supported by the language in question. Some of those methods are language neutral, eg. flags and extra tests, while others are clearly language specific, eg. short-circuiting.

IMHO, language neutral pseudocode should not assume behaviour, like short-circuiting, that is clearly language specific.

In language neutral pseudocode, you can reasonably assume that 'FOR N=1 TO 10' will go from 1 to 10 inclusive. But in 'N=0 AND BLAH', you can't reasonably assume that BLAH is only referenced when N=0. That assumes short-circuiting!

What to do about this?

I believe that we should fix it. I can see four ways to do so.

(1) Create a new pseudocode construct that seperates the two tests in question. I've shown a possible way below. Sorry for the funky markup, I can't get proper markup working inside the PRE block, for some reason.

        while j >= 0 and A[j] > value do
              ^^DELETE^^
        begin
            A[j + 1] := A[j];
            j := j - 1;
        end until j < 0;
            ^^^^ADD^^^^

Pros: Does not rely on short circuiting. j is always >=0 on entry to the loop, so the reference to A[j] at the top will always work first time. Then the test at the bottom kills the loop as soon as j goes <0, before it returns to the top and tests A[j] again.

Cons: Probably not as clear as I originally thought. :-(

(2) Alternativey, change the loop as follows:

        while j >= 0 and A[j] > value do
              ^^DELETE^^
        begin
            A[j + 1] := A[j];
            j := j - 1;
            if j < 0 then exit while;  <<<< ADD <<<<
        end;

Pros: Easy to understand. ("The instant j goes <0, get outta there fast!")

Cons: The implementation language might not let you exit WHILE loops prematurely. But this is the sort of problem that you always face when implementing pseudocode. It's the implementor's problem to work out how to get the right result in the implementation language used.

(3) Use a short-circuit operator, eg. the && from C-style languages:

        while j >= 0  &&  A[j] > value do
                     ^^^^
        begin
            A[j + 1] := A[j];
            j := j - 1;
        end;

Pros: Clearly the simplest and most elegant solution - for readers who understand what && means.

Cons: There would be many readers who do not know what && means. It's a language specific operator, so I question whether it should be used in language-neutral pseudocode. If it were to be used, it should be hyperlinked directly to an explanation of what it does. If a reader didn't understand it, but couldn't be bothered to click it to see, that would be their problem.

(4) At the very least, we should add a note explaining all this. For example: "Note: the following test assumes that if j<0 then the loop will terminate immediately, without referencing A[j]. In languages where that doesn't occur, the test might fail with an array bounds error, when it tries to access A[-1]." But who wants all that guff in the middle of the pseudocode? Its very presence screams: "There is something wrong with this!"

Recommendations

(A) The existing pseudocode has an inappropriate assumption that expressions are short-circuited. I recommend that we fix this using one of the four solutions above.

(B) The referenced article: http://wiki.riteme.site/wiki/Pseudocode does not refer to short-circuiting. This is relevant to pseudocode, so it should be mentioned there.

What says the borg?

PS. I got a logon message (earlier today, perhaps from a different IP?) chastising me for vandalizing an article on a highschool somewhere. I work from public internet, that was nothing to do with me!

TC 203.122.223.121 (talk) 10:28, 18 January 2010 (UTC)

I'm surprised that no-one has a view on this. I'm away for a few days. If there are no comments (pro or con) when I return, I'll assume that no-one cares one way or the other, and will amend the pseudocode using option (2) above. TC 203.122.223.121 (talk) 03:48, 21 January 2010 (UTC)

Done. TC 203.122.223.121 (talk) 10:33, 24 January 2010 (UTC)

It's worth noting that some languages offer a clearly distinguishing, short-circuiting form of its boolean operators (this is usually true when the default form is not short-circuiting). For example, Ada has operators "and then" and "or else", while VB.NET adds "AndAlso"/"OrElse" - both with names clearly implying short-circuiting. That said, an explicit conditional is clearer still. On the other hand, "exit while" is itself a "BASICism", and is generally frowned upon in pseudocode, where boolean flags are preferred over goto-like constructs (which early loop termination is). Especially since pseudocode is written is pretty much untyped Pascal, which never had anything like "exit while". So I'll change it to use a boolean flag instead. -- int19h (talk) 17:39, 4 February 2010 (UTC)

Personally I feel that makes it much less clear. And it would have been good to discuss it here first: like I did! But whatever... 203.122.223.121 (talk) 04:14, 8 February 2010 (UTC)

Python Source Example

Changed the use of range() to xrange() for efficiency. The range() function creates a list with every element between 1 and N, xrange() only stores the current value and when called for the next value it increments the stored value and yields it. xrange() is the correct function to use here unless you like adding N to the cost of your implementation. Asdquefty (talk) 00:20, 11 April 2010 (UTC)

I've changed the Python example to be more similar to the Pascal code because I had to look at both to understand the algorithm, and the Python variable names are confusing. Asdquefty (talk) 00:38, 11 April 2010 (UTC)

Pascal is not Pseudocode

Pascal is not pseudocode, it includes too many language-specific statements that don't mean anything to you unless you're the pascal compiler. Do you see "do", "begin", and "end" shoved in random places when you read an instruction manual? Of course not, it doesn't make sense, and most people find instructions hard enough to read as it is. Asdquefty (talk) 00:43, 11 April 2010 (UTC)

More productively, one could refer to the page on Shell sort where there is a good example of how pseudocode should be written. Asdquefty (talk) 04:02, 12 April 2010 (UTC)

I agree - the existing code is confusing. It is also marked as pascal in the markup whereas the text says it is pseudocode. It can't be both. I would suggest:

insertionSort(array A)
begin
   for i := 1 to length[A]-1 do
   begin
       value := A[i];
       j := i - 1;
       while j >= 0 and A[j] > value do
       begin
           A[j + 1] := A[j];
           j := j - 1;
       end
       A[j + 1] := value;
   end;
end;

Danio (talk) 16:00, 4 May 2010 (UTC)

What you wrote above is still very similar to Pascal. While it is more concise, I think the begin/end statements distract the reader from the intent of the pseudocode. At the least, I feel it is redundant to have "do" and "begin" to denote the start of a loop block, pick one or the other. I suggest:

insertionSort(array A)
begin
   for i := 1 to length[A]-1
   do
       value := A[i];
       j := i - 1;
       while j >= 0 and A[j] > value
       do
           A[j + 1] := A[j];
           j := j - 1;
       end
       A[j + 1] := value;
   end;
end;

Personally, I find pseudocode much more readable when it is written to resemble Python, not Pascal, since Python code was designed to get to the point without redundant statements. Asdquefty (talk) 19:33, 4 May 2010 (UTC)

Yes I agree that the extra begin/do is redundant, but I didn't want to change things too much as there seems to be some kind of pascal v python religious war in the history of this page that I wanted to avoid. I think the most important thing is to go with one of these suggestions and get the algorithm clear as at the moment it is not a positive addition to the page. 82.24.215.72 (talk) 19:37, 4 May 2010 (UTC)

Animation is useless

In the "Best, worst, and average cases", the animation is utterly useless; it does not prove anything . It does not even clearly resemble any kind of sorting algorithm. I strongly suggest for it to be removed. 70.24.154.237 (talk) 00:59, 4 May 2010 (UTC)

It would be prudent for you to read the articles on some of the other algorithms and have a look at http://www.sorting-algorithms.com to see what animations of sorting looks like before you comment. As for proofs, if you are at all familiar with computer science or mathematics you should know animations are not an acceptable method of proof, the point of the animation is to provide a depiction of how the algorithm works. The animation is useful as a demonstration as many people are visual thinkers and it helps them to understand what is happening during an insertion sort. Certainly, the animation could be improved, but it is not useless.

I suggest you finish the sophomore year of a computer science or math degree before you comment on how you think elements of a very well thought-out Wikipedia are useless. Asdquefty (talk) 19:41, 4 May 2010 (UTC)

First of all, I really didn't appreciate you offending me like that. I suggestion was in good faith, and obviously you did not take it as such. That animation on the site you linked to (which I have seen before too) does accurately show what the algorithm is doing in each case, and in my opinion is tremendously better than the animation on this page. Even something like the selection sort animation here: http://wiki.riteme.site/wiki/File:Selection-Sort-Animation.gif would be better suited. 76.67.115.46 (talk) 15:04, 9 May 2010 (UTC)

I agree that the animation is indeed useless. The animation should show each comparison required for the element being inserted for it to be useful. e.g. the inserted value would slowly move from the right to the left, one element at a time until it reaches its place in the array, because this accurately reflects the actual processing time of the algorithm. As it is now, it looks like the element immediately jumps to the correct place in the array, and any input would run in O(n) time, which is obviously wrong. Two images, one showing a relatively sorted initial array, and one showing an input with reverse initial sorting would demonstrate the huge difference in runtime for these min and max inputs. 66.72.215.225 (talk) 18:55, 3 September 2010 (UTC)

List insertion sort code in C++ section

I replaced the Insertion sort#List insertion sort code in C++ section. It had a lot of syntax, little content, took n as an argument, the v were in an array rather than a list, and it created an aux link array for the sort. It was not a list sort.

A list insertion sort pops items off the input list and then splices them into a built up sorted list. When the input list is empty, the algorithm is done (with a possible NREVERSE).

I used a trailing pointer algorithm -- more efficient but less clear.

Glrx (talk) 22:17, 13 December 2011 (UTC)

A little bit beyond this algo

im not sucha great encoder , i just think there could b useful to use some O(k) mem to form a sorted buffer n help insert it

multidimensional ques might b some hybrid from arraies n sorting trees , i guess, the main goal would b using less mem to "control" their access

again, im a poor encoder, my strong point is solving relatevely heavy math problems these ones, sorting i mean, looks a bit noncreatively approached, after my judgement, i mean ok enough with Romanian boring time 4 now :-)

93.118.212.93 (talk) 18:36, 8 February 2013 (UTC)

basically insertion sort, but fast

1 million sorted in 1 second... compiled with qb64 enviroment

'wow !!! superinsertion ;))

DEFDBL A-Z

CONST n = 1000000
DIM a(1 TO n) AS INTEGER

FOR i = 1 TO n: a(i) = n - i: NEXT i

number = 0
FOR i = 1 TO n - 1
    i1 = i + 1 + number: IF i1 > n THEN i1 = n
    FOR j = i + 2 TO i1
        number = number - 1
        IF a(j) < a(i + 1) THEN
            tmin = a(j)
            a(j) = a(i + 1)
            a(i + 1) = tmin
        END IF
    NEXT j

    FOR j = i TO 1 STEP -1
        number = number + 1

        IF a(j) > a(j + 1) THEN
            t = a(j)
            a(j + 1) = a(j)
            a(j) = t
        ELSE
            GOTO nexti


        END IF
    NEXT j
    nexti:

NEXT i

errors = 0

FOR i = 1 TO n - 1
    IF a(i) > a(i + 1) THEN errors = errors + 1
NEXT i
PRINT errors

— Preceding unsigned comment added by 93.118.212.93 (talk) 15:25, 17 February 2013 (UTC)

I'm not sure what that is, but it's not an "insertion" sort. — Arthur Rubin (talk) 16:01, 17 February 2013 (UTC)

again, abt algos that r inspired from insertion sort :)

this (new) idea works recursevely and, in order to offer room for a linear multiinsertion (at least in some hypotetical terms), sorts b4 the lower half of the curently remaining amount to b inserted, idea being that we got (all the) conditions to inset this half of remaining amount to b inseted, sorted also in O(N). im sorry to tell u that but idk if its really working, nor that abt its O() n neither if its also discovered, in case its working. im just following some of my own preocupation in searching for appealing paradigms :) Florin Matei, Romania 93.118.212.93 (talk) 12:37, 15 April 2013 (UTC)

Pseudocode Results in Descending Order

While the pseudocode indeed sorts the array, it does so in descending order. This does not seem like the expected result, since all of the surrounding examples --- the diagrams and the animation --- demonstrate ascending sorts.

To rectify, the third line should employ less-than for the array element comparison: while j > 0 and A[j-1] < A[j] .

Also, while minor, I think the fourth line would read better with the array elements flipped: swap A[j-1] and A[j]. It has better visual symmetry with the preceding line.

Njuk-njuk (talk) 02:35, 7 August 2015 (UTC)

I was wondering if anyone knew a bit of history behind the Insertion Sort algorithm. Hence, where it came from, when it was first published, etc. If anyone has some good resources I would be very glad and thankful if they shared them. Thanks! — Preceding unsigned comment added by Chromechris (talk • contribs) 18:35, 16 March 2017 (UTC)

pseudo code for loop

The for loops in the first two pseudo code examples don't make it clear what the terminating value is: with for i = 1 to length(A), it isn't clear if the last value for i is length(A)-1 or length(A). I'm not aware of a programming language that uses the examples version of for loops. Fortran: do i = 0, n is inclusive, the last value for i is n. C, C++, Java, make it clear using a specific terminator condition: for(i = 1; i < n; i = i + 1), the last value for i is n-1. Python relies on functions in it's for statements like for i in range(0,n), where range() is not part of the for loop but a function that generates a list (array) of numbers 0 to n-1, or for i in xrange(0,n), where xrange() generates the indices 0 to n-1 one at a time. I suggest using C / C++ / Java style syntax, or separating the for loop into 4 statements: i ← 1, while(i < length(A)), ... , i ← i + 1, end while . Rcgldr (talk) 19:32, 15 July 2017 (UTC)

Pseudocode for a quicksort optimization using insertion sort

I have removed the quicksort pseudocode in the section "Relation to other sorting algorithms." Not only do I believe that is better placed in the main article, but that particular variant of the optimization isn't widely used anymore anyway (as described in the main article, section 2.3.3 "Optimizations", third bullet point). Derek M (talk) 01:44, 17 January 2018 (UTC)

C three-line implementation not verifiable?

The article uses an example of a 3 LOC C implementation to demonstrate the algorithms simplicity. I have obtained a digital copy of a book with a matching name and author, but the contents seem to differ and the description and cover seem to refer to a completely different book. In any case, it seems appropriate to remove. 109.43.113.6 (talk) 18:42, 24 December 2021 (UTC)

Google books shows that page 116 of the cited book has a three-line insertion sort. You may not have the same edition of the book. StarryGrandma (talk) 20:13, 26 December 2021 (UTC)

Insertion sort

Nothing 2409:4073:5:4DDA:576D:5CCC:FB34:20FD (talk) 07:01, 1 July 2022 (UTC)

Can you elaborate a bit? --CiaPan (talk) 10:31, 1 July 2022 (UTC)

"←" Symbol in Pseudocode Examples

Using "←" as a replacement for "=" is harder to understand, and I don't see a reason for it. Noice65535 (talk) 21:56, 29 July 2023 (UTC)

While Loop?

Is there any reason that a while loop is used instead of a for loop? For example, if one were to implement it, it'd most likely look something like

void sort (float A[], int n) {
    float temp;
    for (unsigned int i = 1; i < n; i++) {
        for (unsigned int j = i; j > 0 && A[j] < a[j - 1];) {
            temp = a[j];
            a[j] = a[--j]; // Also decrements j.
            a[j] = temp;
        }
    }
}

where n is the length of the array. They would (hopefully) only use a while loop when necessary. Is there a specific reason that while loops are used?

Billnyethefrenchfry (talk) 23:59, 15 August 2023 (UTC)

Early pseudo code didn't use for loops, so it's common / traditional to use while loops. MrOllie (talk) 00:10, 16 August 2023 (UTC)

What do you mean by "early pseudocode"? Anything that I've seen written uses for loops in this case. Even if early examples of pseudocode didn't include for loops, we aren't writing early examples of pseudocode.
Looking at the user that probably prompted the change's comment, they note that FORTRAN (and, in fact, most BASIC-like languages) use for loops like this:

do I = 0, n - 1
    ! ...
end do

Even if we don't want the weird FORTRAN do statement, and can't write C-like loops, we could still write it similar to a language like VBS:

Dim I
For I = 0 To n - 1
    ' ...
Next

This reduces the clutter of the while loop while also being similar to an actual language. If it could be confusing to some people who didn't read the piece of text directly below the code snippet, a comment could be added. In any case, a while loop is not needed.
From my understanding, pseudocode is meant to be used as a skeleton to base actual code off of, and is more useful when it resembles the code that will be based off it.
Billnyethefrenchfry (talk) 03:29, 4 September 2023 (UTC)

Pseudocode is meant to be a human readable explanation of an algorithm, not a 'skeleton to base actual code off of'. It follows certain conventions (which vary a bit from author to author but are mostly consistent). We should not be arbitrarily adopting syntax peculiar to one language or another. Wikipedia in general is meant to educate newcomers to the topic, not to be a repository of code for programmers to cut and paste. MrOllie (talk) 03:50, 4 September 2023 (UTC)

That is a fair point, and I retract my statement of it being a "skeleton". However, a for-loop is (at least for me) more readable than a while loop. Rather than one having to piece together that it iterates over the whole array, it just tells you "loop through the indexes of the array". Billnyethefrenchfry (talk) 16:53, 4 September 2023 (UTC)

Simple for loops are arguably more readable, sure. But in this case one of the loops requires a compound conditional: while j >= 0 and A[j] > x. That does not amend itself to a for loop construction. And it is simpler for a newcomer to understand only one type of loop construction. MrOllie (talk) 17:08, 4 September 2023 (UTC)

If one were to pronounce "for I from 0 to upper bound of A, do a thing", it would be immediately intuitive that, for "I" from 0 to the upper bound of A, a thing would be done. The reason keywords have their names is so that they are simple for someone learning the language to grasp.

I agree with you that the compound conditional in the inner loop is much harder to represent than the outer loop of "for I from x to y", but there is no reason that we shouldn't use the simplest representation ("For I From 1 To length(A) - 1 ... Loop" or "For I From 1 To UBound(A) ... Loop") for the outer loop.

Billnyethefrenchfry (talk) 12:17, 3 October 2023 (UTC)

Sure, there is a reason. To repeat it: it is simpler for a newcomer to understand only one type of loop construction MrOllie (talk) 12:24, 3 October 2023 (UTC)

The example animation is flawed

If feel like nit picking but it just looked like there is something wrong with the animation, and I have to comment for correctness sake ;-).

It (the one with blue background and orange bars - i.e. File:Insertion_sort.gif) does work as in a demonstration on what insertion sort looks like. However, in the beginning a value appears which is not in the original unsorted array at all. The two "same values" from the beginning are not there during the sort, so a value is lost, and the very last value is also lost and just disappears - it is not there anymore when the sort finishes. However it looks like it is sorting correctly otherwise during the animation.

The plausible explanation I can come up with is simple - the example is missing the first (initial state) frame and the last frame! =). Adding an initial state where there are no two same values and one last write (write the stored value) everything lines up.

This is besides the point of an example / demonstration, but those who are keen on details might get confused on what is going on. Viileeditor (talk) 08:29, 26 September 2023 (UTC)

The fact is that it's incorrect, and the fact that there is an inconsistency with the first frame and first element of the list are enough to justify removal I think. There is no need to add a disclaimer about nit-picking, since the algorithms and all examples of this technical topic should be 100% correct. cperk (talk) 23:31, 14 October 2023 (UTC)

Recursive implementation?

What is the purpose of having the recursive implementation?

• Special:Contributions/87.19.154.159 (January 2017)
• Special:Diff/923556769 (October 2019)

Apart from not being cited to any source and looking like a boast of its author, proud of having understood recursion, it also does not make the article any better. The recursive approach is not simpler, not shorter and not faster than the iterative one, and it requires unacceptable amount of additional memory in the stack space. There are many ways to implement the algorithm worse than the original, but IMVHO popularizing them is not a mission of Wikipedia... --CiaPan (talk) 08:38, 29 December 2023 (UTC)