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

Searching in an unsorted array takes O(n) time: you potentially have to look at every item to find out if what you're looking for is there. A sorted array lets you speed up the search. Instead of having to examine every item, you only have to examine at most log2(n) items.

### Activity 2: Find the smallest element

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

### Activity 3: Implement selection sort

Record your answer here

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

### Activity 4: Selection sort: comparisons

Record your answer here
// 15 = 105
// 20 = 190
// 30 = 435
// 60 = 1770
// 90 = 4005
// 150 = 11175
// 300 = 44850

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

Record your answer here
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;
}
// TODO (Activity 6): complete the cod
node_t * midPhead = phead;
phead = phead -> next;
midPhead->next = NULL;
return phead;
}

### 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) { // while both lists have elements
if (a->value < b->value) { // compare head of both lists
result->next = a; // append a to result
a = a->next;
} else {
result->next = b; // append b to result
b = b->next;
}
result = result->next;
}
Node* merge = (struct Node*) malloc(sizeof(struct Node));
merge->result;

return temp.next;
}

### Activity 8: Implement merge sort

node_t * merge_sort(node_t * first) {
if (first->next == NULL) {
return first; // only a single node, so already sorted
}
else {
node_t * next = split(first);
if (a->data <= b->data)
{
first = a;
first->next = merge_sort(a->next, b);
}
else {
first = b;
first->next = merge_sort(a, b->next);
}
return first;
}
}

### Activity 9: Merge sort: comparisons

Record your answer here

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

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

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/).