Cleopatra Forum

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:.

— Leave a comment        October 4

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:.
Share this:.
Click to share on Facebook (Opens in new window).

Click to share on LinkedIn (Opens in new window)

Click to share on Twitter (Opens in new window)

Click to print (Opens in new window)

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

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

Comments RSS feed                    Leave a Reply Cancel reply

Enter  your comment  here.
Fill in your details below or click an icon to  log in :.
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 closest point calculation

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.
Send to Email Address          Your Name        Your Email Address                               Cancel       Post was not sent - check your email addresses.
Email check failed.

Please try again          Sorry

your blog cannot share posts by email.
%d  bloggers like this:.