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

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

* Trying to find a value in an unsorted array will take some time (O(n)) since it is necessary to go linearly through the data structure. The sorted array, on top of the possibility to linearly search, is able to also use a different and a more efficient search algorithm, which takes considerable less time (O(log n)).
* The binary search algorithm is used to search for values in a sorted data structure.

### Activity 2: Find the smallest element

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

### Activity 3: Implement selection sort

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

### Activity 4: Selection sort: comparisons

|List length| Comparions |
|-----------|------------|
|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

**9, 0, 31, 5, 2, 8, 15, 13, 6, 4, 7, 11, 19**

**|0, 9| |5, 31| |2, 8| |13, 15| |4, 6| |7, 11| |19|**

**|0, 5, 9, 31| |2, 8, 13, 15| |4, 6, 7, 11| |19|**

**|0, 2, 5, 8, 9, 13, 15, 31| | 4, 6, 7, 11, 19 |**

**|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->next; // update fast pointer
        phead = phead->next;
    }
    node_t * temp = phead->next;
    phead->next = NULL;
    return temp;
}

### 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;
    }
    while (a != NULL) {
        result->next = a;
        a = a->next;
        result = result->next;
    }
    while (b != NULL) {
        result->next = b;
        b = b->next;
        result = result->next;
    }
   
    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);
        list_t a = {.head = first};
        list_sort(&a);
        list_t b = {.head = next};
        list_sort(&b);
        first = merge(a.head, b.head);
        return first;
    }
}

### Activity 9: Merge sort: comparisons

|List length| Comparions |
|-----------|------------|
|5 |5 |
|10 |15 |
|15 |28 |
|20 |40 |
|30 |71 |
|60 |210 |
|90 |402 |
|150 |788 |
|300 |1901 |

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

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

The logarithmic function is the one that best fits the merge sort and the quadratic function is the one that best fits selection sort.

## Looking back

### What we've learnt

* Conseptually understood the selection and merge sort algorithms.
* There are different time complexities for different sorting algorithms.
* Splitting and merging linked lists.

### What were the surprises

* Not a lot of assingments during this week. We were suprised by this and we appreciated this very much :)

### What problems we've encountered

* Understanding merge sort.
* Unknowingly using nodes and lists interchangeably.

### What was or still is unclear

* For some of our members, the recursion is unclear that is used in merge sort.
* Where else can the sorted data be used besides the faster searching of variables?

### How did the group perform?

* Our team did a lot of cooperation during this week's assignments. We believe that we did a lot during the beginning, meaning that was not a lot of pressure to finish the final harder tasks.

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