CMPT 130 Lab 8 – Insertion Sort

 

As part of our current focus on algorithm efficiency we are going to look a simple sorting algorithm called insertion sort. This lab mostly consists of you running a program that I'm going to give you and thinking about the results.

 

This lab will be better if you work in groups of two or three so that you can discuss the results.

 

Labs are assessed, so make sure that the TA has seen, and marked, your finished work before you leave the lab.

 

Insertion Sort

Below is a completed program. Copy and paste it into your text editor and compile and run it. Take a look at the output and satisfy yourself that all three of the arrays are sorted.

 

#include <iostream>

#include <iomanip>

#include <cstdlib>

#include <time.h>

using namespace std;

 

void printArray(int arr[], int n);

void insertionSort(int arr[], int size);

int* getSequence(int n, int start, int gap);

int* getRandomArray(int n);

 

int main()

{

       srand(time(0));

 

int n = 10;

       cout << endl << "n = " << n << endl << "------------";

 

int* sortedArr = getSequence(n, 0, 1);

       cout << endl << "Sorted input array: ";

       printArray(sortedArr, n);

       cout << endl << "Sort with insertion sort: ";

       insertionSort(sortedArr, n);

       printArray(sortedArr, n);

 

       int* reversedArr = getSequence(n, n-1, -1);

       cout << endl << endl << "Reversed input array: ";

       printArray(reversedArr, n);

       cout << endl << "Sort with insertion sort: ";

       insertionSort(reversedArr, n);

       printArray(reversedArr, n);

 

       int* randomArr = getRandomArray(n);

       cout << endl << endl << "Random input array: ";

       printArray(randomArr, n);

       cout << endl << "Sort with insertion sort: ";

       insertionSort(randomArr, n);

       printArray(randomArr, n);

 

       delete[] sortedArr;

       delete[] reversedArr;

       delete[] randomArr;

       return 0;

}

 

// Function to print an array on one line like this:

//    {2,5,3,9,7}

//    Warning - only useful for small arrays!

// PARAM: arr - array to be printed, n - size of arr

// POST: contents of arr are printed to standard output

void printArray(int arr[], int n)

{

       cout << "{";

       for (int i = 0; i < n; ++i) {

              cout << arr[i];

              if (i != n - 1) {

                     cout << ",";

              }

       }

       cout << "}";

}

 

// Sorts an array using the insertion sort algorithm

// PARAM: arr - array to be sorted, n - size of arr

// POST: arr is sorted

void insertionSort(int arr[], int size)

{

       for (int i = 1; i < size; ++i) {

              int temp = arr[i];

              int pos = i;

              // Shuffle up all sorted items > arr[i]

              while (pos > 0 && arr[pos - 1] > temp) {

                     arr[pos] = arr[pos -1];

                     pos--;

              } //while

              // Insert the current item

              arr[pos] = temp;

       }

}

 

// Returns a pointer to a sequence of integers with a linear progression

// PARAM: n - number of values in sequence

//        start - first value in sequence

//        gap between values in sequence

// POST: returns array with n values starting with start, separated by gap

int* getSequence(int n, int start, int gap)

{

       int next = start;

       int* result = new int[n];

       for (int i = 0; i < n; ++i) {

              result[i] = next;

              next += gap;

       }

       return result;

}

 

// Returns a pointer to a an array of random integers

// PARAM: n - number of values in array

// POST: returns array with n random values from 0 to n

int* getRandomArray(int n)

{

       int* result = new int[n];

       for (int i = 0; i < n; ++i) {

              result[i] = rand() % n;

       }

       return result;

}

 

Calculate Insertion Sort Work

We are now going to make the insertion algorithm return an estimate of the amount of work it is doing, much like we did in class with some other algorithms, including selection Sort. Just to remind you, selection sort performs approximately n2 (where n is the size of the array to be sorted) operations regardless of the organization of the input – that is, it takes just as long to sort a mostly (or entirely) sorted array as it does to sort an array where the values are placed randomly. You are going to assess the efficiency of insertion sort for different organizations of input.

 

Here is the amended version of the insertion sort algorithm. You will need to make a corresponding change to the prototype.

 

long long insertionSort(int arr[], int size)

{

     long long work = 0;

 

     for (int i = 1; i < size; ++i) {

           int temp = arr[i];

           int pos = i;

 

           // Shuffle up all sorted items > arr[i]

           work++;

           while (pos > 0 && arr[pos - 1] > temp) {

                work++;

                arr[pos] = arr[pos -1];

                pos--;

           } //while

           // Insert the current item

           arr[pos] = temp;

     }

     return work;

}

 

Take the time to think about how insertion sort works by reviewing the code – please do this! As an incentive, it's conceivable I might ask you to explain how both insertion sort and selection sort work on the final exam.

 

Insertion sort is another simple sorting algorithm that divides the array into a sorted and unsorted part. It repeatedly takes the first unsorted element and places it in the correct order in the sorted part of the array. If you play cards, this is very similar to the way that many people arrange a hand of cards. Take a look at a couple of demos of the algorithm:

§  Hungarian Folk Dance Insertion Sort – you can get the basic idea from this, though it is pretty irritating so feel free to not watch the entire thing …

§  Insertion Sort with Cards – no dancing, but very clear, and less than two minutes long.

 

Change the Main Function

Now we will re-write the main function to print the estimate of how much work insertion sort is doing instead of printing the sorted arrays. Here is the new main function.

 

int main()

{

srand(time(0));

 

int n = 10;

int* sortedArr = getSequence(n, 0, 1);

 

cout << endl << "Work estimate on sorted array:   " << setw(12) << insertionSort(sortedArr, n) << endl;

int* reversedArr = getSequence(n, n, -1);

cout << "Work estimate on reversed array: " << setw(12) << insertionSort(reversedArr, n) << endl;

nt* randomArr = getRandomArray(n);

cout << "Work estimate on random array:   " << setw(12) << insertionSort(randomArr, n) << endl;

 

delete[] sortedArr;

delete[] reversedArr;

delete[] randomArr;

return 0;

}

 

Run It Repeatedly

Now run the main program and write down the results on a piece of paper. Run it another four times but multiply n by 10 each time you do it. When you've finished you should have completed the following table.

 

n

Sorted

Reversed

Random

10

 

 

 

100

 

 

 

1,000

 

 

 

10,000

 

 

 

100,000

 

 

 

 

Think About It

Try to come up with an approximate formula for how much work insertion sort is doing based on the size and organization of its input. If you've been working in a team discuss this with your team members. If you haven't been working in a team discuss it with the person sitting next to you.

 

Assessment

1 mark for showing the TA your completed table and briefly discussing your conclusions.

 

 

CMPT 130 Home

 

John Edgar (johnwill@sfu.ca)