Insertion Sort


Program Listing

InsertionSort.cpp

/************************************************************************
*                                                                       *
*   Program:    InsertionSort                                           *
*                                                                       *
*   Purpose:    To sort a list of numbers into ascending order          *
*                                                                       *
************************************************************************/

//  Header files

#include <iostream>
#include <string>

using namespace std;

//  Function prototypes

void InsertionSort(int list[], int size);

/************************************************************************
*                                                                       *
*   Function:   main                                                    *
*                                                                       *
*   Purpose:    To sort a list of numbers into ascending order          *
*                                                                       *
************************************************************************/

int main() {

//  Read a list of numbers

    const int maxSize = 100;
    int list[maxSize];
    
    cout << "Enter the size of the list (max of " << maxSize << "):  " << flush;
    int size;
    cin >> size;
    
    cout << "Enter a list of " << size << " integers:" << endl;
    
    for (int i = 0; i < size; i++)
        cin >> list[i];
    
//  Sort the list

    InsertionSort(list, size);
    
//  Print the sorted list

    cout << endl << "The sorted list:" << endl;
    for (int i = 0; i < size; i++)
        cout << list[i] << endl;
        
    return 0;
}
    
/************************************************************************
*                                                                       *
*   Function:   InsertionSort                                           *
*                                                                       *
*   Purpose:    To sort a list of numbers using the insertion sort      *
*               algorithm                                               *
*                                                                       *
************************************************************************/

void InsertionSort(int list[], int size) {

//  For each position i > 0 in the list

    for (int i = 1; i < size; i++) {
    
    //  Insert the member in position i into the sorted sublist
    
        int item = list[i];
        int pos;
        for (pos = i - 1; pos >= 0 && list[pos] > item; pos--)
            list[pos + 1] = list[pos];
        list[pos + 1] = item;
    }

    return;
}

Sample Run

Enter the size of the list (max of 100):  10
Enter a list of 10 integers:
60 30 40 55 75 80 25 45 35 65

The sorted list:
25
30
35
40
45
55
60
65
75
80



Return to Lectures page


e-mail me at robbk@hsc.edu

This page was last modified on Tue Dec 7 16:04:58 1999 .

URL: http://people.hsc.edu/faculty-staff/robbk/Coms261/Examples/InsertionSort.html

Return to Coms 261 home page