1

Say you have a list of names of cities. Associated with each city is a state. When you are building the list, you want to keep it sorted in alphabetical order by city name. When the list is complete, you want to sort it by states. My question is, once you have sorted by the state's name, will the cities for a particular state still be in alphabetical order? Or will the list of cities for each state need to be resorted? Or is there another way to do this?

Chuck Pergiel
  • 151
  • 2
  • 14

3 Answers3

4

No, qsort is not required to be a stable sort.*

It sounds like you need to define a lexicographical comparator - i.e. have your comparator compare state first, and then only compare city if states are equal.

  • From the C99 standard:

[7.20.5.2] If two elements compare as equal, their order in the resulting sorted array is unspecified.

Oliver Charlesworth
  • 267,707
  • 33
  • 569
  • 680
  • A quick sort can be stable but it's require to be implemented in a special way. So it's would differs a little bit from quick sort. We could call that a qsort_stable :p. – Stargateur Jun 16 '17 at 17:17
  • 1
    And indeed you may sort on as many struct members as you wish. Work on the highest priority first, if unequal return the positive or negative `int`, otherwise check the next members in the same way, and so on. – Weather Vane Jun 16 '17 at 17:51
  • 1
    @Stargateur, its name notwithstanding, the standard library's `qsort()` function is in no way required to be implemented via the Quick Sort algorithm. Questions about `qsort()` therefore should not be interpreted as being about Quick Sort. – John Bollinger Jun 16 '17 at 18:00
  • Thanks for the citation in this answer. I had wondered why `qsort` can swap two elements when the comparator result is `0`. – Weather Vane Jun 16 '17 at 18:04
  • @WeatherVane C11 says "The following are unspecified: [...] The order of two elements that compare as equal in an array sorted by the qsort function (7.22.5.2)." – Stargateur Jun 16 '17 at 18:08
  • 2
    @Stargateur strangely, I have seen two equal elements swapped when there are *only* two elements. – Weather Vane Jun 16 '17 at 18:10
  • @JohnBollinger My bad, but I look the tag description is confuse, maybe you could update it. "qsort is a function that performs quicksort." "Use the [quicksort] tag instead for questions about quick-sort or self-written implementations." – Stargateur Jun 16 '17 at 18:25
4

... once you have sorted by the state's name, will the cities for a particular state still be in alphabetical order?

No. qsort() is not required to be stable. When elements equal each other, the order may change.

Or is there another way to do this?

Avoid returning 0 from the compare function. @Weather Vane

int fcmp_by_state_then_by_city(const void *a, const void *b) {
  const geo *ga = a; // assume array of geo
  const geo *gb = b; 
  int cmp = strcmp(ga->state, gb->state);
  if (cmp) return cmp;

  return strcmp(ga->city, gb->city);
}

int fcmp_by_city_then_by_state(void *a, void *b) {
  // like above with strcmp(ga->city, gb->city) first
}

A simple approach is to add another member to the geo type supplying a canonical order - the final tie-breaker - which could be the original index of the element in the original array. Another approach is to create an array of pointers to the elements of the array and sort with pointers to the original array using that 2nd level pointer as the tie-breaker.

int fcmp_by_state_then_by_index(const void *a, const void *b) {
  const geo *ga = a; // assume array of geo
  const geo *gb = b; 
  int cmp = strcmp(ga->state, gb->state);
  if (cmp) return cmp;
  return (ga->index > gb->index) - (ga->index < gb->index)
}

Using the addresses a,b as a final tie-breaker will not necessarily work. @chqrlie

If two elements compare as equal, their order in the resulting sorted array is unspecified.
C11 §7.22.5.2 4

@Oliver Charlesworth

chux - Reinstate Monica
  • 143,097
  • 13
  • 135
  • 256
  • 1
    If one wants more tie-breakers, see [NFL](http://www.nfl.com/standings/tiebreakingprocedures). ;-) – chux - Reinstate Monica Jun 16 '17 at 18:14
  • 1
    I'm afraid your tie-breaker does not work: comparing the pointers is meaningless as the array elements may be swapped without being compared to one another. To use this stability trick, you need an auxiliary array of pointers and sort that, breaking ties with a pointer comparison. – chqrlie Jun 16 '17 at 18:46
  • ...or a `struct` member that contains the original unsorted array index. – Weather Vane Jun 16 '17 at 18:50
  • @charlie Agreed - Rewritten. Been down that wrong path before. Time to re-learn that hole-in-the-road. – chux - Reinstate Monica Jun 16 '17 at 19:05
0

qsort itself is not required to be stable, and in many implementations is not, especially when implemented using the Quick Sort algorithm.

The is a simple way to work around this problem: if your system has mergesort(), this function does implement a stable sort with the same API as qsort().

Otherwise, you could borrow an implementation of merge sort and use it.

chqrlie
  • 131,814
  • 10
  • 121
  • 189