Sorting an array by using pointer arithmetic

Question

I want to sort an array of structs in C, but using pointer arithmetic. My solution is the following:

#include <stdio.h>

typedef struct{
    char* brand;
    double cost;
}Car;


void printA(Car * arr, int size);
void sort(Car * arr, int size);


void printA(Car* v,int s){
    int i=0;
    Car* p;
    for (p=&v[0];p<&v[3];p++){
        printf("%s %lf \n",p->brand, p->cost);
    }
}

void sort(Car* v,int s){
   Car *i,*j,*temp,*k;
   for (i=&v[0]; i<&v[s]; i++)
   {
    for (j=&v[0] ; j<&v[s]; j++)
    {
      k=j+1;
      if (j->cost > (j+1)->cost)
      {
        temp = j;
        j = k;
        k = temp;
      }
    }
   }
}

int main() {
  Car v[3];
  Car a = {.brand = "bmw", .cost = 34.56 };
  Car b = {.brand = "vw", .cost = 47.35 };
  Car c = {.brand = "ford", .cost = 45.23 };
  v[0] = a;
  v[1] = b;
  v[2] = c;
  printA(v,3);
  sort(v,3);
  printA(v,3);
  return 0;
}

The issue is that my resulting array does not get sorted. I believe that I should also swap the cost, but I am not entirely sure. What can I try next?

Hint: You're reassigning a pointer, not the value it points to. — tadman
– tadman, Commented May 28, 2021 at 23:08
thanks @tadman, I have tried by changing something like temp->cost = j->cost, but still I got some issues. — Little
– Little, Commented May 28, 2021 at 23:15

Schwern · Accepted Answer · 2021-05-29 00:06:13Z

The problem is how you're doing the swap.

        temp = j;
        j = k;
        k = temp;

These are all Car *, pointers. All those do is swap the memory address between the variables which are then overwritten by the next iteration of the loop.

You need to swap the contents of the memory.

        Car temp = *j;  // Store the content of j
        *j = *k;        // Replace the content of j with the content of k
        *k = temp;      // Replace the content of k with the saved content of j

That fixes the swap. For the sort to work, you want to compare i to j, not j to j+1.

// size_t is the appropriate type for array indexes.
// See https://en.cppreference.com/w/c/types/size_t
void sort(Car v[], size_t s) {
    // Declaring end makes the code easier to follow.
    //
    // Declare variables individually and in the narrowest
    // possible scope to make the code easier to follow
    // and to avoid accidentally reusing variables.
    Car *end = &v[s-1];

    // Check i <= &v[s-1] to avoid referencing memory
    // we do not own. Probably not an issue since we never
    // access the memory, but let's be safe.
    for (Car *i=&v[0]; i <= end; i++)
    {
        // Start at i + 1. Everything before i has been
        // sorted, and there's no need to compare i to i.
        for (Car *j=i+1; j <= end; j++)
        {
            // Compare i against j.
            if (i->cost > j->cost)
            {
                Car temp = *i;
                *i = *j;
                *j = temp;
            }
        }
    }
}

In production you would not write your own sort function. You'd write a Car comparison function and feed it to an exiting sorting function like qsort.

int compare_cars(const void* _a, const void* _b) {
    const Car *a = (const Car*)_a;
    const Car *b = (const Car*)_b;

    if( a->cost < b->cost )  {
        return -1;
    }
    else if( a->cost > b->cost ) {
        return 1;
    }
    else {
        return 0;
    }
}

qsort(v,s,sizeof(Car), compare_cars);

paulsm4 · Accepted Answer · 2021-05-28 23:37:12Z

-1

Suggested alternatives:

#include <stdio.h>

typedef struct{
    char* brand;
    double cost;
}Car;

// Since you declared function prototypes at the top, you can put the implementations anywhere    
void printA(Car * arr, int size);
void sort(Car * arr, int size);

int main() {
  // Simplify array initialization
  Car v[3] = {
    { "bmw", .34.56 },
    { "vw", 47.35 }
    { "ford", 45.23 }
  };

  printA(v,3);
  sort(v,3);
  printA(v,3);

  return 0;
}

void printA(Car* v, int size){
    // Simplify array element access
    for (int i=0; i < size; i++){
        printf("%s %lf \n", v[i].brand, v[i].cost);
    }
}

void sort(Car* v, int size) {
   // Iterate using indexes (i, j, k); swap array values
   Car temp;
   int k;
   for (i=0; i < size; i++) {
     for (j=0; j < size; j++) {
       k=j+1;
       if (v[j].cost > v[k].cost) {
         temp = v[j];
         v[j] = v[k];
         v[k] = temp;
       }
     }
   }
}

I have not test-compiled, I have not verified your sort algorithm. But I hope this will give you a few useful tips...

answered May 28, 2021 at 23:37

paulsm4

123k23 gold badges175 silver badges245 bronze badges

1 Comment

Schwern Over a year ago

The OP specifically wants to do it with pointer arithmetic.

Collectives™ on Stack Overflow

Sorting an array by using pointer arithmetic

2 Answers 2

Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related