## ARRAYS

• Arrays store sequences of data of a single type!
• Declaration: char A[MAX_N]
declares an array with elements A[0], ... A[MAX_N-1]
• Arrays in C start always at 0!
• Arrays are static!
the size has to be known in advance and can't be changed during runtime.
• Pointers allow dynamic memory management!
(e.g. arrays of flexible size - more next time)

### Program 1: Arrays

```#include<stdio.h>

int main() {

int A[10];
int i;

/*
* store seven numbers in array A
* Questions: What are these numbers?
*/

A[0] = 1;
A[1] = 2;
A[2] = 4;
A[3] = 6;
A[4] = 10;
A[5] = 12;
A[6] = 16;

/* print numbers in A */

printf("forward\n");
for (i = 0; i < 7; ++i)
printf("A[%d] = %d\n",i,A[i]);

/* print numbers in A backwards */

printf("\nbackward\n");
for (i = 6; i >= 0; --i)
printf("A[%d] = %d\n",i,A[i]);
}
```

### Program 2: Using arrays

```#include<stdio.h>

#define MAX_N 20

int main() {

/*
* Consider a sequence of numbers a_0, a_1, ..., a_(n-1),
* and a number x.
*
* We want to count how many numbers of A are less than x.
* This quantity is usually called rank_A(x)
*
*/

float A[MAX_N];
float x;
int rank, i;

int n;

printf("how many numbers:\t");
scanf("%d",&n);

/* read numbers */

for (i = 0; i < n; ++i) {
printf("number:\t");
scanf("%f",&A[i]);
}

/* read x */
printf("x:\t");
scanf("%f",&x);

/* count elements smaller than x */
rank = 0;
for (i = 0; i < n; ++i)
rank += (A[i] < x);

/* output */
printf("rank(%f) = %d\n",x,rank);
}
```

### Program 3: Sorting Numbers

```#include<stdio.h>

#define MAX_N 20

int main() {

/* Consider a set of numbers a_0, a_1, ..., a_(n-1)
* without repeats.
*
* In this example, we're sorting the set using ranks.
* This sorting algorithm is bad for two reasons. Why?
* Think in terms of required space and time...
*
* What do you need to change to allow repeated numbers?
*/

int A[MAX_N];
int Asorted[MAX_N];

int i, j;
int rank[MAX_N];
int n;

printf("how many numbers:\t");
scanf("%d",&n);

/* read numbers */
for (i = 0; i < n; ++i) {
printf("number:\t");
scanf("%d",&A[i]);
}

/* count elements smaller than x */
for (j = 0; j < n; ++j) {
rank[j] = 0;
for (i = 0; i < n; ++i)
rank[j] += (A[i] < A[j]);
}

/* sort elements */
for (i = 0; i < n; ++i)
Asorted[rank[i]] = A[i];

/* output */
for (i = 0; i < n; ++i)
printf("%d \t",Asorted[i]);
}
```

### Program 4: Sorting Numbers - Differently

```#include<stdio.h>

#define MAX_N 20
#define MAX_M 100

int main() {

/* Consider a set of numbers a_0, a_1, ..., a_(n-1)
* from 0 to MAX_M without repeats.
*
* Here's a different sorting algorithm.
* Can you figure out how it works? What's so special
* about this one? Compare it to the previous one.
* Do you know other algorithms?
*
* Can you fix it to work with repeats?
* In which situation is this algorithm bad?
* How would you fix it?
*/

int A[MAX_N];
int B[MAX_M];
int C[MAX_N];

int i, j, n;

/* initialization */

for (i = 0; i < MAX_M; ++i) B[i] = 0;

/* input */

printf("how many numbers:\t");
scanf("%d",&n);

for (i = 0; i < n; ++i) {
printf("number:\t");
scanf("%d",&A[i]);
}

/* sorting */

for (i = 0; i < n; ++i)
++B[A[i]];

for (i = 0; i < MAX_M-1; ++i)
B[i+1] += B[i];

for (i = 0; i < n; ++i)
C[B[A[i]]-1] = A[i];

/* output */

for (i = 0; i < n; ++i)
printf("%d \t",C[i]);
}
```

### Program 5: Primes

```#include<stdio.h>

#define MAX_N 200

int main() {

/*
* Compute prime number in interval from 1 to MAX_N.
*
* Questions:
* How many prime numbers are in that interval? How
* does this number grow for large MAX_N? Draw the
* graph if you know how to use any graphics functions.
*/

int P[MAX_N];
int i, k;

/* mark all numbers */
for (i = 0; i < MAX_N; ++i)
P[i] = 1;

for (i = 2; i < MAX_N; ++i)
if (P[i]) {
printf("%d\n", i);
for (k = i+i; k < MAX_N; k+= i) P[k] = 0;
}
}
```