Home > Articles, Data Structures & Algorithms > Implementation of insertion sort algorithm for single linked lists.

Implementation of insertion sort algorithm for single linked lists.

The following program generates N random integers between 0 and 999, creates a linked list inserting a number in each node and then rearranges the nodes of the list so that the numbers appear sorted when we go through the list. For the sorting, it maintains two lists: one input list (not sorted) and one output list (sorted). In each iteration of the loop, it removes a node from the input list and enters it in the appropriate position in the output list. The code is simplified by using head nodes for each list, which contains links to the first node lists. Also, both lists (input and output) are printed.

You should know that the implementation of the algorithm does not take into account issues of data input validation or proper management of dynamic memory (e.g. avoiding memory leaks) because it is only necessary to highlight the logic of the algorithm.

#include <iostream>
#include <iomanip>
#include <cstdlib>
using namespace std;

struct node {
  int item; node * next;

  node (int x, node * t) {
    item = x; next = t;
  }
};

typedef node * plink;

int
main () {
  const int N = 20;

  srand (time (NULL));

  node heada (0, 0); plink a = &heada, t = a;
  for (int i = 0; i < N; i++)
    t = (t->next = new node (rand () % 1000, 0));

  cout << "Initial Sequence:" << endl;

  t = a->next;
  while (t != 0) {
    cout << setw (5) << t->item << right << endl;
    t = t->next;
  }

  node headb (0, 0); plink u, x, b = &headb;
  for (t = a->next; t != 0; t = u) {
    u = t->next;

    for (x = b; x->next != 0; x = x->next)
      if (x->next->item > t->item)
        break;

    t->next = x->next; x->next = t;
  }

  cout << "Sorted Sequence:" << endl;

  t = b->next;
  while (t != 0) {
    cout << setw (5) << t->item << right << endl;
    t = t->next;
  }

  return 0;
}
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: