Thread: Insertion Sort Help

  1. #1
    Registered User
    Join Date
    Dec 2009
    Posts
    1

    Insertion Sort Help

    Ok so I have to write insertion sort but every time I compile it and run it and enter numbers to sort i get some crazy errors.
    here is an example, I entered :2 3 4 1 5 and I got this output 2 -2.70464e+303 1 3 4
    Im so confused on what to do

    Here is my code so far:
    any advice/help would greatly be appreciated
    Code:
      #include<iostream>
    using namespace std;
    
    #define MAX_LIST_LEN  100
    
    int main(void){   
    
       int    n,                    // list length
              j,                    // loop control
              L,                    // index of rightmost element in unsorted section
          count;                    // Count comparisons
       double temp,                 // temporary storage
              list[MAX_LIST_LEN];   // array to be sorted
    
       // Get values for n and list.
       cout << "Enter list length (must be less than or equal to "
            << MAX_LIST_LEN << "): ";
       cin  >> n;
       cout << "Enter " << n << " numbers:" << endl;
       for(j=0; j<n; j++){
          cin >> list[j];
       }
      
       // perform InsertionSort algorithm on list
    
       L=2;
       while(L<=n)
    {
           j=L;
           while(j>=2 && list[j]<list[j-1]){
                temp = list[j];
                list[j]=list[j-1];
                list[j-1]=temp;
                j--;
    }
           L = L+1;
    }
       
       // Print out sorted list.
       for(j=0; j<n; j++){
          cout << list[j] << " ";   
       }
       cout << endl;
       
       return(0);
    }

  2. #2
    train spotter
    Join Date
    Aug 2001
    Location
    near a computer
    Posts
    3,868
    Code:
    while(L<=n)
    {
           j=L;
           while(j>=2 && list[j]<list[j-1])
          {
                temp = list[j];
                list[j]=list[j-1];
                list[j-1]=temp;
                j--;
          }
           L = L+1;
    }
    In the sorting loop what happens when L == n? (in this case 5)

    Does it use an element of the array you have not received input for? (and is full of random data because you did not init your variables.)
    "Man alone suffers so excruciatingly in the world that he was compelled to invent laughter."
    Friedrich Nietzsche

    "I spent a lot of my money on booze, birds and fast cars......the rest I squandered."
    George Best

    "If you are going through hell....keep going."
    Winston Churchill

  3. #3
    Registered User
    Join Date
    Nov 2009
    Posts
    82
    A good way to do some basic debugging is to add cout in to the loop and observe yourself what is being compared and read. If you're list is not holding the data you entered it might be a problem with cin >>, clearing it? Just a guess...

    Add a small loop to echo out the list your sorting, before the while loop, did the input save in to the array correctly?

    Code:
    for(j=0; j<n; j++){
          cout << list[j];
    }
    If so continue using cout to get output as the algorithm progresses. You can do some more convenient debugging if you're using Visual C++ or what ever, just read up on it for your IDE/tools.
    Last edited by since; 12-04-2009 at 11:29 AM.

  4. #4
    train spotter
    Join Date
    Aug 2001
    Location
    near a computer
    Posts
    3,868
    Quote Originally Posted by since View Post
    If you're list is not holding the data you entered it might be a problem with cin >>, clearing it? Just a guess....
    The problem is the use of '>=' in the sortings while loop (as it allows the array to go OOB).

    In this case the array has elements 0-4 (for a total of 5) but this logic error in the sorting loop allows the 6th element of the array to be sorted (index of 5).

    The 6th element contains a random value (because the variables are not initialised) which is then sorted into the inputed values.

    That is not all that is wrong but it will move the OP forward.
    "Man alone suffers so excruciatingly in the world that he was compelled to invent laughter."
    Friedrich Nietzsche

    "I spent a lot of my money on booze, birds and fast cars......the rest I squandered."
    George Best

    "If you are going through hell....keep going."
    Winston Churchill

  5. #5
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Why j>=2 ?
    Don't items 0 and 1 also deserve to be swapped if necessary?
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  6. #6
    train spotter
    Join Date
    Aug 2001
    Location
    near a computer
    Posts
    3,868
    Quote Originally Posted by iMalc View Post
    Why j>=2 ?
    Don't items 0 and 1 also deserve to be swapped if necessary?
    The OP appears to think arrays in C/C++ are one based.

    By starting at index 2 they think they are accessing/sorting the first elements of the array (with j==2 and comparing with [j-1]) on the loops first run (which would be correct in VB for example).
    "Man alone suffers so excruciatingly in the world that he was compelled to invent laughter."
    Friedrich Nietzsche

    "I spent a lot of my money on booze, birds and fast cars......the rest I squandered."
    George Best

    "If you are going through hell....keep going."
    Winston Churchill

  7. #7
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Quote Originally Posted by novacain View Post
    The OP appears to think arrays in C/C++ are one based.
    One might think that, but both for loops are correct in their indexing.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  8. #8
    train spotter
    Join Date
    Aug 2001
    Location
    near a computer
    Posts
    3,868
    Quote Originally Posted by iMalc View Post
    One might think that, but both for loops are correct in their indexing.
    Good point.

    Which makes me wonder where the OP got the sorting code from.....
    "Man alone suffers so excruciatingly in the world that he was compelled to invent laughter."
    Friedrich Nietzsche

    "I spent a lot of my money on booze, birds and fast cars......the rest I squandered."
    George Best

    "If you are going through hell....keep going."
    Winston Churchill

  9. #9
    Registered User slingerland3g's Avatar
    Join Date
    Jan 2008
    Location
    Seattle
    Posts
    603
    Odd code nevertheless, the issue is that the OP has hard coded L =2. Then sets j = L. Then they call

    Code:
    ...
    
       j--; /*potential problem and will lead to list[j-1] going to a negative index */

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 5
    Last Post: 08-02-2008, 06:23 AM
  2. Straight Insertion Sort function problem
    By StaticKyle in forum C++ Programming
    Replies: 6
    Last Post: 05-12-2008, 04:03 AM
  3. Insertion Sort on Array of Structs
    By n0r3gr3tz in forum C Programming
    Replies: 3
    Last Post: 04-01-2008, 08:28 AM
  4. Insertion Sort Problem
    By silicon in forum C++ Programming
    Replies: 1
    Last Post: 05-08-2005, 12:30 PM
  5. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM