0

I notice that <stdlib.h> only includes qsort which is not stable. Therefore I cannot sort a composite data structure along different columns.

Is there any standard (POSIX/C11) and stable sorting algorithms in C?

nowox
  • 25,978
  • 39
  • 143
  • 293
  • 3
    Not as far as I know, but you might find [this](https://stackoverflow.com/questions/48135394/using-qsort-for-stable-sort) interesting. – Jabberwocky May 18 '20 at 06:21
  • I am confused by the title of your question. You are asking about the C standard library not about the C language, which is different. – JoelFan May 18 '20 at 06:26
  • 3
    @JoelFan Unless you're a language lawyer, or dealing with non-hosted implementations, the distinction is rarely significant. – Barmar May 18 '20 at 06:44
  • @Barmar I didn't get your point – nowox May 18 '20 at 07:09
  • @nowox In most contexts the distinction between the standard library and the language itself is not important, so JoelFan's comment is not really helpful. – Barmar May 18 '20 at 07:11
  • @Barmar.... if you say so... I sure would not hire someone who didn't know the difference – JoelFan May 18 '20 at 18:48
  • @JoelFan Unless you're doing kernel programming, why would the difference matter? Does anyone really care that `printf()` isn't part of the language, but is just a library function? You can rely on it being there just as much as `if` and `while`. – Barmar May 18 '20 at 18:58
  • @Barmar, there may not be many situations where "it makes a difference" to know such things, but it's hard to be a good developer when you don't understand "what's really going on" in general. It's similar to not knowing the difference between the heap and the stack or thinking that there's such a thing as a "JSON object". Sure it usually "doesn't matter", but good developers know these things. – JoelFan May 18 '20 at 19:14
  • 1
    @JoelFan I'd consider it an "expert programmer" thing -- I'm sure you can do just fine as a competent programmer without knowing these details. – Barmar May 18 '20 at 19:39

1 Answers1

-4

Standard C library provides qsort() that can be used for sorting an array. As the name suggests, the function uses QuickSort algorithm to sort the given array. Following is prototype of qsort()

void qsort (void* base, size_t num, size_t size, 
            int (*comparator)(const void*,const void*));

The key point about qsort() is comparator function comparator. The comparator function takes two arguments and contains logic to decide their relative order in sorted output. The idea is to provide flexibility so that qsort() can be used for any type (including user defined types) and can be used to obtain any desired order (increasing, decreasing or any other).

The comparator function takes two pointers as arguments (both type-casted to const void*) and defines the order of the elements by returning (in a stable and transitive manner).

Still if you get any doubt fell free to ask.

Aditya Shende
  • 114
  • 6
  • Yep qsort is great, but qsort is unstable :( – nowox May 18 '20 at 18:02
  • In the context of sorting, *stable* means that, when two elements are equal in sort order, their order in the list is preserved. This may matter when records are being sorted by one field but contain others that distinguish them. – Eric Postpischil May 18 '20 at 18:17