Click here to Skip to main content
15,070,511 members
Please Sign up or sign in to vote.
1.00/5 (1 vote)
See more:
Binary insection sort alphabetically order.

I have problems in code.
Please help me.

What I have tried:

C++
#include <stdio.h>
#include <string.h>
#include <conio.h>

#define MAX_STRINGS 50
#define MAX_STRING_LEN 50

struct students 
{
   char studentmuber[21];
   char firstname[21777];
   char surname[21];
   char group[21];
};



void InsertionSort(char list[MAX_STRINGS][MAX_STRING_LEN]);

int main()
{
        struct students sg1[43]; 

//DT265A	�	part-time	Higher	Diploma	
//DT265A	�	12	students	


strcpy(sg1[0].studentmuber, "C17501096");
    strcpy(sg1[0].firstname, "Patrik");
    strcpy(sg1[0].surname, "Farrell");
    strcpy(sg1[0].group, "DT265A");
    
     strcpy(sg1[1].studentmuber, "C17719309");
    strcpy(sg1[1].firstname, "Iosif");
    strcpy(sg1[1].surname, "Balasca");
    strcpy(sg1[1].group, "DT265A");
    
      strcpy(sg1[2].studentmuber, "C17313136");
    strcpy(sg1[2].firstname, "Monika");
    strcpy(sg1[2].surname, "Adamczewska");
    strcpy(sg1[2].group, "DT265A");
    
    strcpy(sg1[0].studentmuber, "C17325641");
    strcpy(sg1[0].firstname, "Benjamin");
    strcpy(sg1[0].surname, "Cox");
    strcpy(sg1[0].group, "DT265A");
    
     strcpy(sg1[1].studentmuber, "C17368666");
    strcpy(sg1[1].firstname, "Immanuel");
    strcpy(sg1[1].surname, "Mahmoud");
    strcpy(sg1[1].group, "DT265A");
    
      strcpy(sg1[2].studentmuber, "C17452664");
    strcpy(sg1[2].firstname, "Mahmoud");
    strcpy(sg1[2].surname, "Almahroum");
    strcpy(sg1[2].group, "DT265A");
    
       strcpy(sg1[3].studentmuber, "C17470662");
    strcpy(sg1[3].firstname, "Ryan");
    strcpy(sg1[3].surname, "Farmar");
    strcpy(sg1[3].group, "DT265A");
    
    strcpy(sg1[4].studentmuber, "C17407044");
    strcpy(sg1[4].firstname, "Ryan");
    strcpy(sg1[4].surname, "Campbell");
    strcpy(sg1[4].group, "DT265A");
    
      strcpy(sg1[5].studentmuber, "C17484426");
    strcpy(sg1[5].firstname, "Daire");
    strcpy(sg1[5].surname, "English");
    strcpy(sg1[5].group, "DT265A");
    
    strcpy(sg1[6].studentmuber, "C17318676");
    strcpy(sg1[6].firstname, "Joseph");
    strcpy(sg1[6].surname, "Byrne");
    strcpy(sg1[6].group, "DT265A");
    
     strcpy(sg1[7].studentmuber, "C17431466");
    strcpy(sg1[7].firstname, "Janae");
    strcpy(sg1[7].surname, "Farinas");
    strcpy(sg1[7].group, "DT265A");
    
     strcpy(sg1[8].studentmuber, "C17504869");
    strcpy(sg1[8].firstname, "Alexanderu");
    strcpy(sg1[8].surname, "Cardas");
    strcpy(sg1[8].group, "DT265A");
   
    strcpy(sg1[9].studentmuber, "C17319656");
    strcpy(sg1[9].firstname, "Harry");
    strcpy(sg1[9].surname, "Bebbigton");
    strcpy(sg1[9].group, "DT265A");
    
       
    strcpy(sg1[10].studentmuber, "D17125070");
    strcpy(sg1[10].firstname, "Taif");
    strcpy(sg1[10].surname, "Beedh");
    strcpy(sg1[10].group, "DT265A");
    
    strcpy(sg1[11].studentmuber, "C17744044");
    strcpy(sg1[11].firstname, "Martynas");
    strcpy(sg1[11].surname, "Drazdziulis");
    strcpy(sg1[11].group, "DT265A");
    
    
//2. DT265C	�	part-time	Master�s	Qualifier	

//DT265C	�	10	students	

    strcpy(sg1[12].studentmuber, "C7335606");
    strcpy(sg1[12].firstname, "Daniel");
    strcpy(sg1[12].surname, "Foley");
    strcpy(sg1[12].group, "DT265C");
    
       strcpy(sg1[13].studentmuber, "C17431012");
    strcpy(sg1[13].firstname, "Joel");
    strcpy(sg1[13].surname, "Kell");
    strcpy(sg1[13].group, "DT265C");
    
    
          strcpy(sg1[13].studentmuber, "C17455002");
    strcpy(sg1[13].firstname, "Stephen");
    strcpy(sg1[13].surname, "Lynch");
    strcpy(sg1[13].group, "DT265C");
    
           strcpy(sg1[14].studentmuber, "C17438392");
    strcpy(sg1[14].firstname, "Gibson");
    strcpy(sg1[14].surname, "Neil");
    strcpy(sg1[14].group, "DT265C");
    
           strcpy(sg1[15].studentmuber, "C17458124");
    strcpy(sg1[15].firstname, "Ryan");
    strcpy(sg1[15].surname, "Machren");
    strcpy(sg1[15].group, "DT265C");
    
      strcpy(sg1[16].studentmuber, "C17407712");
    strcpy(sg1[16].firstname, "Ross");
    strcpy(sg1[16].surname, "Mac William");
    strcpy(sg1[16].group, "DT265C");
    
     strcpy(sg1[17].studentmuber, "C17744515");
    strcpy(sg1[17].firstname, "George");
    strcpy(sg1[17].surname, "Hawthorne");
    strcpy(sg1[17].group, "DT265C");
    
    strcpy(sg1[18].studentmuber, "C17744516");
    strcpy(sg1[18].firstname, "George");
    strcpy(sg1[18].surname, "Hawthornic");
    strcpy(sg1[18].group, "DT265C");
    
    
      strcpy(sg1[19].studentmuber, "C17501096");
    strcpy(sg1[19].firstname, "Patrick.");
    strcpy(sg1[19].surname, "Farrell");
    strcpy(sg1[19].group, "DT265C");
    
    
      strcpy(sg1[20].studentmuber, "C17463744");
    strcpy(sg1[20].firstname, "Ivan");
    strcpy(sg1[20].surname, "Garcia");
    strcpy(sg1[20].group, "DT265C");
    
    
      strcpy(sg1[21].studentmuber, "C17331306");
    strcpy(sg1[21].firstname, "Jerricho.");
    strcpy(sg1[21].surname, "Juliano");
    strcpy(sg1[21].group, "DT265C");
    
        strcpy(sg1[22].studentmuber, "C17740835");
    strcpy(sg1[22].firstname, "Mohammed.");
    strcpy(sg1[22].surname, "Kadiri");
    strcpy(sg1[22].group, "DT265C");
    
 //  3. DT265B	�	full-time	Master�s	Qualifier	 
// DT265B	�	14	students	 
    
     strcpy(sg1[23].studentmuber, "C17474812");
    strcpy(sg1[23].firstname, "James");
    strcpy(sg1[23].surname, "Mc Ardle");
    strcpy(sg1[23].group, "DT265B");
    
      strcpy(sg1[24].studentmuber, "C17303563");
    strcpy(sg1[24].firstname, "Richard");
    strcpy(sg1[24].surname, "Meyer");
    strcpy(sg1[24].group, "DT265B");
    
      strcpy(sg1[25].studentmuber, "C17737111");
    strcpy(sg1[25].firstname, "Dean");
    strcpy(sg1[25].surname, "Rourke");
    strcpy(sg1[25].group, "DT265B");
    
     strcpy(sg1[26].studentmuber, "C17427304");
    strcpy(sg1[26].firstname, "Meenal");
    strcpy(sg1[26].surname, "Mujahed");
    strcpy(sg1[26].group, "DT265B");
    
      
     strcpy(sg1[26].studentmuber, "D17123259");
    strcpy(sg1[26].firstname, "Tyra");
    strcpy(sg1[26].surname, "Neftzer");
    strcpy(sg1[26].group, "DT265B");
    
    
    strcpy(sg1[27].studentmuber, "C17441552");
    strcpy(sg1[27].firstname, "Conor");
    strcpy(sg1[27].surname, "O_Donell");
    strcpy(sg1[27].group, "DT265B");
    
      strcpy(sg1[28].studentmuber, "C7718445");
    strcpy(sg1[28].firstname, "Ciab");
    strcpy(sg1[28].surname, "Morrin");
    strcpy(sg1[28].group, "DT265B");
    
    
      strcpy(sg1[29].studentmuber, "C17323756");
    strcpy(sg1[29].firstname, "Gedimas.");
    strcpy(sg1[29].surname, "Petreikis");
    strcpy(sg1[29].group, "DT265C");
    
    strcpy(sg1[30].studentmuber, "C17706201");
    strcpy(sg1[30].firstname, "Jurijus");
    strcpy(sg1[30].surname, "Pacalovas");
    strcpy(sg1[30].group, "DT265B");
    
        strcpy(sg1[31].studentmuber, "C17426754");
    strcpy(sg1[31].firstname, "Eoghan");
    strcpy(sg1[31].surname, "Mellott");
    strcpy(sg1[31].group, "DT265B");
    
        strcpy(sg1[32].studentmuber, "C14045363");
    strcpy(sg1[32].firstname, "Richar");
    strcpy(sg1[32].surname, "Mayer");
    strcpy(sg1[32].group, "DT265B");
    
    
    strcpy(sg1[33].studentmuber, "C16409062");
    strcpy(sg1[33].firstname, "Brian");
    strcpy(sg1[33].surname, "Mc_Gee");
    strcpy(sg1[33].group, "DT265B");
    
     strcpy(sg1[34].studentmuber, "C17390923");
    strcpy(sg1[34].firstname, "Gleen");
    strcpy(sg1[34].surname, "Moore");
    strcpy(sg1[34].group, "DT265B");
    
     strcpy(sg1[35].studentmuber, "C17303406");
    strcpy(sg1[35].firstname, "Robert");
    strcpy(sg1[35].surname, "MC_Givney");
    strcpy(sg1[35].group, "DT265B");
    
     strcpy(sg1[36].studentmuber, "D16127812");
    strcpy(sg1[36].firstname, "Seng_Keong");
    strcpy(sg1[36].surname, "Onny_Lim");
    strcpy(sg1[36].group, "DT265B");
    
 //  4. DT8900	�	full-time	International	Master�s	Qualifier		Admission	numbers	are	as	follows:	  
//  DT8900	�	6	students
    
     
         strcpy(sg1[37].studentmuber, "C17718415");
    strcpy(sg1[37].firstname, "Jonathan");
    strcpy(sg1[37].surname, "Unsworth");
    strcpy(sg1[37].group, "DT8900");
    
         strcpy(sg1[38].studentmuber, "C17751103");
    strcpy(sg1[38].firstname, "Niall");
    strcpy(sg1[38].surname, "Williams");
    strcpy(sg1[38].group, "DT8900");
    
     strcpy(sg1[39].studentmuber, "17764691");
    strcpy(sg1[39].firstname, "Jason.");
    strcpy(sg1[39].surname, "Van Raamsdonk");
    strcpy(sg1[39].group, "DT8900");
    
     strcpy(sg1[40].studentmuber, "C17378303");
    strcpy(sg1[40].firstname, "Mariana.");
    strcpy(sg1[40].surname, "Pirtac");
    strcpy(sg1[40].group, "DT8900");
    
     strcpy(sg1[41].studentmuber, "C17433026");
    strcpy(sg1[41].firstname, "Philip.");
    strcpy(sg1[41].surname, "Toolan");
    strcpy(sg1[41].group, "DT8900");
    
     strcpy(sg1[42].studentmuber, "C17388633");
    strcpy(sg1[42].firstname, "Killian");
    strcpy(sg1[42].surname, "Pogue");
    strcpy(sg1[42].group, "DT8900");
    
    int index;
   char strings[MAX_STRINGS][MAX_STRING_LEN]={"", "Farrell","Balasca","Adamczewska","Cox","Almahroum","Farmar","Campbell","English","Byrne","Farinas","Cardas","Bebbigton","Beedh","Drazdziulis","Foley","Kell","Lynch","Neil","Machren","Mac","William","Hawthorne","Hawthornic","Farrell","Garcia","Juliano","Kadiri","Mc,Ardle","Meyer","Rourke","Mujahed","Neftzer","O_Donell","Morrin","Petreikis","Pacalovas","Mellott","Mayer","Mc_Gee","Moore","MC_Givney","Onny_Lim","Unsworth","Williams","Van,Raamsdonk","Pirtac","Toolan","Pogue","Z"};


    for (index = 0; index < MAX_STRINGS; index++)
    {
       strings[index][sizeof(strings[index]) - 1] = '\0';
        
        
    }

    InsertionSort(strings);

    printf("\nThe input set, in alphabetical order:\n");
    for (index = 1; index < MAX_STRINGS; index++)
    {
        printf("%s\n", strings[index]);
    }
    
     getch();
    
    
    
    
        return  0;
}

 int binarySearch(char stringslist[MAX_STRINGS][MAX_STRING_LEN], char item[MAX_STRINGS][MAX_STRING_LEN], int low, int high)
{
	if (high <= low)
		return (item[MAX_STRINGS][MAX_STRING_LEN] > stringslist[low][MAX_STRING_LEN])? (low + 1): low;

	int mid = (low + high)/2;

	if(item[MAX_STRINGS][MAX_STRING_LEN] == stringslist[mid][MAX_STRING_LEN])
		return mid+1;

	if(item[MAX_STRINGS][MAX_STRING_LEN] > stringslist[low][MAX_STRING_LEN])
		return binarySearch(stringslist, item, mid+1, high);
	return binarySearch(stringslist, item, low, mid-1);
}

void InsertionSort(char list[MAX_STRINGS][MAX_STRING_LEN])
{
    char loc[MAX_STRINGS][MAX_STRING_LEN];
int j=0;
    char selected[MAX_STRINGS][MAX_STRING_LEN];

    for (int i = 1; i < MAX_STRINGS; i++)
    {    
         j = i - 1;
		selected[MAX_STRINGS][MAX_STRING_LEN] = list[i][MAX_STRING_LEN];
        
        loc[MAX_STRINGS][MAX_STRING_LEN] = binarySearch(list, selected, j, j);
        
      
        
        	while (j >= loc[MAX_STRINGS][MAX_STRING_LEN])
		{
			list[j+1][MAX_STRING_LEN] = list[j][MAX_STRING_LEN];
			j--;
		}
		list[j+1][MAX_STRING_LEN] = selected[MAX_STRINGS][MAX_STRING_LEN];
        
       
    }
}
Posted
Updated 20-Apr-18 5:38am
v2
Comments
Patrice T 20-Apr-18 3:37am
   
'I have problems in code.'
What problem ? Where ?

No one will do your work for you, so learn to code with some tutorial.

Read my how to start your homeworks.

And you have luck I gave an answer to a similar question which should help you.

Additional tip: use functions like
C++
FillStudent( students *student, char* number, ....
   
Comments
Member 13768333 20-Apr-18 6:20am
   
I have two char with two dominions how to make
key 2d = strings 2d
Not your mystery problem, but:
C++
char firstname[21777];

That is a long firstname !
   
One problem is that you have out of bound array accesses at
selected[MAX_STRINGS][MAX_STRING_LEN] = list[i][MAX_STRING_LEN];
and all other lines using the array sizes as indexes. The maximum allowed index is size - 1.

The second problem is that you did not know how to copy character arrays. In the above code line you are copying a single character (from and to the wrong place due to to out of bound). You have to copy each character:
C++
for (int k = 0; k < MAX_STRING_LEN; k++)
    selected[j][k] = list[i][k];
or just use strcpy():
C++
strcpy(selected[j], list[i]);
or memcpy():
C++
memcpy(selected[j], list[i], MAX_STRING_LEN);

The next problem is that you did not understand Insertion sort - Wikipedia[^] or failed at least to use the proper indexes.

There may be more problems but I did not checked all the code.
   
Here are a couple of tips. I like type definitions as I find they simplify many things such as making changes. Here's how I would use a type with your program :
C++
#define TEXTSIZE  23
typedef char textitem[TEXTSIZE+1];  // I prefer four byte boundaries

typedef struct students 
{
   textitem number;
   textitem firstname;
   textitem surname;
   textitem group;
} Students;
You can initialize data structures directly. Here is an example of the first two items:
C++
#define STUDENT_COUNT 43

Students sg1[STUDENT_COUNT] =
{
    { "C17501096", "Patrik", "Farrell", "DT265A" },
    { "C17719309", "Iosif",  "Balasca", "DT265A" },
    // and so on...
};
Another type and initialization :
C++
#define MAX_STRING_LEN 47
typedef char String[MAX_STRING_LEN+1];
String strings[MAX_STRINGS] =
{
   "", "Farrell","Balasca","Adamczewska","Cox",
  // and so on...
};
The for loop following that and before the InsertionSort call is unnecessary. Lastly, here is how binarySearch should look :
C++
int binarySearch( String stringslist[], String item, int low, int high )
{
    int mid;   // must be here in C

    if( high <= low )
        return strcmp( item, stringslist[low] ) > 0 ? (low + 1): low;

    mid = ( low + high ) / 2;

    if( strcmp( item, stringslist[mid] ) == 0 )
        return mid + 1;

    if( strcmp( item, stringslist[low] ) > 0 )
        return binarySearch( stringslist, item, mid+1, high );

    return binarySearch( stringslist, item, low, mid-1 );
}
I am not sure about the last two calls to binarySearch because you swapped the order of the arguments. One should be the list and one the search term and they can't be swapped. The key thing there is you need to compare the strings. What you have is not doing that. I leave the insertion sort function for you to figure out. They key is compare the strings with strcmp and, as Jochen mentioned, copy the strings with strcpy or memcpy.

One other thing. You had the declaration of mid in the middle of the function. You can't do that in C but you can in C++. If this is actually C++ then I would use constants and not the definitions. There are other things that could be done differently but since the purpose of this is learning the algorithms I will refrain from getting into those.
   
v3

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)




CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900