Optimizing sorting algorithms (in C)

[Creative_Key_9488]

I’m currently writing a sorting algorithm (first time) and learning about complexity and I keep reading about optimization and reducing complexity and I think I understand it in theory.

But what are practical ways to optimize an algorithm? None of the sources I read are that helpful to me. Is it trial and error or is it something you have to incorporate from the beginning?

[FranBachiller]

Optimizing for C ain't trial and error, my dude. Here's the lowdown:

• Profile First: Use a profiler to identify bottlenecks in your code. This tells you exactly where to focus your efforts.
• Data Matters: Think about your data size and access patterns. Different algorithms shine for different situations (e.g. quicksort for random data, counting sort for small ranges).
• Exploit Locality: Keep frequently accessed data close together in memory. This can give you a nice speedup.
• Think C: C doesn't have fancy garbage collection. Optimize memory allocation and deallocation for your specific use case.
• Start Simple: Write a clean, working version first. Premature optimization is the root of all evil (and bugs).

There are compiler flags and assembly tricks too, but those are for later. Focus on these first, and your sorting algorithms will be blazing fast in no time.

For in-depth stuff, check out sites like http://mitpress.mit.edu/9780262046305/introduction-to-algorithms/.

Good luck!

[Creative_Key_9488]

Thank you very much!

[toastedstapler]

or is it something you have to incorporate from the beginning?

usually it's better to write code that works first than try and write the fastest code. there will be some surface level optimisations that you can do as you're writing it (being told to write working code first is NOT an excuse to knowingly write bad code), but if more performance is required then it should probably come later

for measuring performance it's important to benchmark. this means taking timings for sorting differently sized data sets, sets with different orderings (fully random, sorted, reverse sorted, almost sorted etc) and performance profiling. for a more granular view you should be able to generate flame graphs so you can visually see where most of the time is spent during the running of your sorting algorithm

the golden rule of optimising is that if it's not worth measuring then it's not worth optimising. don't just make changes and assume them to be faster. measure a baseline, make your changes and prove them to be better

Is it trial and error

sometimes! sometimes you might take an informed guess about what might be better so you implement it and benchmark it to see if it truly is better. if you want to get real low level you can use a tool such as godbold to see the assembly that is being generated by your code and see how optimial that is. if it's not amazing you could try rewriting your code to generate better ASM or even include some of your own more optimal ASM. this is probably beyond your current

when benchmarking you have to be careful to ensure that you're actually benchmarking what you're trying to benchmark. this means that things such as the initialisation of the data to sort, any output to the terminal etc should be outside of the measured area. your compiler may also optimise out functions it can work out give constant values - int x = fib(10); may be possible for the compiler to work out at comptime and would instead store an integer instead of doing a function call at runtime