---
# System prepended metadata

title: Untitled

---

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