Insertion sort question

This is a discussion on Insertion sort question within the C++ Programming forums, part of the General Programming Boards category; Hey all, I'm doing an assignment, in which I'm reading the contents of a binary file, into a linked-list, which ...

  1. #1
    Registered User
    Join Date
    Aug 2002
    Posts
    55

    Insertion sort question

    Hey all,

    I'm doing an assignment, in which I'm reading the contents of a binary file, into a linked-list, which I then need to sort by customer code. At first, I was going to use a bubble-sort on the linked list, but after searching this board, it seemed that an insertion sort would be more appropriate.

    However, I think I'm right in saying that I'd need a doubly-linked list to do this? I've only ever used a singly-linked list in the form of a stack, so I'm a little in the dark still. I think this is the correct theory though.

    Just wondered if that was right or not and if I need to go and learn how to use a *prev pointer.

    Thanks,

    John.

  2. #2
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >However, I think I'm right in saying that I'd need a doubly-linked list to do this?
    Insertion sort doesn't require a doubly linked list, but you will find that building a new list as you break down the old one is the easiest solution:
    Code:
    struct node *sort_list ( struct node *in )
    {
      struct node out = {0,0};
      struct node *i, *step, *next;
    
      for ( step = in; step != 0; step = next ) {
        next = step->next;
    
        for ( i = &out; i->next != 0; i = i->next ) {
          if ( i->next->data > step->data )
            break;
        }
    
        step->next = i->next;
        i->next = step;
      }
    
      return out.next;
    }
    -Prelude
    My best code is written with the delete key.

  3. #3
    Registered User
    Join Date
    Aug 2002
    Posts
    55
    Thanks Prelude.

    John.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. I need help to compile this code...
    By wise_ron in forum C Programming
    Replies: 17
    Last Post: 05-07-2006, 01:22 PM
  2. Sorting
    By vasanth in forum A Brief History of Cprogramming.com
    Replies: 12
    Last Post: 11-10-2003, 05:21 PM
  3. Radix Sort question
    By ripper079 in forum C++ Programming
    Replies: 5
    Last Post: 01-06-2003, 06:58 AM
  4. question about Quick Sort
    By Liberty4all in forum C++ Programming
    Replies: 8
    Last Post: 11-23-2002, 10:38 AM
  5. recursive insertion sort.
    By Alien_Freak in forum C++ Programming
    Replies: 3
    Last Post: 03-23-2002, 01:31 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21