# Week 5 - Sorting

## Team

Team name:
Date:

Members

| Role | Name |
|-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|------|
| **Facilitator** keeps track of time, assigns tasks and makes sure all the group members are heard and that decisions are agreed upon. | |
| **Spokesperson** communicates group’s questions and problems to the teacher and talks to other teams; presents the group’s findings. | |
| **Reflector** observes and assesses the interactions and performance among team members. Provides positive feedback and intervenes with suggestions to improve groups’ processes. | |
| **Recorder** guides consensus building in the group by recording answers to questions. Collects important information and data. | |

## 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

Elementen binnen een gesorteerde arry worden gevonden met een binaire zoekactie, in O(log n)

Elementen binnen een niet gesorteerde array O(n)

### Activity 2: Find the smallest element

int *find_min(int *values, size_t count){
    if(values == NULL) return NULL;
    int *min = &values[0];
    for (size_t i = 0; i < count; ++i) {
        if(values[i] < *min) min = &values[i];
    }
    return min;
}

### Activity 3: Implement selection sort

void array_sort(array_t *array) {
        // TODO (Activity 3): implement
    for (int i = 0; i < array->count; ++i) {
        //sorteren
        //minvalue vinden
        int *pMin = find_min(array->data + i, array->count - i);
        swap(&array->data[i], pMin);
    }
}

### Activity 4: Selection sort: comparisons

5 10
10 45
15 105
20 190
30 435
60 1770
90 4005
150 11175
300 44850

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

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

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

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 *tempSecondHead = phead->next;
    phead->next = NULL;
    // TODO (Activity 6): complete the code
    return tempSecondHead;
}

### Activity 7: Merging two linked lists

node_t *merge(node_t *a, node_t *b) {
    node_t temp = {.next = NULL};
    node_t *result = &temp;
    while (a != NULL && b != NULL) {
        if (a->value < b->value) {
            result->next = a;
            a = a->next;
        } else {
            result->next = b;
            b = b->next;
        }
        result = result->next;
    }
    if(a != NULL) result->next = a;
    else if(b != NULL) result->next = b;
    // TODO (Activity 7): complete the code
    return temp.next;
}

### Activity 8: Implement merge sort

node_t *merge_sort(node_t *first) {
    if (first->next == NULL) return first;
    else {
        node_t *next = split(first);
        first = merge_sort(first);
        next = merge_sort(next);

        return merge(first, next);
        return first;
    }
    // TODO (Activity 8) : complete the code
    return first;
}

### Activity 9: Merge sort: comparisons

Record your answer here

### Activity 10: Compare merge sort and selection sort

| Algorithm | Time complexity |
| --------------------------------- | --------------- |
| Merge sort | |
| Selection sort | |

Record your answer here

## Looking back

### What we've learnt

Formulate at least one lesson learned.

### What were the surprises

Fill in...

### What problems we've encountered

Fill in...

### What was or still is unclear

Fill in...

### How did the group perform?

How was the collaboration? What were the reasons for hick-ups? What worked well? What can be improved next time?

> Written with [StackEdit](https://stackedit.io/).