# Week 5 - Sorting

## Team

Team name:BeastFromTheEast
Date:11/04/2022

Members
Nikola Zahariev, Attila Poldan, Casian Ionescu, Alexandra Melei

| 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

Record your answer here:

1) Assuming that the user peforms a single look-up, in this case there is no need to sort the data before, as the "sorting" would be implied already in the action of the look-up, in which case the time complexity of both unsorted and sorted arrays is the same at O(n). However, on the account that multiple searches will be performed in that array, a sorted array that uses a binary search look-up algorythm will yield (on average) a time complexity of O(log2(n)), significantly faster than the previous O(n).
2) Algorithm Binary search is used to search a sorted array for a value

### Activity 2: Find the smallest element

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

### Activity 3: Implement selection sort
We start looking from the first value and comparing all of them to each other. When we find the smaller value we swap its place in the array with the value that was in the beginning. After that we continue with the second value in the index and looking for the second smallest value, and we do that auntil the arrray is sorted.

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

    }
}

### Activity 4: Selection sort: comparisons

| List lenght| Comparisons|
|------------|------------|
|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 lists | [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;
        phead = phead->next;
    }
    fast=phead->next;
    phead->next=NULL;
    return fast;
}

### 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)// 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;
    }
    // TODO (Activity 7): complete the code

	if (a != NULL)
		result->next = a;
	else
		result->next = b;

    return temp.next;
}

### Activity 8: Implement merge sort

Record your answer here:

node_t * merge_sort(node_t* first)
{
	if(first == NULL || first->next == NULL)
	{
		return first;
	}
	node_t *second = split(first);

	node_t *left = merge_sort(first);

	node_t *right = merge_sort(second);


	node_t *sortedList = merge(left,right);

	return sortedList;

}

### Activity 9: Merge sort: comparisons

Record your answer here:

| List lenght | Comparisons |
| -------- | -------- |
| 5 | 5 |
| 10 | 15 |
| 15 | 44 |
| 20 | 60 |
| 30 | 101 |
| 60 | 253 |
| 90 | 439 |
| 150 | 838 |
| 300 | 1992 |

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

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

The logarthmic function makes the most sense for the merge sort method. And as for the selection sort method, the standard quadratic formula expresses the most efficiency.

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