Alphabetic Order Algorithm

[ChrisPy]

Hi guys...(I can start this topic with :"Sorry for my english")

I'm having few problems with my code, to say the truth I don't know what is the problem... but I need a hint to solve it.

My code has to be a "address book" with names and telephone numbers,
So I have my struct:

   struct agenda{
char nome [20] //Name string
char cell [10] //Telephone number String
}

After the input of all names and numbers that We want, I have to order them.
so I wrote a function to "order" (it doesn't work):

void inverti(agenda* &array,int primo,int secondo){ //Change Function, operands:"Array"(only the pointer),and the psition of elements
    agenda pippo=array[primo];                      
    array[primo]=array[secondo];                    
    array[secondo]=pippo;                           
}
void ordina(agenda* &array,int elementi){           //Order Function, operands:"Array"(only the pointer),and the number of elements
    int i;
    int ciccio;                                     //Needs to know if a change has been made
    int lettera=0;                                    //Indicate wich character are we comparing
    do{
        ciccio=0;
        
    for(i=0;i<elementi-1;i++){      //For each element(-1) of the array
        if(array[i].nome[lettera]>array[i+1].nome[lettera]){ //Compare the character that we are comparing whith the next element's character
            inverti(array,i,i+1);ciccio++;                   //if The first one is above, reverse them,also does cicco+1            
    }        
        if(array[i].nome[lettera]==array[i+1].nome[lettera]){             //else,if them are equal, it compares the next char.
                if(array[i].nome[lettera+1]>array[i+1].nome[lettera+1]){  
                  inverti(array,i,i+1);ciccio++;}                         //if the first one is above, reverse them. also does ciccio+1
            }
        } 
    
        if(ciccio==0){lettera++;} //If ciccio doesn't change, it go to the next char
    }while(lettera<5);           
}

I really don't know why it doesn't order my names.. it changes something but not in Alphabetic Order and I don't know why...
I have tried to use strings, but I can't, because im using a "dynamic array" and, if I use strings It can't know the size of my struct to allocate new bytes.

[Ganado]

There's no reason why you can't use std::strings

class agenda {
    std::string nome;
    std::string cell;
};

. You can get a string's length with the .size() or .length() function.

But that aside, what input are you giving the ordina function?

You have an odd hardcoded condition of "lettera < 5". What happens if a word is less than 5 characters long?

[ChrisPy]

first of all, Thanks for your reply.

If I use strings the program stops automatically at the second name input
because the "string type"hasn't a specific byte dimension
and than sizeof(agenda) isn't correct.
the add contact function(to explain):

void aggiungi(agenda *&array,int elementi){    //Add function, operands (array's pointer,number of elements)
    array=(agenda*)realloc(array,elementi*sizeof(agenda)); //Add 30 byte in the array |(sizeof(agenda)=30byte)|
    cout<<"Inserire il nome del contatto\n";
    cin>>array[elementi-1].nome;
    cout<<"Inserire il numero del contatto\n";
    cin>>array[elementi-1].cell;
            
}

the condition will be "lettera<variable" where variable is the length of the shortest word
(i know that isn't totally correct...but i can't imagine to other solutions...)

so... I've thought about the order function, with my pencil and a paper sheet, this is working:

void ordina(agenda* &array,int elementi){           //Order Function, operands:"Array"(only the pointer),and the number of elements
    int i;
    int ciccio;                                     //Needs to know if a change has been made
    int lettera=0;                                    //Indicate wich character are we comparing
    do{
        ciccio=0;
        
    for(i=0;i<elementi-1;i++){      //For each element(-1) of the array
        
        if(array[i].nome[lettera]>array[i+1].nome[lettera]){cout<<"Invertiti:  "<<array[i].nome<<" e "<<array[i+1].nome<<"\n"; //Compare the character that we are comparing whith the next element's character
            inverti(array,i,i+1);ciccio++;                   //if The first one is above, reverse them,also does cicco+1            
    }  
       if(lettera!=0){ 
        if(array[i].nome[lettera-1]==array[i+1].nome[lettera-1]){             //else,if them are equal, it compares the next char.
                if(array[i].nome[lettera]>array[i+1].nome[lettera]){  
                  inverti(array,i,i+1);ciccio++;}                         //if the first one is above, reverse them. also does ciccio+1
            }
       }
        } 
    
        if(ciccio==0){lettera++;} //If ciccio doesn't change, it go to the next char
    }while(lettera<=3);           
}

but it still not work.... I'm getting crazy


**EDIT**: i saw now that you suggested me to use classes instead of structures.
but I haven't studied classes yet (probably i'm going to study them in the next hours...but this exercise is a school one, so i can't use something that we haven't studied at school)

[Ganado]

I don't know what in particular is wrong with your ordina function (besides the weirdness already mentioned). If I simply re-write it with an equally inefficient bubble-sort, it might get the job done...

Note that I converted the nome char array to an std::string for easy lexicographical string comparison. If you don't want to use std::strings like this, you'd have to change the implementation of the "comp" function I made.

#include <iostream>
#include <string>
#include <algorithm>

struct agenda{
    char nome [20]; //Name string
    char cell [10]; //Telephone number String
};

/// Lexographical compare
int comp(char this_nome[], char that_nome[])
{
    std::string this_str(this_nome);
    std::string that_str(that_nome);
    return this_str.compare(that_str);  
}

/// "Bubble sort"
void ordina(agenda* arr, int num_elements){       
   
    for( int i = 0; i < num_elements - 1; i++)
    {
        for (int j = 0; j < num_elements-1 - i; j++)
        {
            // Swap if "greater than"
            if (comp(arr[j].nome, arr[j+1].nome) > 0)
            {                
                std::swap(arr[j], arr[j+1]);
            }
        }
    }
}

void print(agenda* array, int elementi)
{
    for (int i = 0; i < elementi; i++)
    {
        std::cout << array[i].nome << '\n';   
    }
    std::cout << '\n';
}

int main()
{
    const int N = 4;
    
    agenda arr[N] {
        { "zeta",        "0" },
        { "alpha",       "0" },
        { "aaaaaaaaaa",  "0" },
        { "banana",      "0" }
    };
    
    print(arr, N);   
    ordina(arr, N);
    print(arr, N);   
}

cplusplus252306>main
zeta
alpha
aaaaaaaaaa
banana

aaaaaaaaaa
alpha
banana
zeta

I think part of the confusion here is the letters and varying lengths of the strings.
My advice is to first understand how to sort ints, because sorting ints just requires a simple > (greater than) check.

Then, once you understand how to sort ints, sort char arrays (strings) by writing a comp function similar to the one I used.

There is also a built-in function called strcmp.
http://www.cplusplus.com/reference/cstring/strcmp/
#include <cstring> to use it.

**EDIT**: i saw now that you suggested me to use classes instead of structures.
but I haven't studied classes yet (probably i'm going to study them in the next hours...but this exercise is a school one, so i can't use something that we haven't studied at school)

Yes, use structs. I didn't mean to confuse you, I meant to write struct. (Structs and classes are the same thing in C++ except structs are public by default).


In the real word, we'd use std::sort with a custom comparator function.
http://www.cplusplus.com/reference/algorithm/sort/
https://stackoverflow.com/questions/1380463/sorting-a-vector-of-custom-objects

[ChrisPy]

thanks a lot, now i don't have time, it's morning and i have to go school.
later i will tet you know if i have understand it :D