Calculating the sum of all numbers
≤ n
// Return the sum of all values from 1 to n.
unsigned long long add_to(unsigned n) {
unsigned long long sum = 0;
for (unsigned i = 1; i <=n; ++i) {
sum += i;
}
return sum;
}
What is wrong with the above naive implementation?
The asymptotic performance is
// Return the sum of all values from 1 to n.
unsigned long long add_to(unsigned n) {
return (unsigned long long) ((n / 2.0 * n) + (n / 2.0));
}
Which impact can
clang sum_to.c -o sum_to
time ./sum_to n
time ./sum_to 1
Despite computers being faster than ever, why are data structures and algorithms still important, even more so than in the past?
Because computers have to deal with larger amounts of data.
Computation time costs energy
Repeatedly step through the list, compare adjacent elements and swaps them
Bubble-sort with Hungarian ("Csángó") folk dance
Exercise: implement the bubble sort algorthm
void bsort(int* array, size_t cnt)
Although simple, it is not used in practice due to
the slow
In practice, don't implement your own search. Use the standard library.
#include <stdio.h>
#include <stdlib.h> // qsort
int compare (const void * a, const void * b) {
return ( *(int*)a - *(int*)b );
}
int main () {
int values[] = { 33, 12, 99, 90, 7, 45 };
qsort (values, 6, sizeof(int), compare);
for (size_t n=0; n<6; ++n) {
printf ("%d ",values[n]);
}
printf("\n");
return 0;
}
Download qsort.c