CODEWITHSUNDEEP
c
user8753900
user8753900

Reputation:

Applying bubble sort using pointer to pointer concept?

I am sorting an array alphabetically using bubble sort while applying the pointer to pointer concept. My program crashes when I use strcpy function to swap address of array *b[4] using pointer to pointer **p[4], apart from that the program works fine.

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

int main()
 {
   char a[][10]={"milk","eggs","bread","cheese"};
   char *b[4],**p[4],*temp;
   int length[4];
   int i,j;

   for(i=0;i<4;i++)
   {
      length[i]=strlen(a[i]);
      b[i]=(char *)calloc(length[i],sizeof(char));
      strcpy(b[i],a[i]);
      p[i]=&b[i];
    }

  for(j=0;j<4;j++)
   {
     for(i=0; i<3-j; i++)
      {
        if(strcmp(*p[i],*p[i+1])>0)
          { /*         
            strcpy(temp,*p[i]);    This is the part of the code where the  
            strcpy(*p[i],*p[i+1]); program crashes, can someone please point            
            strcpy(*p[i+1],temp);  out the logical flaw
             */
          }
       }
    }  

  for(i=0;i<4;i++)
   {
    puts(*p[i]);
   }  


}

Upvotes: 0

Views: 125

Answers (4)

ikegami
ikegami

Reputation: 385897

In strcpy(temp,*p[i]), temp is expected to point to memory into which the string should be copied. You never initialized temp, causing undefined behaviour.

But as you mentioned, all you need is to copy the pointer.

temp = p[i];
p[i] = p[i+1];
p[i+1] = temp;

Cleaned up solution:

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

int main(void) {
   const char *a[] = { "milk", "eggs", "bread", "cheese" };
   size_t n = sizeof(a)/sizeof(a[0]);

   const char** p;
   { /* Make p a shallow copy of a so that we don't change a */
      p = malloc(n * sizeof(char*));

      {
         size_t i;
         const char** src = a;
         const char** dst = p;
         for (i=n; i--; )
            *(dst++) = *(src++);
      }
   }

   { /* Sort p using bubble sort */
      size_t i;
      int swapped = 1;
      while (swapped) {
         swapped = 0;
         for (i=0; i<n-1; ++i) {
            if (strcmp(p[i], p[i+1]) > 0) {
               const char* temp = p[i];
               p[i] = p[i+1];
               p[i+1] = temp;
               swapped = 1;
            }
         }
      }
   }

   {
      size_t i;
      for (i=0; i<n; ++i)
         puts(p[i]);
   }

   free(p);
   return 0;
}

Upvotes: 0

David C. Rankin
David C. Rankin

Reputation: 84559

I'm not sure whether your desire to allocate and copy is for purpose of simple exercise, but in approaching the problem that way you wildly over-complicate what should be a simple pointer-swap to sort a. For example, why declare a as a 2D array of char instead of an array of pointers to char (e.g. char *a[] = {....})?

By declaring a as an array of pointers, you simply need to swap pointers in your sort -- no allocation or copying required, e.g.

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

int main (void) {

    char *a[] = {"milk","eggs","bread","cheese"};
    size_t n = sizeof a / sizeof *a, i, j;

    for(j = 0; j < n; j++)
        for(i = 0; i < n - 1 - j; i++)
            if(strcmp(a[i], a[i+1]) > 0) {        
                char *tmp = a[i];  
                a[i] = a[i+1];            
                a[i+1] = tmp;
            }

    for (i = 0; i < n; i++)
        printf ("a[%zu] : %s\n", i, a[i]);

    return 0;
}

Compile VS (cl.exe)

>cl /nologo /Wall /wd4710 /Ox /Foobj/bsarrayptr /Febin/bsarrayptr /Tc bsarrayptrs.c

Compile gcc

$ gcc -Wall -Wextra -pedantic -std=gnu11 -Ofast -o bin/bsarrayptr bsarrayptrs.c

Example Use/Output

C:\Users\david\Documents\dev\src-c\tmp>bin\bsarrayptr.exe
a[0] : bread
a[1] : cheese
a[2] : eggs
a[3] : milk

If your intent was just to perform an exercise using additional levels of indirection, copying and allocation, that's fine, but if you intent was to handle a alphabetical sort of a, then simply swapping pointers is a much more efficient approach.

Look things over and let me know if you have further questions.

Upvotes: 0

aditya rawat
aditya rawat

Reputation: 164

The problem is here

 for(i=0; i<3-j; i++)

j will iterate till it is less than 4, that means i will iterate till it is less than -1?

  1. i started from 0 and it is incremented by one.

  2. array index can never be equal to -1(because it starts from 0).

also, change the above line to this 

 for(i=0; i<(j); i++)

the code is fine.

Upvotes: 0

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 726639

The reason your program crashes is that you are trying to copy the content of a C string into an uninitialized pointer temp, causing undefined behavior.

Even if you fix this by supplying a buffer of appropriate length for the temp, you would get undefined behavior on copying longer strings into space allocated for shorter strings (e.g. when copying "cheese" into the space that has been allocated for "eggs"). Moreover, your current implementation currently has undefined behavior, too, because it fails to allocate enough space to accommodate null terminator of your strings.

A proper way of fixing this is to swap pointers, rather than using them to copy the content.

Upvotes: 1

Related Questions