• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

How to Efficiently Sort a Large Array of Structs in C?

 
Greenhorn
Posts: 10
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I have a large array of structs, and I need to sort them based on a specific field within the struct. What's the most efficient way to do this in C? Should I use a custom sorting function or a standard library function like qsort? Any tips for optimizing the sorting process, especially when dealing with a large dataset?"

This question addresses a common task in C programming and invites experienced developers to share their insights on optimizing sorting algorithms and techniques.
 
Saloon Keeper
Posts: 15535
364
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Well, first you need to answer some important questions:

  • Do you know whether the data could already be partially sorted?
  • Does the sort need to be stable?
  • Do you need to sort elements as they enter your application, or are all elements already available in memory?
  • Can you use an arbitrary amount of memory in addition to the memory needed to hold the elements?
  •  
    Rancher
    Posts: 508
    15
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    Also, what's the priority - time efficiency (speed), memory efficiency, a combination of the 2, and/or something else?
     
    Marshal
    Posts: 79242
    377
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator

    Lucky Kumar wrote:. . . Should I use . . . a . . . function like qsort? . . .

    To add to the discussion, make sure you know what qsort does before you use it.
     
    Saloon Keeper
    Posts: 27809
    196
    Android Eclipse IDE Tomcat Server Redhat Java Linux
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    Standard procedure in C is that you provide a comparator function that returns -1, 0, or +1 depending on whether 2 items fed to it compare low, equal or high. If this looks like something you've seen in Java Comparators, it's no accident. Java knew a good thing and stole it.

    If your data is entirely in-memory, there are about 5 standard sorts that come with the base C library packages, corresponding to the major sorts detailed in Donald Knuth's Art of Computer Programming.. Something like bubble, shell, heap, quick, and I think I forgot one.

    Each of those sorts can be invoked with a simple function call that you pass pointers to your data and comparator function to. Everything else is automatic. The logic of the sorts is extremely efficient, so the overall efficiency of the sort depends on the data being sorted. Stuff that's already mostly sorted will perform very badly on quicksort but much better on heap or shell sorts. Stuff that's mostly random performs best on quick or heap sorts.

    If the data is too large for RAM, then you have to get more creative. If you're lucky there's an external sort utility program that can do that for you. In fact, there was a strong commercial market for third-party external sorting programs on IBM mainframes in the 1960s and 1970s.
     
    Campbell Ritchie
    Marshal
    Posts: 79242
    377
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator

    Tim Holloway wrote:. . . Java knew a good thing and stole it.

    You can tell from some of the functions in the earlier utility classes that Java® stole lots and lots from C. It even stole names, like ceil().

    . . . Something like bubble, shell, heap, quick, and I think I forgot one. . . .

    Merge sort?
     
    Consider Paul's rocket mass heater.
    reply
      Bookmark Topic Watch Topic
    • New Topic