CODEWITHSUNDEEP
carrayssortingstructinsertion-sort
hwang hyungchae
hwang hyungchae

Reputation: 39

tried to sort data in a struct, it sorts right but one last line is wrong

 void sort(loc_sos_t a[], int array_size)
{
int i, j;
double index;
loc_sos_t index_block;
for (i = 1; i < array_size; i++){

    index = a[i].sos;
    index_block= a[i];
    for (j = i; j > 0 && a[j-1].sos > index; j--){
        a[j].sos = a[j-1].sos;
    }

    a[j].sos = index;
    a[j]= index_block;
}
}

so this snippet is supposed to take a struct and integer as its arguments. the struct is an array. at each index, the struct contains x,y coordinates and a value for watts. the snippet sorts the watts values in ascending order and bring their corresponding x,y coordinates to its new position. 

input
30.0 meters east, 70.0 meters north, power 0.0045 watts
53.0 meters east, 63.0 meters north, power 0.0006 watts
36.5 meters east, 27.0 meters north, power 0.0005 watts
70.0 meters east, 25.0 meters north, power 0.0015 watts
20.0 meters east, 50.0 meters north, power 0.0008 watts

output
36.5 meters east, 27.0 meters north, power 0.0005 watts
53.0 meters east, 63.0 meters north, power 0.0006 watts
20.0 meters east, 50.0 meters north, power 0.0008 watts
70.0 meters east, 25.0 meters north, power 0.0015 watts
30.0 meters east, 70.0 meters north, power 0.0045 watts

wrong output generated by wrong code
36.5 meters east, 27.0 meters north, power 0.0005 watts
53.0 meters east, 63.0 meters north, power 0.0006 watts
20.0 meters east, 50.0 meters north, power 0.0008 watts
70.0 meters east, 25.0 meters north, power 0.0015 watts
20.0 meters east, 50.0 meters north, power 0.0045 watts

the last line of my output is wrong. please help. i have no idea why only one line is wrong.

Upvotes: 0

Views: 64

Answers (2)

Amit Sharma
Amit Sharma

Reputation: 2067

Your code is logically incorrect. If you see the output per iteration; you will have the following output.

53.000000  63.000000  0.000600
53.000000  63.000000  0.004500
36.600000  27.000000  0.000500
70.000000  25.000000  0.001500
20.000000  50.000000  0.000800
----------------------------
36.600000  27.000000  0.000500
53.000000  63.000000  0.000600
36.600000  27.000000  0.004500
70.000000  25.000000  0.001500
20.000000  50.000000  0.000800
----------------------------
36.600000  27.000000  0.000500
53.000000  63.000000  0.000600
70.000000  25.000000  0.001500
70.000000  25.000000  0.004500
20.000000  50.000000  0.000800
----------------------------
36.600000  27.000000  0.000500
53.000000  63.000000  0.000600
20.000000  50.000000  0.000800
70.000000  25.000000  0.001500
20.000000  50.000000  0.004500
----------------------------

I think @hwang hyungchae can easily guess where you are wrong. The following code produce the desired output.

void sort(loc_sos_t a[], int array_size)
{
   int i, j;
   double index;
   struct loc_sos_t index_block;

   for (i = 0; i < array_size; i++){
    index = a[i].sos;
    for (j = i-1; j > 0 && a[j-1].sos > index; j--){
       index_block= a[j-1];
       a[j-1]=a[i];
       a[i]=index_block;
    }
   }
}

Upvotes: 1

Cristian Greco
Cristian Greco

Reputation: 2596

This is the code for your insertion sort with minimal fix for the copy of array values (the logic is right, you just messed up the copy of the elements of the array):

void sort(loc_sos_t a[], int array_size) {
    int i, j;
    double index;
    loc_sos_t index_block;
    for (i = 1; i < array_size; i++) {
        index = a[i].sos;
        index_block = a[i];
        for (j = i; j > 0 && a[j - 1].sos > index; j--) {
            a[j] = a[j - 1];
        }
        a[j] = index_block;
    }
}

Anyway, you may want to use the more efficient qsort from standard library:

int cmplocsos(const void *p1, const void *p2) {
    double s1 = ((loc_sos_t*)p1)->sos;
    double s2 = ((loc_sos_t*)p2)->sos;
    return (s1 > s2) - (s1 < s2);
}

qsort(&arr[0], array_size, sizeof(loc_sos_t), cmplocsos);

Upvotes: 1

Related Questions