# Cleopatra Forum

Cleopatra Forum

You are not logged in.

## #1 2020-09-13 19:37:37

LoreneColo
Member
From: Denmark, Arre
Registered: 2020-09-13
Posts: 1

### Click to share on Facebook (Opens in new window)

##### Implementation of insertion sort algorithm for single linked lists

Filed under:.

2010                 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 name space  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; }           Rate this:.
Click to share on Facebook (Opens in new window).

##### Click to email this to a friend (Opens in new window)

Like this:.
Related.
Tags: , insertion sort,     .

Email  (Address never made public)                 Name                 Website                                                            You are commenting using your  WordPress.com  account.
( Log Out /     )                                                             You are commenting using your Google account.
( Log Out /     )                                                             You are commenting using your Twitter account.
( Log Out /     )                                                             You are commenting using  your Facebook  account.
( Log Out /     )                             Cancel   Connecting to %s             Notify me of new comments via email.
Notify me of new posts via email.

##### Implementation of basic string processing functions in C

».
(79).
(21).
(15).
(26).
(4).
(7).
(55).
(24).
(4).
(16).
(14).
(4).
(7).
(10).
(78).
(11).
(9).
(1).
October 2010      M  T  W  T  F  S  S           123      45678910      11121314151617      18192021222324      25262728293031        « Sep     Nov ».
(2).
(4).
(1).
(1).
(2).
(1).
(1).
(1).
(2).
(1).
(9).
(1).
(8).
(1).
(1).
(2).
(4).
(7).
(1).
(1).
(1).
(8).
(12).
(1).
(2).
(1).
(2).
(1).
(2).
(1).
(1).
(4).
(20).
(13).
(5).
(2).
(10).
(13).
(10).
(10).
(20).
287,006 hits.