Can't alphabetize(sort) strings?

0

So I'm using insertion sort to sort the strings. It runs if the strings are already are sorted. If they are partially sorted or completely reversed. It either runs producing incorrect results or gives error:(0xC0000005).

Declaration of ptr: char **ptr; where memory is dynamically allocated.

Insertion sort:

 void insertionSort(char **ptr,int rows,int cols)
{
   char *key;
   int i,j;

   //first element is considered sorted 

   for( i=1;i<=rows-1;i++)
   {
      key=ptr[i];
      for( j=i-1;strcmp(key,ptr[j])<0 && j>=0;j--)
      {
         ptr[j+1]=ptr[j];
      }
      /*Program sometimes stalls at this part and gives error:`(0xC0000005)` 
      when strings are partially sorted/completely reversed*/
      ptr[j + 1] = key;
   }
}

It is your pretty standard insertion sort implmentation. Works with numbers so I don't know why I can't sort the strings.

Also this is how ptr's values were defined from the user:

void read_charArray(char **ptr,int rows,int cols)
{
   for(int i=0;i<=rows-1;i++)
   {
      printf("Enter name for name #%-3d: ",i+1);
      fgets(ptr[i],cols+5,stdin);
      ptr[i]=strtok(array[i],"\n");
   }
}
c
string
sorting
insertion-sort
asked on Stack Overflow Jan 31, 2020 by Leon • edited Jan 31, 2020 by Leon

1 Answer

1

The error lies in the 2nd for() loop of the insertion part of the program:

Insertion sort:

 void insertionSort(char **ptr,int rows,int cols)
{
   char *key;
   int i,j;

   //first element is considered sorted 

   for( i=1;i<=rows-1;i++)
   {
      key=ptr[i];
      for( j=i-1;strcmp(key,ptr[j])<0 && j>=0;j--)
      {
         ptr[j+1]=ptr[j];
      }
      /*Program sometimes stalls at this part and gives error:`(0xC0000005)` 
      when strings are partially sorted/completely reversed*/
      ptr[j + 1] = key;
   }
}

When j is decremented to be below 0, program actually continues to evaluate strcmp(key,ptr[j]) first despite the j>=0 expression being present(basically short-circuiting. See https://softwareengineering.stackexchange.com/a/201899 )-->This means that you are trying to access memory that is out of bounds(not allocated for program) thus causing an error:(0xC0000005).

This error: (0xC0000005) means "you accessed memory you had no right to use", such as, abusing pointers or arrays that aren't big enough,etc.

To rectify this all you have to do is switch up the condition expressions in for( j=i-1; strcmp(key,ptr[j])<0 && j>=0;j--) to for( j=i-1; j>=0 && strcmp(key,ptr[j])<0;j--).

What this does is that the moment j is decremented to be below 0, program tests for j>=0 first thus exiting loop rather than causing an error.

answered on Stack Overflow Jan 31, 2020 by Leon

User contributions licensed under CC BY-SA 3.0