Insert into array in sorted order

[ElleJay]

I have a txt file of employees with their names, skills and years of experience with that skill. I'm storing their names in ascending order as they are read from the file in an array struct, while their skills and years are stored in a linked list.

This is my attempt, but the logic seems to be off

void insertInOrder (Emp e[], int i, string str) {
	int j;
	j=i;
	while (j>=0 && str[0]<e[j].fname[0]) {
   	    e[j+1] = e[j];
	    j--;
	}
	e[j+1].fname = str;
}

  if(option==1){
        in>>e[i].fname>>num;
        while(e[i].fname!="END"){
            insertInOrder(e, i, e[i].fname);
            cout<<e[i].fname<<" - "<<num<<endl;
                //insert into linked list
                for(i=1; i<=num; i++){
                    in>>skill>>year;
                    top=insertAtHead(top, skill, year);
                }
                //print skills and years
                Node *curr=top;
                for(int j=0; j<num; j++){
                    cout<<curr->data.name<<"-"<<curr->data.years<<endl;
                    curr=curr->next;
                }
                cout<<endl;

            //creates new node for each employee
            Node *newNode = new Node;
            newNode->next=top;
            top=newNode;

            i++;
            in>>e[i].fname>>num;
        }
        cout<<"Data read"<<endl;
    }
}

[jonnin]

I think you have the right idea:
find it,
make a gap by moving everything 1 slot
put it into the gap.
I don't have enough here to debug. Ill try to spot a bug but I don't see yet

alternately, there are a couple of sorts that approach O(N) as the data approaches already sorted, such that adding to the end and sorting is O(N) (its a little more than N iterations, but not by much).

[ElleJay]

My code doesn't actually sort it though, rather it changes nothing. But I can't figure out where it's gone wrong. This is the whole thing:

#include <iostream>
#include <fstream>

using namespace std;

#include "Skill.h"

// insert your function prototypes here
struct Emp{
    string fname;
    //int num;
    Node *top;
};

Node * createNode (string skill_name, int skill_years){
    Node *newNode;
    newNode= new Node;

    newNode->data.name=skill_name;
    newNode->data.years=skill_years;

    newNode->next==NULL;
    return newNode;
}

Node * insertAtHead (Node * top, string skill_name, int skill_years){
    Node *newNode;
    newNode=createNode(skill_name, skill_years);

    newNode->next=top;
    top=newNode;

    return top;
}

void insertInOrder (Emp e[], int i, string str) {
	int j;
	j=i;
	while (j>=0 && str[0]<e[j].fname[0]) {
		e[j+1] = e[j];
		j--;
	}
	e[j+1].fname = str;
}


void printNames (Emp list[], int n) {
	for (int i=0; i<n; i++) {
		cout << list[i].fname<<endl;
	}
	cout << endl;
}

void printList (Node * top) {
   Node * curr;

   curr = top;
   while (curr != NULL) {
      cout << curr->data.name<<", "<< curr->data.years << endl;
      curr = curr->next;
   }
}


*/
int main() {

    ifstream in;
    in.open("Employees.txt");

    Emp e[30];
    Skill s;

    string skill="";

    int year=0;
    int num=0;
    int option=0;
    int len;


    Node *top;
    top = NULL;


    printMenu();
    cin>>option;

    int i=0;

    if(option==1){
        in>>e[i].fname>>num;
        while(e[i].fname!="END"){
            insertInOrder(e, i, e[i].fname);
            //cout<<e[i].fname<<" - "<<num<<endl;
                //insert into linked list
                for(int h=1; h<=num; h++){
                    in>>skill>>year;
                    top=insertAtHead(top, skill, year);
                }
            

            //creates new node for each employee
            Node *newNode = new Node;
            newNode->next=top;
            top=newNode;
            
            i++;
            in>>e[i].fname>>num;
        }

        cout<<"Data read"<<endl;
    }
;
   }

[againtry]

Please show us a sample of your text file with the raw data on it.

[learningcplusplus898]

when sorting data you need to have a "temp " variable that takes the comparing value ,making the first variable empty.