Thread: Array sort with qsort, by using two criteria?

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

    Array sort with qsort, by using two criteria?

    Hello!

    I already posted one question related to my quick sort problem, but since it is solved and I have a new one, I am starting a new thread. 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!


    Which works fine, with following code:

    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) {
            do ++i; while (a[i] >= pivot && i < r);
            do --j; while (a[j] < pivot);
    
            if (i >= j) break;
                switch_pos(&a[i], &a[j]);
                switch_pos(&array_order[i], &array_order[j]);
        } 
        switch_pos(&a[l], &a[j]);
        switch_pos(&array_order[l], &array_order[j]); 
       return j;
    }
    
    void switch_pos(int *one, int *two) {
        int temp = *one;
        *one = *two;
        *two = temp;
    }


    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;
    }

    But now I would like to add the second criteria: if two numbers of my list are equal, then I want the them to be sorted according to their position in array_ordered, which means if I have:

    9 9
    [0] [5]

    They stay the same, but if they are like:

    9 9
    [5] [0]

    i would like to swap them (for some reasons..doesnt matter why).

    I tried to add the criteria : (if (a[i] != a[j] || (a[i] == a[j] && array_order[i] > array_order[j]))) before calling switch_pos, but it is not working since sometimes you swap two numbers like:

    11 9 15 9 <= here the 11 and 15 are swapped,

    but the two 9's will never be swapped <=> compared.

    Does someone have some suggestion how could I do this?? I mean I could run it again with the array_order on the first parameter position, but this would increase my runtime enormously!

  2. #2
    Registered User
    Join Date
    May 2014
    Posts
    69
    Nobody has any suggestions :??

  3. #3
    Registered User
    Join Date
    May 2010
    Posts
    4,480
    If you really want to maintain the order of numbers that are equal you'll probably want a different sorting function. The documentation I found for qsort states:

    If two members compare as equal, their order in the sorted array is undefined.

    Jim

  4. #4
    Registered User
    Join Date
    May 2014
    Posts
    69
    Quote Originally Posted by jimblumberg View Post
    If you really want to maintain the order of numbers that are equal you'll probably want a different sorting function. The documentation I found for qsort states:

    Jim
    Hmm ok, I thought to use sort since it has a good worst case runtime, and stuff like bubble sort is quadratic so I don't know which one is my sorting algorithm i should use :S

  5. #5
    Registered User
    Join Date
    May 2009
    Posts
    3,747
    You can use qsort to sort with two indexes; you just have to re-write the compare function to add the second index rule.

    Note: from what you posted I have no idea what that rule is.

    Edit: Its been about 15 years since I last used qsort; but, the info should be correct.

    Tim S.
    Last edited by stahta01; 09-26-2014 at 08:24 AM.
    "...a computer is a stupid machine with the ability to do incredibly smart things, while computer programmers are smart people with the ability to do incredibly stupid things. They are,in short, a perfect match.." Bill Bryson

  6. #6
    Registered User
    Join Date
    May 2010
    Posts
    4,480
    There are other stable sorts besides bubble sort, for example insertion sort, maybe you should search the net for "stable sort"? And as stated above it should be possible to make qsort() a stable sort by modifying the compare function.

    But one question to ask yourself, is it really necessary that your sort be stable?


    Jim

  7. #7
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    You have the original indexes, because you are in fact sorting those.
    So your next step is to rewrite this such that the two comparisons against pivot both call a function called compare.
    Code:
            do ++i; while (a[i] >= pivot && i < r);
            do --j; while (a[j] < pivot);
    The compare function must compare both the values and if equal then also the indexes.
    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. Use qsort() to sort array of pointers to struct
    By VIgnotam in forum C Programming
    Replies: 4
    Last Post: 04-04-2012, 06:42 PM
  2. Replies: 9
    Last Post: 08-23-2010, 02:31 PM
  3. Using qsort to sort an array of strings
    By MSF1981 in forum C Programming
    Replies: 31
    Last Post: 05-17-2009, 01:31 AM
  4. using qsort to sort an array of strings
    By bobthebullet990 in forum C Programming
    Replies: 6
    Last Post: 11-25-2005, 08:31 AM
  5. Replies: 4
    Last Post: 09-10-2005, 01:07 PM