Lexicographic sorting in C++
Sorting a list lexicographically, means sorting the contents of list so that the resultant list have its contents in dictionary order. Although, such a lexicographic sorting can be performed using a number of algorithms, I will be discussing here, the most common and the simplest technique called Bubble sort.
Bubble sort is a very simple sorting technique and I assume that the readers have it's prior knowledge. So without taking the pain of explaining the bubble sort, I directly jump over to the explanation of the function used for comparing two stings in C/C++.
strcmp() and strcmpi()
I have used the function called strcmpi(), and for accessing this function you should include the header file string.h. The general declaration for this function is as follows:
int strcmpi(const char*s1,const char*s2);
Here you should note that this function performs comparison of s1 and s2 without case sensitivity. On the other hand, if we talk about the strcmp() function, it performs the comparison of s1 and s2 without ignoring the case sensitivity.
This function starts comparing the first character of each string. If
they are equal to each other, it continues with the following pairs
until the characters differ or until a terminating null-character is
reached.
Both of these functions have a return type integer, means both of these functions returns an integral value, depending upon the relationship between s1 and s2.
A zero value indicates that both strings are equal.
A value greater than zero indicates that the first character that does not match has a greater value in s1 than in s2; and a value less than zero indicates the reverse condition.
A value greater than zero indicates that the first character that does not match has a greater value in s1 than in s2; and a value less than zero indicates the reverse condition.
The good thing about my code is that it is totally user defined and initially asks the user to input the total number of words that are to be sorted. For this I have also used the concept of allocating the memory dynamically.
Here is my cpp source code:
#include<conio.h>
#include<iostream.h>
#include<string.h>
int main()
{
clrscr();
char **arr;
int n;
cout<<"ENTER THE NUMBER OF WORDS \n";
cin>>n;
//dynamic memory allocation
arr=new char*[n];
for(int i=0;i<n;i++)
arr[i]=new char[20];
//prompting user to input words
cout<<"ENTER THE WORDS\ n";
for(i=0;i<n;i++)
cin>>arr[i];
//applying the bubble sort
for(i=1;i<n;i++)
{
for(int j=0;j<n-i;j++)
{
if(strcmpi(arr[j],arr[j+1])>0)
{
char*tmp;
tmp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=tmp;
}
}
}
//printing lexicographically sorted list
cout<<"\n LEXICOGRAPHICALLY SORTED WORDS ARE : \n"<<endl;
for(i=0;i<n;i++)
cout<<arr[i]<<endl;
getch();
return 1;
}
for(i=0;i<n;i++)
cin>>arr[i];
//applying the bubble sort
for(i=1;i<n;i++)
{
for(int j=0;j<n-i;j++)
{
if(strcmpi(arr[j],arr[j+1])>0)
{
char*tmp;
tmp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=tmp;
}
}
}
//printing lexicographically sorted list
cout<<"\n LEXICOGRAPHICALLY SORTED WORDS ARE : \n"<<endl;
for(i=0;i<n;i++)
cout<<arr[i]<<endl;
getch();
return 1;
}
Output:-
1)/2
