# Week 3 - Sorting and Searching

## Team

Team name: Group 3
Date: 01-03-2021

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

## Activities

### Activity 1: Purpose of sorted lists

>"The main advantage is the time taken. The main benefit for an array to be sorted is that it gives a high level of certainty, because we are pretty much sure that the number to be searched is either to the right or left of a randomly selected number of the array sorted in ascending order, depending whether the searched element is greater or smaller than randomly selected number respectively. Then searching the number in only that part.
And if the randomly selected number is itself the searched element then bingo, you got the number. Otherwise, continue the process until you are sure that the element does not exist."

Reference: https://www.quora.com/What-is-the-advantage-of-searching-in-a-sorted-list-rather-than-in-an-unsorted-list

Concrete cases:
- Sorting population by age to identify 18+ citizens
- Flights arrival and departure at the airport (sort by time)
- Grades in school (sort who passed or level of IQ)
- Sort playing cards in a deck

### Activity 2: Explanation of selection sort

Watched : https://www.youtube.com/watch?v=xWBP4lzkoyM&feature=youtu.be&ab_channel=GeeksforGeeks

### Activity 3: Performance of selection

- **How does the runtime of selection sort depend on the number of elements in the array?**

Everytime you go through the array of elements, it takes the smallest number, creates a new array and stores it in the index + 1(apart from the first element)

The runtime to do this will depend on the amount of elements in the array because the bigger the array, the more times you would have to loop through the array of elements.

There wil also be additional runtime to create the new sorted array and add the elements in that array as well.

- **How much time (roughly) will the algorithm need to sort a list of 2n or 4n elements?**

Selection sort takes one millisecond to sort 1000 items (worst-case time) on a particular computer. This could be diffrent on another computer.

In general:

==For an array with 2n elements, let n be 5, will take 2 times as long as the array n.==

- **If you were to use a linked list instead of an array, would the performance be any different?**

We don't think the performance would be any different.

### Activity 4: Implement selection sort

void selectionSort(Data arr[], int n)
{
    int i, j, min_idx;

    // One by one move boundary of unsorted subarray
    for (i = 0; i < n-1; i++)
    {
        // Find the minimum element in unsorted array
        min_idx = i;
        for (j = i+1; j < n; j++)
            if (arr[j].year < arr[min_idx].year)
                min_idx = j;

        // Swap the found minimum element with the first element
        swap(&arr[min_idx].year, &arr[i].year);
    }
}

### Activity 5: Explanation of merge sort

Watched: https://www.youtube.com/watch?v=4VqmGXwpLqc&feature=youtu.be&ab_channel=MichaelSambol

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

|9|3|0|17|12|1|1|5|2|10|8|4|9|3|2|
|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|
|3-9||0-17||1-12||1-5||2-10||4-8||3-9||2-/|
|0-3-9-17||1-1-5-12||2-4-8-10||2-3-9-/|
|0-1-1-3-5-9-12-17||2-2-3-4-8-9-10-/|
|0-1-1-2-2-3-3-4-5-8-9-9-10-12-17|

### Activity 7: Implement the merge function

void merge(Data arr[], int l, int m, int r)
{
    int i, j, k;
    int n1 = m - l + 1;
    int n2 = r - m;

    Data L[n1], R[n2];

    for (i = 0; i < n1; i++)
        L[i].year = arr[l + i].year;
    for (j = 0; j < n2; j++)
        R[j].year = arr[m + 1 + j].year;

    i = 0;
    j = 0;
    k = l;
    while (i < n1 && j < n2) {
        if (L[i].year <= R[j].year) {
            arr[k].year = L[i].year;
            i++;
        }
        else {
            arr[k].year = R[j].year;
            j++;
        }
        k++;
    }

    while (i < n1) {
        arr[k].year = L[i].year;
        i++;
        k++;
    }

    while (j < n2) {
        arr[k].year = R[j].year;
        j++;
        k++;
    }
}

### Activity 8: Implement the divide-and-conquer algorithm

void mergeSort(Data arr[], int l, int r)
{
    if (l < r) {
        int m = l + (r - l) / 2;

        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);

        merge(arr, l, m, r);
    }
}

### Activity 9: Test merge sort

When looking at the code provided, we didn't really understand much of it. Therefor we created our own code and used the Spotify struct (years) to test our code and it worked. We randomly filled our songs array with years that the songs were released, then we used the merge sort to sort them in ascending order. This worked as expected.

### Activity 10: Binary search - step by step

| Step 1 | Search range | Middle element | Discarded range |
| -------- | -------- | -------- | -------- |
| 1 | [0 ... 22) | 11 22 | [0 ... 11] |
| 2 | [12 ... 22) | 17 55 | [12 ... 17] |
| 3 | [18 ... 22) | 19 70 | [18 ... 19] |
| 4 | [19 ... 22) | 20 75 | [19 ... 21] |

### Activity 11: Implement binary search

int binarySearch(const Array *pArray, const Data *pValue)
{
    int lpos = 0;
    int rpos = pArray->count;
    
    while (lpos < rpos) {
        int mid = (lpos + rpos) / 2;
        
        int ordering = compare(&pArray->values[mid], pValue);
        
        if (ordering > 0) {
            rpos = mid;
        }
        
        else if (ordering < 0) {
            lpos = mid;
        }
        
        else {
            return mid;
        }
    }
    
    return -1;
}

### Activity 12: Test binary search

### Activity 13: Time complexity

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

### Activity 15: Compare naive search and binary search

## Look back

### What we've learnt

Cas: This week I've learned that you can divide and then combine arrays to sort them in a full array.

Artem: This week, I have worked with arrays, sorting algorithms, and analyzing the benefits of sorted data. After this week I learned about sorting and merging two arrays. Also, I got some knowledge about the efficiency and advantages of these algorithms.

### What were the surprises

Cas: I wasn't really surprised by this subject, rather excited that I learned how to merge 2 arrays

Artem: I was surprised by the methodology of the binary search algorithm because, at the first time, it seems confusing, but after the key idea becomes pretty clear and logical.

### What problems we've encountered

Cas: The problem I encountered is that the code that was provided was not really clear to me. Once i wrote the code myself it wazs easier to understand how to do it.

Artem: I do not think that I can emphasize some problems, but I would like to say that the topic regarding Big O was interesting, but sometimes confusing for me at the same time. But I handled it because it was just struggling and unclarity in my understanding and I found a way, how to learn it. Thus, I managed to learn whole this information from this week.

### What was or still is unclear

Cas: To me it is still unclear how to to the binary search and the Time complexity. I haven't worked on this part of the assignment this week.

Artem: This week, I have worked with my parts of assignments and also, did everything for my personal development; Thus, I would say that I understand the whole of this knowledge base related to this week.

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

Cas: At the beginning of this week the whole group worked on activities 1-4. We decided that we should come together on Wednesday to finish the rest of the activities. Unfortunately, Adriaan was not there on Wednesday to work on the activities. Artem was there but was not actively participating when working on them. Raglan and I made activities 4-9 and told the other members of the group that is fair to let them do activities 10-13 and then do activities 14 and 15 when the other activites were done. At the time of writing (21-03-2020 at 21:00), the activites 10-13 are not completed. Therefor the oher activites remain incomplete as well.

Artem: After the first meeting, the group was doing great. On Wednesday, when the first meeting was held, I struggled with understanding the organization of the group working process. That was not the group's fault, that was my misunderstanding. After the first meeting, I came up with a plan of what I can do by the end of the week and I successfully managed to complete my plan. I have partly worked on activities 1-4 and 10-13, but from the last activities, I uploaded in HackMD only 10-11 because the remaining part was expected from Adriaan. Also, on Sunday evening was planned a group meeting to solve the last problems (14-15), but unfortunately, the meeting was skipped and as a result, the 14-15 activates were not completed.
In addition, I would like to say that the nice work was done by Cas and Raglan, and was sad to do not to get a response from Adriaan, I hope that he is doing well. I also would like to reflect on my actions as I am a reflector person. I would like to improve my management skill as sometimes I can struggle with organization, but talking about code writing, I think that I completed my assigned work and gain a lot of useful experience thanks to my team members.