Thread: 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!

Nobody has any suggestions :??

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

Originally Posted by jimblumberg

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

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