Programmeringsmetodik: Inlämningsuppgift 2, Komplexitetsteori

Läs först introduktionen till komplexitetsteori.

Redovisning

Uppgiften

Tips: Det är inte meningen att man ska provköra alla funktionerna och mäta tiden, utan det går att sluta sig till tidskomplexiteten bara genom att studera programkoden. Därför lämpar sig uppgiften bra som hemuppgift. (Därmed inte sagt att man inte får provköra. Här finns en fil med alla funktionerna, och exempel på anrop: inl2funktioner.c)

Ett tips till: Glöm inte att först läsa introduktionen till komplexitetsteori.

1. Funktionen "find_max_in_array"

// Finds the largest value in the array "a" of length "length"
double find_max_in_array(double a[], int length) {
    double max = a[0];
    for (int i = 1; i < length; ++i) {
        if (a[i] > max) {
            max = a[i];
        }
    }
    return max;
}

2. Funktionen "incorrect_reverse_string"

// Reverses the string "s" in place, but there is a bug
void incorrect_reverse_string(char* s) {
    int n = strlen(s);
    for (int i = 0; i < n; ++i) {
        char temp = s[i];
        s[i] = s[n - i - 1];
        s[n - i - 1] = temp;
    }
}

3. Funktionen "reverse_string"

// Reverses the string "s" in place
void reverse_string(char* s) {
    int n = strlen(s);
    for (int i = 0; i < n / 2; ++i) {
        char temp = s[i];
        s[i] = s[n - i - 1];
        s[n - i - 1] = temp;
    }
}

4. Funktionen "arrays_are_equal"

// Compares two arrays of length "length" and returns 1 if they are equal
double arrays_are_equal(double a[], double b[], int length) {
    for (int i = 0; i < length; ++i) {
        if (a[i] != b[i]) {
            return 0;
        }
    }
    return 1;
}

5. Funktionen "find_number_of_matches"

// Returns the sum of how many times each needle occurs in the haystack,
// both arrays of length "length"
int find_number_of_matches(int needles[], int haystack[], int length) {
    int nr_matches = 0;
    for (int n = 0; n < length; ++n) {
        for (int h = 0; h < length; ++h) {
            if (needles[n] == haystack[h]) {
                ++nr_matches;
            }
        }
    }
    return nr_matches;
}

6. Funktionen "sort_array"

// Sorts the array "a" of length "length" in ascending order using selection sort
void sort_array(double a[], int length) {
    for (int sorted = 0; sorted < length - 1; ++sorted) {
        int smallest_in_rest = sorted;
        for (int in_rest = sorted + 1; in_rest < length; ++in_rest) {
            if (a[in_rest] < a[smallest_in_rest]) {
                smallest_in_rest = in_rest;
            }
        }
        double temp = a[sorted];
        a[sorted] = a[smallest_in_rest];
        a[smallest_in_rest] = temp;
    }
}

7. Funktionen "is_array_sorted"

// Returns 1 if the array "a" of length "length" is sorted in ascending order
int is_array_sorted(double a[], int length) {
    for (int i = 0; i < length - 1; ++i)
        if (a[i] > a[i + 1])
            return 0;
    return 1;
}

8. Funktionen "is_array_sorted_2"

// Returns 1 if the array "a" of length "length" is sorted in ascending order
int is_array_sorted_2(double a[], int length) {
    double *copy = malloc(length * sizeof(double));
    memcpy(copy, a, length * sizeof(double));
    sort_array(copy, length);
    int result = arrays_are_equal(a, copy, length);
    free(copy);
    return result;
}

9. Funktionen "shuffle_array"

// Sorts the array "a" of length "length" in random order
void shuffle_array(double a[], int length) {
    for (int randomized = 0; randomized < length; ++randomized) {
        // Select a random position in the rest of the array
        int selected = randomized + rand() % (length - randomized);
        // Swap the current position with the random position
        double oldvalue = a[randomized];
        a[randomized] = a[selected];
        a[selected] = oldvalue;
    }
}

10. Funktionen "shuffle_array_really_well"

// Sorts the array "a" of length "length" in random order, but more thoroughly
void shuffle_array_really_well(double a[], int length) {
    shuffle_array(a, length);
    shuffle_array(a, length);
    shuffle_array(a, length);
}

11. Funktionen "shuffle_array_really_really_well"

// Sorts the array "a" of length "length" in random order, even more thoroughly
void shuffle_array_really_really_well(double a[], int length) {
    shuffle_array(a, length);
    shuffle_array(a, length);
    shuffle_array(a, length);
    shuffle_array(a, length);
    shuffle_array(a, length);
}

12. Funktionen "shuffle_array_really_really_really_well"

// Sorts the array "a" of length "length" in random order, ridiculously well
void shuffle_array_really_really_really_well(double a[], int length) {
    for (int i = 0; i < length; ++i)
        shuffle_array(a, length);
}

13. Funktionen "shuffle_array_really_really_really_really_well"

// Sorts the array "a" of length "length" in random order, even more ridiculously well
void shuffle_array_really_really_really_really_well(double a[], int length) {
    shuffle_array(a, length);
    shuffle_array_really_well(a, length);
    shuffle_array_really_really_well(a, length);
    shuffle_array_really_really_really_well(a, length);
}

14. Funktionen "bogosort_array"

// Sorts the array "a" of length "length" in ascending order using bogosort
void bogosort_array(double a[], int length) {
    while (! is_array_sorted(a, length))
        shuffle_array(a, length);
}

15. "Really, really well"?