# Week 5 - Sorting

## Team

Team name:Error
Date:19.03.2022

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. | Hoa |
| **Spokesperson** communicates group’s questions and problems to the teacher and talks to other teams; presents the group’s findings. | Minh |
| **Reflector** observes and assesses the interactions and performance among team members. Provides positive feedback and intervenes with suggestions to improve groups’ processes. | Thanh |
| **Recorder** guides consensus building in the group by recording answers to questions. Collects important information and data. | Kaloyan |

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

With unsorted array, sometimes we need to go through the whole array to lookup a middle value of the array. It means it take O(n) time to lookup the desired value. On the other hand, we just need to go half way to find the middle value of the array. It means we just take O(log n).

Binary search algorithm is used to search a sorted array.

### Activity 2: Find the smallest element

Record your answer here

int* find_min(int* value, size_t count) { 
 if (count == 0) { 
 return NULL; 
 } else for (int i = 0; i < (int) count -1 ; i++) { 
   for (int j = 0; j < (int) count - 1; j++) { 
    if (value[j] > value[j+1]) { 
     int temp = value[j]; 
     value[j] = value[j + 1]; 
     value[j + 1] = temp; 
     } 
    } 
   } 
return value; 
}

### Activity 3: Implement selection sort

Record your answer here

void array_sort(array_t *array){

for(size_t i=0;i<array->count-1;i++){

size_t min=i;

for(size_t j=i+1;j<array->count;j++){

g_comp++;

if(array->data[min]>array->data[j]){

min=j;

    }

}

int key=array->data[min];

//Move the minimum value at current i

for(;min>i;min--){

    array->data[min]=array->data[min-1];

    array->data[i]=key;

    }

}

### Activity 4: Selection sort: comparisons

Record your answer here

| List lenght | Comparison |
| -------- | -------- |
| 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

Record your answer here

| Stage | Subsequences |
| -------- | -------- |
| 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

Record your answer here

    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 *split = phead->next;
    phead->next = NULL;
    return split;
}

### Activity 7: Merging two linked lists

Record your answer here

    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;
    }
    ///NEW PART
    if (a != NULL) {
        result->next = a;
    } else if (b != NULL) {
        result->next = b;
    }
    ///////
    return temp.next;
    }

### Activity 8: Implement merge sort

Record your answer here

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);
        first = merge(first, next);
        return first;
    }
}

### Activity 9: Merge sort: comparisons

| List length | Comparisons |
| ----------- | ----------- |
| 5 | 5-7 |
| 10 | 15-19 |
| 15 | 28-31 |
| 20 | 40-48 |
| 30 | 71-77 |
| 60 | 172-184 |
| 90 | 275-317 |
| 150 | 515-579 |
| 300 | 1180-1308 |

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^2) |

Record your answer here

## Looking back

### What we've learnt

We learned how the selection sort and the merge sort work for singly linked lists. In addition, to complete the merge sort we had to split the list and to merge it again. For this week we also learned about the recursive way of sorting and last but not least the time complexity of both the sorting algorithms.

### What were the surprises
It is surprising how things change with bigger lists and the algorithms that sort them. The time needed and the operations done.

### What problems we've encountered

No problems were encountered this week.

### What was or still is unclear.

Everthing is clear and learned.

### How did the group perform?

The group performed very well and collaboratevly. We did our exercises in time and in a way that every group member to understand them.