Back to General and Gameplay Programming

Insertion Sort

Published September 13, 1999 by Yin-So Chen, posted by Myopic Rhino

Do you see issues with this article? Let us know.

The basic step in this algorithm is to insert a data set into a sequence of ordered (increasing) data sets in such way that the resulting sequence of data set is also ordered. Thus if the data set D is inserted in position i, then the data sets in position j less than i will be less than D, and the data sets in position j greater than i will be greater than D.

Since we will be manipulating the data sets in an array, we will have to compare all of the values of the data and move them once the ordering relationship between two values are determined. Below is the pseudo-code of the algorithm.

[font="Verdana, Tahoma, Arial"][size="2"]

Insertion Sort (Sorting the array A[size])



    For index i = 2 up to i = size

    {

        While before reach the end of cells

        {

            Compare the element Awith the preceding element (A[i - 1]).

            If the element is smaller than the preceding one (A < A[i - 1]),

                swap them;

            else, go to the next element.

        }

    }

[font="Courier New, fixedsys"][size="2"][color="#000088"] [/color][/font][/font]

0 Likes 0 Comments

Comments

Nobody has left a comment. You can be the first!

You must log in to join the conversation.

Don't have a GameDev.net account? Sign up!

Insertion sort can run in O (n) in the best case, however its worst case is O (n[sup]2[/sup]). It can, however, be used to optimize the quicksort, and is therefore worth learning.

Insertion Sort

Comments

Recommended Tutorials

Other Tutorials by Myopic Rhino

Insertion Sort

Comments

Recommended Tutorials

Other Tutorials by Myopic Rhino

Reticulating splines