# Week 5 - Sorting

## Team

Team name:Taimour III
Date:23-03-2022

Members
Nafizul Habib Redwan
Rimma Davletova
Naomi Verschuur
Yazan Tayeh

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

## 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
The array is sorted. Use a binary search, where you cut the number of elements that are left to look at in half for each element you examine.O(n)
The array is unsorted. Just look at each value. O(log n)

### Activity 2: Find the smallest element

if(count == 0){
        return NULL;
    }
    else {
        size_t i = 0;
        while (i < count) {

            if (values[0] > values[i]) {
                values[0] = values[i];
            }
            i++;

        }
        return &values[0];
	}

### Activity 3: Implement selection sort

void array_sort(array_t *array){
    int n=array->count;
    int i, j, position, swap;
    for (i = 0; i < (n - 1); i++) {
        position = i;
        for (j = i + 1; j < n; j++) {
            if (array->data[position] > array->data[j])
                position = j;
        }
        if (position != i) {
            swap = array->data[i];
            array->data[i] = array->data[position];
            array->data[position] = swap;
        }
    }
}

### Activity 4: Selection sort: comparisons
List length=15 ; Comparions=105
List length=20 ; Comparions=190
List length=30 ; Comparions=435
List length=60 ; Comparions=1770
List length=90 ; Comparions=4005
List length=150 ; Comparions=11175
List length=300 ; Comparions=44850

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

[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) {
    if(phead == NULL)
        return NULL;

    node_t * fast = phead->next;
    while (fast != NULL && fast->next != NULL) {
        fast = fast->next; // update fast pointer
        if(fast == NULL)
            break;
        fast = fast->next;
        phead = phead->next; // update slow pointer
    }

    node_t *toReturn = phead->next;
    phead->next = NULL;
    return toReturn;
}

### 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;
         }
     // more code is needed here!
    if (a != NULL) {
        temp.next = a;
    } else if (b != NULL) {
        temp.next = b;
    }
     return temp.next;
 }

### Activity 8: Implement merge sort

// merge-sorts the list starting in first, and returns the first element
// of the resulting list
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 (l < r) {
        int m = l + (r - l) / 2;
        // Sort first and second halves
        merge_sort(arr, l, m);
        merge_sort(arr, m + 1, r);
    }
    merge(first, next);
    return first;
    }
}

### Activity 9: Merge sort: comparisons
15-40
20-67
30-109
60-285
90-469
150-911
300-2100

### Activity 10: Compare merge sort and selection sort
| Algorithm | Time complexity |
| --------------------------------- | --------------- |
| Merge sort | O(n*Log(n) |
| Selection sort | O(n^2) |

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