Sorting an array of strings with Bubble sort

Question

Any help would be greatly appreciated. I am trying to sort 12 strings alphabetically which are contained in an array using bubble sort with the following code:

#include <stdio.h>
#include <string.h>
int main()
{
   //initialising variables and the array
   char *DT [12] = { "James Smith DT01 DT265A", "John Murphy DT02 DT265A", "Robert Lam DT03 DT265A", "Michael Martin DT04 DT265A", "William Brown DT05 DT265A", "David Roy DT06 DT265A", "Richard Tremblay DT07 DT265A", "Joseph Lee DT08 DT265A", "Thomas Gagnon DT09 DT265A", "Charles Wilson DT10 DT265A", "Chris Philips DT11 DT265A", "Henry Hill DT12 DT265A"  } ;
   char temp[100];
   int n = sizeof(DT)/sizeof(DT[0]);

   //Implementing Algorithm using bubble sort to sort string array
   //
   for (int j = 0 ; j < n - 1 ; j++ )
   {
      for (int i = j + 1 ; i < n ; i++ )
      {
         if( strcmp(DT[j], DT[i]) > 0 ) 
         {
            strcpy(temp, DT[j]);
            strcpy(DT[j], DT[i]);
            strcpy(DT[i], temp);
         }//end if
      }//end for
   }//end for
   printf("Strings in sorted order are : ");
   for (int i=0; i<n; i++)
   {
      printf("\n String %d is %s", i+1, DT[i]);
   }

   getchar();
   getchar();
   return 0;
}//end main()

The output I get is:

Strings in sorted order are :

String 1 is A

String 2 is A

String 3 is 2vid Roy DT06 DT265A

String 4 is Roy DT06 DT265A

String 5 is Charles Wilson DT10 DT265A

String 6 is

String 7 is Chris Philips DT11 DT265A

String 8 is 06 DT265A

String 9 is avidRoy DT06 DT265A

String 10 is mith DT01 DT265David Roy Dyy DT06 DT265A

String 11 is y DT06 DT265A

String 12 is y DT06 DT265A

char *DT [12] not sure, but isn't it an array of literals? — Jean-François Fabre
– Jean-François Fabre ♦, Commented Apr 12, 2018 at 13:13

Some programmer dude · Accepted Answer · 2018-04-12 13:13:40Z

5

The problem is that you attempt to overwrite the contents of the literal strings, and literals strings in C are read-only arrays of characters.

Instead of attempting to copy the strings themselves, copy the pointers. As in

char *temp = DT[j];
DT[j] = DT[i];
DT[i] = temp;

Another possible solution is to make DT an array of arrays instead:

char DT[12][100] = { ... };

Make sure that the size of the secondary array is large enough to fit the longest string (plus one as you of course needs space for the terminator as well).

answered Apr 12, 2018 at 13:13

Some programmer dude

411k36 gold badges420 silver badges655 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

chux Over a year ago

Detail: String literals can well be thought of as "read-only" for learners. Yet writing string literals is UB - not read-only. strcpy() might "work" - it might not - it is UB.

Vlad from Moscow · Accepted Answer · 2018-04-12 13:43:05Z

You have an array of pointers to string literals

char *DT [12] = { "James Smith DT01 DT265A", ... };

and then you are trying to change the string literals.

strcpy(DT[j], DT[i]);
strcpy(DT[i], temp);

However you may not change string literals. Any attempt to change a string literal results in undefined behavior.

From the C Standard (6.4.5 String literals)

7 It is unspecified whether these arrays are distinct provided their elements have the appropriate values. If the program attempts to modify such an array, the behavior is undefined.

What you need to swap is pointers to string literals.

Also take into account that you implemented the bubble sort algorithm incorrectly. In fact you implemented the inefficient selection sort. The bubble sort algorithm is based on comparing adjacent elements.

And according to the C Standard the function main without parameters shall be declared like

int main( void )

Here is a demonstrative program that shows how the bubble sort algorithm can be applied to your array.

#include <stdio.h>
#include <string.h>

int main(void) 
{
    enum { N = 12 };
    char * DT[N] = 
    { 
        "James Smith DT01 DT265A", 
        "John Murphy DT02 DT265A", 
        "Robert Lam DT03 DT265A", 
        "Michael Martin DT04 DT265A", 
        "William Brown DT05 DT265A", 
        "David Roy DT06 DT265A", 
        "Richard Tremblay DT07 DT265A", 
        "Joseph Lee DT08 DT265A", 
        "Thomas Gagnon DT09 DT265A", 
        "Charles Wilson DT10 DT265A", 
        "Chris Philips DT11 DT265A", 
        "Henry Hill DT12 DT265A"  
    };

    for ( size_t n = N, last; !( n < 2 ); n = last )
    {
        for ( size_t i = last = 1; i < n; i++ )
        {
            if ( strcmp( DT[i], DT[i-1] ) < 0 )
            {
                char *tmp = DT[i];
                DT[i] = DT[i-1];
                DT[i-1] = tmp;
                last = i;
            }
        }
    }

    puts( "Strings in sorted order are" );

    for ( size_t i = 0; i < N; i++ )
    {
        printf( "String %zu is %s\n", i + 1, DT[i] );
    }

    return 0;
}

The program output is

Strings in sorted order are
String 1 is Charles Wilson DT10 DT265A
String 2 is Chris Philips DT11 DT265A
String 3 is David Roy DT06 DT265A
String 4 is Henry Hill DT12 DT265A
String 5 is James Smith DT01 DT265A
String 6 is John Murphy DT02 DT265A
String 7 is Joseph Lee DT08 DT265A
String 8 is Michael Martin DT04 DT265A
String 9 is Richard Tremblay DT07 DT265A
String 10 is Robert Lam DT03 DT265A
String 11 is Thomas Gagnon DT09 DT265A
String 12 is William Brown DT05 DT265A

If you want to deal with a two-dimensional character array containing strings then the program can look the following way

#include <stdio.h>
#include <string.h>

int main(void) 
{
    enum { M = 12, N = 100 };
    char DT[M][N] = 
    { 
        "James Smith DT01 DT265A", 
        "John Murphy DT02 DT265A", 
        "Robert Lam DT03 DT265A", 
        "Michael Martin DT04 DT265A", 
        "William Brown DT05 DT265A", 
        "David Roy DT06 DT265A", 
        "Richard Tremblay DT07 DT265A", 
        "Joseph Lee DT08 DT265A", 
        "Thomas Gagnon DT09 DT265A", 
        "Charles Wilson DT10 DT265A", 
        "Chris Philips DT11 DT265A", 
        "Henry Hill DT12 DT265A"  
    };

    for ( size_t n = M, last; !( n < 2 ); n = last )
    {
        for ( size_t i = last = 1; i < n; i++ )
        {
            if ( strcmp( DT[i], DT[i-1] ) < 0 )
            {
                char tmp[N];
                strcpy( tmp, DT[i] );
                strcpy( DT[i], DT[i-1] );
                strcpy( DT[i-1], tmp );
                last = i;
            }
        }
    }

    puts( "Strings in sorted order are" );

    for ( size_t i = 0; i < M; i++ )
    {
        printf( "String %zu is %s\n", i + 1, DT[i] );
    }

    return 0;
}

Its output is the same as shown above.

Tom's · Accepted Answer · 2018-04-12 13:14:55Z

0

You can't use strcpy on a readonly string. When you type "James Smith DT01 DT265A" and affect its address, this string is readonly.

So if you want to keep this way, you can replace

char temp[100];
...
        strcpy(temp, DT[j]);
        strcpy(DT[j], DT[i]);
        strcpy(DT[i], temp);

by

char *temp;
...
        temp = DT[j];
        DT[j] = DT[i];
        DT[i] = temp;

answered Apr 12, 2018 at 13:14

Tom's

2,4981 gold badge14 silver badges25 bronze badges

Comments

Abhishek Keshri · Accepted Answer · 2018-04-12 13:27:37Z

0

You can use char arr[][MAX] and for sorting use the following function:

void sortStrings(char arr[][MAX], int n)
{
    char temp[MAX];

    // Sorting strings using bubble sort
    for (int j=0; j<n-1; j++)
    {
        for (int i=j+1; i<n; i++)
        {
            if (strcmp(arr[j], arr[i]) > 0)
            {
                strcpy(temp, arr[j]);
                strcpy(arr[j], arr[i]);
                strcpy(arr[i], temp);
            }
        }
    }
}

edited Apr 12, 2018 at 13:27

answered Apr 12, 2018 at 13:15

Abhishek Keshri

3,31417 silver badges35 bronze badges

2 Comments

Vlad from Moscow Over a year ago

It is not better.

chux Over a year ago

Showing how to use this with char *DT [12] (or whatever changes are needed) would help.

Collectives™ on Stack Overflow

Sorting an array of strings with Bubble sort

4 Answers 4

1 Comment

Comments

Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

1 Comment

Comments

Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related