how to sort 3 values

Problem
You have 3 values (e.g. three numbers), and you need to sort them. It could be a simple interview question to warm you up :)

Solution
The easiest way might be to use the good ol’ bubble sort. It can be done manually, without loops, since we only have three numbers.

Three values (let’s call them A, B, and C) are sorted, if A <= B <= C. Thus, the pseudo code to sort them is the following:

if A > B: swap(A, B)
if B > C: swap(B, C)    # the largest value is now in C
if A > B: swap(A, B)    # A and B are also sorted now

And now, let’s see it in C:

#include <stdio.h>

int main(int argc, char *argv[])
{
    int a = 8;
    int b = 7;
    int c = 6;
    int tmp;

    /* sort them in asc. order */
    if (a > b) {
        tmp = a; a = b; b = tmp;
    }
    if (b > c) {
        tmp = b; b = c; c = tmp;
    }
    if (a > b) {
        tmp = a; a = b; b = tmp;
    }

    /* print result */
    printf("%d <= %d <= %d\n", a, b, c);

    return 0;
}

Output:

6 <= 7 <= 8

Links

• Bubble Sort (with animation)

Basic Data Structures and Algorithms in the Linux Kernel

http://luisbg.blogalia.com/historias/74062

Algorithm Complexity Analysis

A Gentle Introduction to Algorithm Complexity Analysis

“However, theoretical computer science has its uses and applications and can turn out to be quite practical. In this article, targeted at programmers who know their art but who don’t have any theoretical computer science background, I will present one of the most pragmatic tools of computer science: Big O notation and algorithm complexity analysis. As someone who has worked both in a computer science academic setting and in building production-level software in the industry, this is the tool I have found to be one of the truly useful ones in practice, so I hope after reading this article you can apply it in your own code to make it better. After reading this post, you should be able to understand all the common terms computer scientists use such as “big O”, “asymptotic behavior” and “worst-case analysis”.” (source)

Dictionary of Algorithms and Data Structures

see http://xlinux.nist.gov/dads/

Generate random numbers deterministically and non-deterministically

Problem
I wanted to compare the efficiency of some sorting algorithms. For this, I wrote a simple program that accepts a command-line parameter (the name of a sorting algorithm) and calls the specified algorithm on a large array containing random integers. Using the Unix “time” command I could do my tests.

However, if the array is filled up with different random numbers each time, the tests wouldn’t be fair. Thus, the array should contain random numbers that are generated in a deterministic way, i.e. each time I execute my little program, the array should be filled with the same numbers in the same order.

Generate random numbers deterministically
C snippet:

int UPPER = 10;

for (i = 0; i < 10; ++i) {
    printf("%d ", (int)(random() % UPPER + 1));
}

Full source code is here.

Python snippet:

UPPER = 10
random.seed(0)  # use a constant seed

for _ in range(10):
    print random.randint(1, UPPER),

Full source code is here. Doc on random.seed is here.

Sample output:

$ ./det.py
4 7 8 6 4 6 7 3 10 2
$ ./det.py
4 7 8 6 4 6 7 3 10 2

Generate random numbers non-deterministically
Now let’s see how to generate random numbers non-deterministically.

Note that this method is still deterministic since it uses the current time as its seed. If someone knows the time when you launched your program, (s)he could reproduce your “random” numbers. As John von Neumann said: “Any one who considers arithmetical methods of producing random digits is, of course, in a state of sin.”

C snippet:

int UPPER = 10;

srand((unsigned)time(NULL));   /* use current time as seed */

for (i = 0; i < 10; ++i) {
   printf("%d ", (int)(random() % UPPER + 1));
}

Full code is here.

Python snippet:

UPPER = 10

for _ in range(10):
    print random.randint(1, UPPER),

Full code is here.

Sample output:

$ ./non-det.py
2 4 4 10 6 9 4 3 2 7
$ ./non-det.py
5 8 10 2 10 10 1 10 4 5

Note
Notice the different behaviors of C and Python. By default, C uses the same seed, thus if you want “true randomness”, you must call srand. On the other hand, Python generates “true random” numbers by default and you must provide a constant seed if you want a determinsitic behavior.

_{Thanks to Temia E. for his (her?) help.}

Books on graphs and graph algorithms

http://stackoverflow.com/questions/510758/can-you-suggest-a-good-book-on-graphs-and-graph-algorithms

Links

• Graph Theory with Applications by J.A. Bondy and U.S.R. Murty (in HTML and PDF)
• Introduction to Algorithms
• Graph Theory
• Programming Challenges
• Introductory Graph Theory
• Data Structures and Network Algorithms