Thread: Sort array and save the new order of elements

  1. #1
    Registered User
    Join Date
    May 2014
    Posts
    69

    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
    [0] [1] [2] [3],

    after sorting it becomes:

    2 3 4 7
    [3] [1] [0] [2] <== 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. #2
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,907
    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. #3
    Registered User
    Join Date
    May 2014
    Posts
    69
    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[0] = 4;list[1] = 8; list[2] = 14; list[3] = 1; list[4] = 2;
        list[5] = 1;list[6] = 22; list[7] = 12; list[8] = 2; list[9] = 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. #4
    Registered User
    Join Date
    May 2014
    Posts
    69
    Oh yes and the do's in my first post are just typos!line 20, 21

  5. #5
    Registered User
    Join Date
    Apr 2013
    Posts
    1,649
    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. #6
    Registered User
    Join Date
    May 2014
    Posts
    69
    Quote Originally Posted by rcgldr View Post
    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. #7
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    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...
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Sort and count frequency of array elements.
    By Nurlana in forum C++ Programming
    Replies: 12
    Last Post: 10-25-2012, 11:50 PM
  2. Replies: 8
    Last Post: 02-10-2010, 01:28 PM
  3. Sort an Array in Ascending Order ?
    By Coding in forum C++ Programming
    Replies: 5
    Last Post: 01-09-2008, 08:32 PM
  4. printing array elements in ascending order
    By galmca in forum C Programming
    Replies: 29
    Last Post: 10-24-2004, 11:24 PM
  5. Joining array elements and save in variable.
    By Nutshell in forum C Programming
    Replies: 12
    Last Post: 01-12-2002, 01:06 AM