InsertionSort Algorithm, Whats Wrong with my Code?

Question

I'm trying out a InsertSort Algorithm for an input of strings stored in a vector.

What I do is to input some strings into the vector, Then i use insertionsort to sort the vectors.

But I'm not sure why does it not work! Could anyone point me to the right direction?

#include <iostream>
#include <cstring>
#include <vector>
#include <cstdlib>
using namespace std;

int main (){
    vector <string> names; //vector to store
    string input; //input is the variable of strings

    cout<<"Input a list of names \n";
    cout<<"To end the list type 'END'" <<endl;

    while (true){
        getline(cin, input);

        if (input =="END")
        break;

        names.push_back(input); //push into vector names
    }


  //my insertsort starts here
  string temp;
  int i;
  for (int j = 1; j < names.size(); j++){
        i = j - 1;        

        while ((i>0) && (names[i]>names[j]) ) {

            names[i+1] = names[i];

            i=i-1;         
                                                 }

        names[i+1] = names[j];

    }



    for (unsigned int i = 0; i<names.size (); i++)
    cout<<names[i]<<endl;
    cout<<endl;
    system("pause");
}

Thanks a bunch

EDIT: I will be inputing strings for example I will type:

Peter Apple Rabbit

And my desired output is, in alphabatical order,:

Apple Peter Rabbit

At the moment with the example input, I get: Peter Apple Rabbit

EDIT 3:

My insert sort now looks like this:

 string temp;
  int i;
  for (int j = 1; j < names.size(); j++){
        i = j - 1;        
        temp = names[j];

 while ((i>=0) && (names[i]>names[j]) ) {
    names[i+1] = names[i];
    i=i-1;                                                  
                                        }

 names[i+1] = temp;
    }

define "does not work". what input are you using and what output are you geting ? — Oren
– Oren, Commented Apr 7, 2013 at 15:22

taocp · Accepted Answer · 2013-04-07 17:54:42Z

2

You missed one point:

 //You have to remember names[j] before while loop
 //the variable temp is never used
 temp = names[j];
 while ((i>=0) && (names[i]>temp) ) {
    names[i+1] = names[i];
    i=i-1;                                                  
 }
 names[i+1] = temp;
 // since names[j] was already been filled by other words during swapping

If it is not required to use insertion sort, you'd better use stl sort algorithm.

edited Apr 7, 2013 at 17:54

answered Apr 7, 2013 at 15:23

taocp

23.7k10 gold badges52 silver badges62 bronze badges

Sign up to request clarification or add additional context in comments.

7 Comments

Candy Man Over a year ago

Thanks, I edited the code as you advised, but the output is still wrong, which I don't get either. Is there anything I'm missing?

taocp Over a year ago

@CandyMan i >0 should be i>=0 otherwise the first spot will not be examined. see my updated answer?

Candy Man Over a year ago

Pardon me, but I think the output is wrong for longer inputs. What's wrong with my algorithm?

Candy Man Over a year ago

Ah, what I meant was, when I entered more elements like, instead of Apple, Candy, Egg, I have, Apple, Candy, Egg, Butter, Peter.

Candy Man Over a year ago

Woops, I might not have been clear. Sorry bout that. I input the elements in separate lines, that is, after hitting enter in the console window, and not all in one line.

|

Collectives™ on Stack Overflow

InsertionSort Algorithm, Whats Wrong with my Code?

1 Answer 1

7 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

7 Comments

Your Answer

Sign up or log in

Post as a guest

Related