# Thread: Sort array and save the new order of elements

1. ## Sort array and save the new order of elements

So I try to sort an array with qsort and then save the new order, so this means if I have a list like:

4 3 7 2
   ,

after sorting it becomes:

2 3 4 7
    <== this is what I want to have!

Code:
```void qsort_my(int *a, int l, int r, int *array_order)
{
int j;
if( l < r )
{
j = split( a, l, r, array_order);
qsort_my( a, l, j-1, array_order);
qsort_my( a, j+1, r, array_order);
}
}

int split(int *a, int l, int r, int *array_order) {

int pivot, i, j, t;
pivot = a[l];
i = l; j = r+1;
int switch_pos_temp;
while( 1)
{
while( a[i] <= pivot && i <= r ) do ++i;
while( a[j] > pivot ) do --j;
if( i >= j ) break;

t = a[i];       switch_pos_temp = i;
a[i] = a[j];    array_order[i] = j;
a[j] = t;       array_order[j] = switch_pos_temp;
}
t = a[l];      switch_pos_temp = l;
a[l] = a[j];   array_order[l] = j;
a[j] = t;      array_order[j] = switch_pos_temp;

return j;
}```

But my problem is that the list gets sorted, but the indexes do strange stuff. When I run with this list:

4 8 14 1 2 1 22 12 2 14
Pos: 0 1 2 3 4 5 6 7 8 9

I get:
1 1 2 2 4 8 12 14 14 22
Pos: 1 0 1 0 0 5 7 6 5 6

And with some printfs I noticed, the first two calls of split it is fine but then strange things start to happen, somebody have any suggestion what I do wrong? 2. The actual printf calls would be nice, as would more info on these "strange things" that start to happen. What is strange about them, what do you expect and how do they differ? Also, it would be immensely helpful if you provided enough code for us to compile and run your sort routines. Make sure to provide all required headers, struct and other definitions, code to get input and print output, and a main function. It's often much easier for us to compile this and run it through a debugger, then to analyze by hand. 3. Code:
```#include <stdio.h>
#include <stdlib.h>
#include <dirent.h>
#include <string.h>

int main(int argc, char** argv) {

int tot = 10;   int ini;
int*list;
list = malloc(sizeof(int)*tot);

list = 4;list = 8; list = 14; list = 1; list = 2;
list = 1;list = 22; list = 12; list = 2; list = 14;

int *array_ordered;
array_ordered = malloc(sizeof(int)*tot);
for(ini = 0; ini < tot; ini++) array_ordered[ini] = ini;
qsort_my(list, 0, tot-1, array_ordered);

free(list); free(array_ordered);
return 0;
}```
Whell what happens is, so this is just how the array ordered is switched, at some point it doesnt make any sense whats happening: (this are not the numbers! just how the positions are switched, the numbers so the list is sorted just fine!)

0 8 2 3 4 5 6 7 1 9
0 8 5 3 4 2 6 7 1 9
4 8 5 3 0 2 6 7 1 9 <== until here is fine
3 8 5 0 0 2 6 7 1 9
3 2 1 0 0 2 6 7 1 9
1 0 1 0 0 2 6 7 1 9
1 0 1 0 0 2 9 7 1 6
1 0 1 0 0 8 9 7 5 6
1 0 1 0 0 5 9 7 5 6
1 0 1 0 0 5 7 6 5 6
1 0 1 0 0 5 7 6 5 6 4. Oh yes and the do's in my first post are just typos!line 20, 21 5. It would be simpler to sort array_order, using a[array_order[...]] for the compares and pivot points. Then afterwards, you can reorder or copy a according to array_order. The copy is simple, using i to index through the array, b[i] = a[array_order[i]]; . The in place reorder involves a variation of cycle sort (vA is the array, vI is the array of sorted indices):

Code:
```void reorder(vector<int>& vA, vector<size_t>& vI)
{
size_t i, j, k;
int t;
for(i = 0; i < vA.size(); i++){
if(i != vI[i]){
t = vA[i];
k = i;
while(i != (j = vI[k])){
// every move places a value in it's final location
vA[k] = vA[j];
vI[k] = k;
k = j;
}
vA[k] = t;
vI[k] = k;
}
}
}``` 6. Originally Posted by rcgldr It would be simpler to sort array_order, using a[array_order[...]] for the compares and pivot points. Then afterwards, you can reorder or copy a according to array_order. The copy is simple, using i to index through the array, b[i] = a[array_order[i]]; . The in place reorder involves a variation of cycle sort (vA is the array, vI is the array of sorted indices):

Code:
```void reorder(vector<int>& vA, vector<size_t>& vI)
{
size_t i, j, k;
int t;
for(i = 0; i < vA.size(); i++){
if(i != vI[i]){
t = vA[i];
k = i;
while(i != (j = vI[k])){
// every move places a value in it's final location
vA[k] = vA[j];
vI[k] = k;
k = j;
}
vA[k] = t;
vI[k] = k;
}
}
}```

Yes well I removed the error by just introducing a separate function for swap:

Code:
```void switch_pos(int *one, int *two) {

int temp = *one;
*one = *two;
*two = temp;
}``` 7. Trying to see what's going on with 10 items can be a little hard. It's a lot easier to debug the problem if you find the smallest possible case where it doesn't work. I.e.
Does it work with 0 items? (sometimes that even crashes)
Does it work with 1 item?
Does it work with 2 items that are in the correct order?
Does it work with 2 items that are not in the correct order?
Does it work with 3 items... Popular pages Recent additions 