Algorithms in C

Robert Sedgewick

Mentioned 6

Defines and explores the implementation and figures of the algorithms required for various applications, offering commentary, descriptions, and exercises for developers, researchers, and students.

More on Amazon.com

Mentioned in questions and answers.

To follow the example of The Definitive C++ Book Guide and List for C Books here is a wiki post for organization.

A tag search for "C" and "Books" returns no complete book list results as of writing this question. That search is here.

This post is to providing QUALITY books and an approximate skill level. Maybe we can add a short blurb/description about each book that you have personally read / benefited from. Feel free to debate quality, headings, etc.

Reference Style - All Levels

Beginner

Intermediate

Above Intermediate

Uncategorized Additional C Programming Books

C Unleashed : is also a good book. Its not ideal or anything. But for intermediate programmers, its definitely worth practising programs written in this book.

I added The Standard C Library by P.J. Plauger. It contains complete source code to an implementation of the C89 standard library along with extensive discussion. It was very influential to my C programming style. As a library it is much more accessible than, say, STL.

Problem Solving and Program Design in C (6th Edition) is an intermediate level book. If you have other C Advanced books then this is not an ideal book to buy but its definitely worth going through once.

I think the knowledge you're looking for is to be found not in books about C but in books and articles about system design. These are fairly thin on the ground, unfortunately. You might consider

  • Abstraction and Specification in Program Development by Barbara Liskov and John Guttag (not the newer Java-based version by Liskov alone). It is an undergraduate text but has some ideas worth thinking about.

  • Books from the late 1970s and early 1980s by Yourdon and Myers on structured design (one is called Composite/Structured Design.

  • For an example of how to organize a big C project as a bunch of useful libraries, you can't beat C Interfaces and Implementations by Dave Hanson. Basically Hanson took all the code he'd written as part of building Icon and lcc and pulled out the best bits in a form that other people could reuse for their own projects. It's a model of good C programming using modern design techniques (including Liskov's data abstraction).

Beginner: Applications Programming in ANSI C, by Johnsonbaugh & Kalin

Intermediate: Data Structures - An Advanced Approach Using C, by Esakov and Weiss

Beginner

Intermediate

  • Algorithms in C by Robert Sedgewick: gives you a real grasp of implementing algorithms in C; very lucid and clear; you will probably throw away all your algorithms books and keep this one

Expert

I'd like to make an anti-recommendation. Under no circumstances should you read any books by Herbert Schildt. In particular, you should stay away from C: The Complete Reference.

Having read the same books, hopefully I can help with a few more:

And finally a good cookbook-like one from comp.lang.c contributors:

I am trying to write a 2d game engine in C (no c++). What are some good libraries that have generic data types I may need - for example queues, trees, maps, lists, and so on?

Not sure if this answer is what you're after, but a useful read on the subject is Sedgewick's "Algorithms in C"

HTH

What is the best place or a link to learn algorithms in C? How do you know when and where to use the implementation of algorithms by just looking into the problems?

Algorithms in C by Sedgewick is a great place to start the investigation. Once you are familiar with what algorithms are available and what the performance characteristics of each are, you'll be able to see where to use each of them.

Algorithms aren't necessarily tied to a specific language, just to clarify, so any algorithms book will work great as long as you can understand the concept being the data structure/algorithm.

That said, this seems like a good choice: Algorithms in C. I have the C++ equivalent on my shelf.

There is also a book that seems language agnostic (correct me if I'm wrong) called Data Structures & Algorithm's, though I hear it's a bit dated, so you'll miss out on more recent structures.

Don't forget the internet has a plethora of information available to you. However, books are usually better for these sorts of things. This is because internet resources tend to focus on one thing at a time. For example, you need to understand what Big-O notation is before you can understand what it means when we say a List has O(1) [constant time] removal.

A book will cover these things in the correct order, but an internet resource will focus on either Big-O notation or data structures, but often won't easily connect the two.


When it comes to using it, you'll mostly make the connection when it comes to what you'll be doing with the data.

For example, you might want a vector (array) if you just need ordered elements, but if you need ordered elements and removal from any place (but can sacrifice random access), then a list would be more appropriate, due to it's constant-time removal.

I read Pointers on C by Kenneth Reek recently. I thought I was pretty well versed in C, but this book gave me a few epiphanies, despite being aimed at beginners. The code examples are things of beauty (but not the fastest code on a x86-like CPU). It provide good implementations of many of the most common algorithms and data-structures that are in use, with excellent explanations about why they are implemented as they are (and sometimes code or suggestions for alternative implementations).

On the same page as your question: patterns for creating reusable code in C (that is what we all want, isn't it?), C Interfaces and Implementations: Techniques for Creating Reusable Software, by David R. Hanson. It has been a few years since I read it, and I don't have a copy to verify what I recall is correct, but if I remember correctly it deals with how to create good C API:s to data structures and algorithms, as well as giving example implementations of some of the most common algorithms.

Of topic: As I have mostly written throw-away programs in C for private use, this one helped me get rid of some bad coding habits as well as being an excellent C reference: C: A reference Manual. Reminds me that I ought to buy that one.

I want to fundamentally learn algorithm efficiency by self study (hopefully both in how a program can make best use of hardware and in designing an algorithm). I wanted to know about some good books on this topic. I write my programs in c.

I'll recommend the book Algorithms in C, Parts 1-4: Fundamentals, Data Structures, Sorting, Searching, the author Robert Sedgewick has a magic power to explain hard things easily understood. The book though not well edited, is the best reference on data structure and algorithms in C I've read.

Quoting from editorial reviews:

Highlights

  • Expanded coverage of arrays, linked lists, strings, trees, and other basic data structures Greater emphasis on abstract data types (ADTs) than in previous editions
  • Over 100 algorithms for sorting, selection, priority queue ADT implementations, and symbol table ADT (searching) implementations
  • New implementations of binomial queues, multiway radix sorting, Batcher's sorting networks, randomized BSTs, splay trees, skip lists, multiway tries, and much more
  • Increased quantitative information about the algorithms, including extensive empirical studies and basic analytic studies, giving you a basis for comparing them
  • Over 1000 new exercises to help you learn the properties of algorithms

Whether you are a student learning the algorithms for the first time or a professional interested in having up-to-date reference material, you will find a wealth of useful information in this book.

As a reader, I'll say it deserves this accomplishment.

What is a popular/good data structures and algorithm analysis book for C other than Data Structures, Algorithms, and Software Principles in C by Thomas Standish.

Algorithms in C (Sedgewick) is also good

The Algorithm Design Manual is very readable

I'm studying the Shell sort from Sedgewick Algorithms in C part 1-4 on p172.

I use size (the length of array), not l and r (start and end); so my code is

int i,j,h;
int key;
for( h=1;h<=(size-1)/9;h=h*3+1);
for(;h>0;h/=3)
{
    for(i=h;i<size;i++)
    {
        key=num[i];
        j=i;
        while(j>=h&&key>num[j-h];j-=h)
        {
            num[j]=num[j-h];
        } 
        num[j]=key;
    }
}

I know all of this. I read TAOCP. I know 1, 4, 13, … is the best sequence (comparable). But in this position, my code has

for(h=1;h<size;h=h*3+1);

My question is: why did he write h<(size-1)/9?

What does the '/9' mean?

The loop:

for (h = 1; h < size; h = h * 3 + 1)
    ;

overshoots the size of the array most of the time. The alternative loop keeps the gap within range.

You can see this for yourself with a trivial test program like this:

#include <stdio.h>

static inline int hs_gap9(int size)
{
    int h;
    for (h = 1; h <= (size - 1) / 9; h = h * 3 + 1)
        ;
    return h;
}

static inline int hs_gap3(int size)
{
    int h;
    for (h = 1; h < size; h = h * 3 + 1)
        ;
    return h;
}

int main(void)
{
    for (int i = 1; i < 100; i++)
        printf("Size: %3d; gap9 = %d; gap3 = %d\n", i, hs_gap9(i), hs_gap3(i));
    return 0;
}

Sample output:

Size:   1; gap9 =   1; gap3 =   1
Size:   2; gap9 =   1; gap3 =   4
Size:   3; gap9 =   1; gap3 =   4
Size:   4; gap9 =   1; gap3 =   4
Size:   5; gap9 =   1; gap3 =  13
Size:   6; gap9 =   1; gap3 =  13
Size:   7; gap9 =   1; gap3 =  13
Size:   8; gap9 =   1; gap3 =  13
Size:   9; gap9 =   1; gap3 =  13
Size:  10; gap9 =   4; gap3 =  13
Size:  11; gap9 =   4; gap3 =  13
Size:  12; gap9 =   4; gap3 =  13
Size:  13; gap9 =   4; gap3 =  13
Size:  14; gap9 =   4; gap3 =  40
Size:  15; gap9 =   4; gap3 =  40
Size:  16; gap9 =   4; gap3 =  40
…
Size:  34; gap9 =   4; gap3 =  40
Size:  35; gap9 =   4; gap3 =  40
Size:  36; gap9 =   4; gap3 =  40
Size:  37; gap9 =  13; gap3 =  40
Size:  38; gap9 =  13; gap3 =  40
Size:  39; gap9 =  13; gap3 =  40
Size:  40; gap9 =  13; gap3 =  40
Size:  41; gap9 =  13; gap3 = 121
Size:  42; gap9 =  13; gap3 = 121
Size:  43; gap9 =  13; gap3 = 121
…
Size:  97; gap9 =  13; gap3 = 121
Size:  98; gap9 =  13; gap3 = 121
Size:  99; gap9 =  13; gap3 = 121

As you can see, the 'gap3' algorithm returns an initial value of h that is larger than the size of the array. The 'gap9' algorithm returns an initial value of h that is smaller than the size of the array. This saves a little overhead on the loops (saves one iteration of the outer loop, where the middle loop exits on the first cycle without touching the inner loop.