# Week 5 - Sorting

## Team

>Members:
>
>- Tom Rutjes
>- David Cigri
>
> Date: 19 maart 2024

## Activities

Make sure to have the activities signed off regularly to ensure progress is tracked.

Download the provided project and open it in CLion.

### Activity 1: Benefits of sorted data :heavy_check_mark:

When searching a sorted array, you can "guess" where the correct data is stored. If this is not the correct spot, you can check if the data is smaler or greater than the data you are looking for to take another educated guess.

### Activity 2: Find the smallest element :heavy_check_mark:

int *find_min(int *values, size_t count) {
    int* smallest = &values[0]; //Verdwijnt deze var niet door lifetime enzo?
    for (size_t i = 1; i < count; i++) {
       if(values[i] < *smallest) smallest = &values[i];
    }
    return smallest;
}

### Activity 3: Implement selection sort :heavy_check_mark:

void array_sort(array_t *array) {
    for (size_t i=0; i<array->count; ++i) {
        swap(&array->data[i], find_min(&array->data[i], array->count-i));
    }
}

### Activity 4: Selection sort: comparisons :heavy_check_mark:

| Array size | Comparisons |
|------------|-------------|
| 5 | 10 |
| 10 | 45 |
| 15 | 105 |
| 20 | 190 |
| 50 | 1225 |
| 100 | 4950 |
| 150 | 11175 |
| 250 | 31125 |
| 500 | 124750 |
| 1000 | 499500 |
| 5000 | 12497500 |
| 10000 | 49995000 |

### Activity 5: Merge sort - step by step :heavy_check_mark:

| Stage | Subsequences |
|-----------|----------------------------------------------------------|
| 13 lists: | [9],[0],[31],[5],[2],[8],[15],[13],[6],[4],[7],[11],[19] |
| 7 lists: | [0,9],[5,31],[2,5],[8,15],[6,13],[4,7],[11,19] |
| 4 lists | [0,5,9,31],[2,5,8,15],[6,8,13,15],[4,7,11,19] |
| 2 Lists | [0,2,5,5,8,9,15,31],[4,6,7,8,11,13,15,19] |
| 1 list: | [0,2,4,5,5,6,7,8,8,9,11,13,15,15,19,31] |

### Activity 6: Splitting a linked list in two halves :heavy_check_mark:

node_t *split(node_t *phead) {
    node_t *fast = phead->next;
    while (fast != NULL && fast->next != NULL) {
        fast = fast->next;
        fast = fast->next;
        phead = phead->next;
    }

    node_t *returnNode = phead->next;
    phead->next = NULL;
    return returnNode;
}

### Activity 7: Merging two linked lists :heavy_check_mark:

node_t *merge(node_t *a, node_t *b) {
    // this function reconstructs a linked list from the two linked lists a and b.
    // sentinel will be used as a "fake" head of the resulting list, nodes from node sequences a and b will be appended to sentinel.
    node_t sentinel = {.next = NULL};
    node_t *result = &sentinel;         // result always points to the last node in the sequence we're constructing
    (void) result;  // remove this line when you've implemented this function
    while (a != NULL && b != NULL) {
        g_compares++;   // a comparison is made, count it
        if (a->value < b->value) {
            result->next = a;
            a = a->next;
        } else {
            result->next = b;
            b = b->next;
        }
        result = result->next;
    }
    // Either a or b will be NULL at this point
    if(a == NULL) result->next = b;
    else result->next = a;
    return sentinel.next;   // return the sequence of nodes we've constructed
}

### Activity 8: Implement merge sort :heavy_check_mark:

node_t *merge_sort(node_t *first) {
    if (first->next == NULL) return first;  // no need to sort a list with one element
    
    node_t *second = split(first);
    //  merge_sort these two lists, and then merge them together again
    first = merge_sort(first);
    second = merge_sort(second);
    first = merge(first, second);
    //  Finally, return the first element of the sorted list
    return first;
}

### Activity 9: Merge sort: impact of order :heavy_check_mark:
Done. While merge-sorting {5,4,3,2,1}, the smaller numbers are in the smaller lists. Because of this, there are less comparisons.

### Activity 10: Merge sort: determining efficiency :heavy_check_mark:

| List length | Comparisons |
|-------------|-----------------|
| 5 | 5 - 7 |
| 10 | 15 - 19 |
| 15 | ~28 |
| 20 | ~40 |
| 50 | ~133 |
| 100 | ~316 |
| 250 | ~983 |
| 500 | ~2216 |
| 1000 | ~29804 |
| 10000 | ~120334 |

### Activity 11: Compare merge sort and selection sort :heavy_check_mark:

| Algorithm | Time complexity |
| ---------------| -----------------|
| Merge sort | O(n log(n)) |
| Selection sort | O(n^2) |

## Looking back

### What we've learnt

Time complexity with log(n) functions.

### What were the surprises

5,4,3,2,1 is easier to merge-sort than 1,2,3,4,5
C

### What problems we've encountered

Recursion was a bit hard to wrap your head around. But it wasnt he hardest thing I've ever done.

### What was or still is unclear

Nothing :sunglasses:

### How did the group perform?

Very good! Till next time! :construction_worker: