# Week 5 - Sorting

## Team

>Members:
>
>- Andreas Andreou 507675
>- Kawin Feng 525253
>
> Date: *day* *month* 2023 | |

## 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
When you search in a sorted array we use a binary search method and is much fater than an unsorted array.The time complexity of a sorted array increses logarithmicly with the size of the array.So binary search has time complexity of O(log x) where x is the size of the array.While if the array is sorted the time coplexity is O(n).In conclusion searching a value in a soted array is much esier and faster than in an unsorted one

### Activity 2: Find the smallest element

int* find_min(int* values, size_t count) {
    if (count == 0) {
        return NULL; // return nothing if values empty
    }

    int* min = values; // set first element as the smallest

    for (size_t i = 1; i < count; i++) {
        if (values[i] < *min_ptr) {
            min = values + i; // if a smaller values is found replace the min 
        }
    }

    return min; // return a pointer to the smallest value
}

### Activity 3: Implement selection sort

void array_sort(array_t *array) {
    int n = array->count;
    int* values = array->data;

    for (int i = 0; i < n - 1; i++) {
        int min = i;

        for (int j = i + 1; j < n; j++) {
            if (values[j] < values[min]) {
                min = j;
            }
        }

        if (min != i) {
            int nmin = values[i];
            values[i] = values[min];
            values[min] = nmin;
        }
    }
}

Another way is:(I show this way because we are a group of tow so both of us can understand by just reding the HackMD file with ous farther studing(507675))

void swap(int *xp, int *yp)
{
    int temp = *xp;
    *xp = *yp;
    *yp = temp;
}
 
void selectionSort(int 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] < arr[min_idx])
            min_idx = j;
 
        // Swap the found minimum element with the first element
           if(min_idx != i)
            swap(&arr[min_idx], &arr[i]);
    }
}
 
/* Function to print an array */
void printArray(int arr[], int size)
{
    int i;
    for (i=0; i < size; i++)
        printf("%d ", arr[i]);
    printf("\n");
}
 
// Driver program to test above functions
int main()
{
    int arr[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr)/sizeof(arr[0]);
    selectionSort(arr, n);
    printf("Sorted array: \n");
    printArray(arr, n);
    return 0;
}

### Activity 4: Selection sort: comparisons

#include <stdio.h>
#include <stdlib.h>

int main() {
int sizes[] = {5, 10, 15, 20, 30, 60, 90, 150, 300, 1000, 10000};

for (int i = 0; i < sizeof(sizes) / sizeof(int); i++) {
int* data = malloc(sizes[i] * sizeof(int));

// initialize array with random values
for (int j = 0; j < sizes[i]; j++) {
data[j] = rand();
}

count = 0;
min(data, sizes[i]);

printf("Array size %d, comparisons %d\n", sizes[i], count);

free(data);
}

return 0;
}

Use the website [Tables generator](https://www.tablesgenerator.com/markdown_tables) to easily create a table for use in markdown documents.

| Array size | Comparisons |
|------------|-------------|
| 5 | 10 |
| 10 | 45 |
| 15 | 105 |
| 20 | 190 |
| 30 | 435 |
| 60 | 1770 |
| 90 | 3970 |
| 150 | 11175 |
| 300 | 44850 |
| 1000 | 499500 |
| 10000 | 49995000 |

### Activity 5: Merge sort - step by step
The list is initially divided into 13 sublists, each containing a single element:
[9], [0], [31], [5], [2], [8], [15], [13], [6], [4], [7], [11], [19]

We make a sub list with larger sublist and sort them individually
[0, 9], [5, 31], [2, 8], [13, 15], [4, 6], [7, 11], [19]

We make a list with larger sublist as equaly legth as possible and sorth them one by one so we make 3 sorts
[0, 5, 9, 31], [2, 8, 13, 15], [4, 6, 7, 11], [19]

we merge them again with 2 larger sublist we sort the biggest sub list and le the last element out
[0, 2, 4, 5, 6, 7, 8, 9, 11, 13, 15, 19], [31]

The final step is to merge the two remaining sublists to form the sorted list:
[0, 2, 4, 5, 6, 7, 8, 9, 11, 13, 15, 19, 31]

Example of merge sort program with arrays so both of our team members can understand (507675):
#include <stdio.h>
#include <stdlib.h>

// Merges two subarrays of arr[].
// First subarray is arr[l..m]
// Second subarray is arr[m+1..r]
void merge(int arr[], int l, int m, int r)
{
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;

/* create temp arrays */
int L[n1], R[n2];

/* Copy data to temp arrays L[] and R[] */
for (i = 0; i < n1; i++)
L[i] = arr[l + i];
for (j = 0; j < n2; j++)
R[j] = arr[m + 1 + j];

/* Merge the temp arrays back into arr[l..r]*/
i = 0; // Initial index of first subarray
j = 0; // Initial index of second subarray
k = l; // Initial index of merged subarray
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
}
else {
arr[k] = R[j];
j++;
}
k++;
}

/* Copy the remaining elements of L[], if there
are any */
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}

/* Copy the remaining elements of R[], if there
are any */
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}

/* l is for left index and r is right index of the
sub-array of arr to be sorted */
void mergeSort(int arr[], int l, int r)
{
if (l < r) {
// Same as (l+r)/2, but avoids overflow for
// large l and h
int m = l + (r - l) / 2;

// Sort first and second halves
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);

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

/* UTILITY FUNCTIONS */
/* Function to print an array */
void printArray(int A[], int size)
{
int i;
for (i = 0; i < size; i++)
printf("%d ", A[i]);
printf("\n");
}

/* Driver code */
int main()
{
int arr[] = { 12, 11, 13, 5, 6, 7 };
int arr_size = sizeof(arr) / sizeof(arr[0]);

printf("Given array is \n");
printArray(arr, arr_size);

mergeSort(arr, 0, arr_size - 1);

printf("\nSorted array is \n");
printArray(arr, arr_size);
return 0;
}
### Activity 6: Splitting a linked list in two halves

node_t * split(node_t * phead) {
node_t * fast = phead->next;
node_t * slow = phead;
while (fast != NULL && fast->next != NULL) {
fast = fast->next; // update fast pointer
fast = fast->next;
slow = slow->next; // update slow pointer
}
node_t * second_half = slow->next;
slow->next = NULL;
return second_half;
}
void test_split() {
// create a list of 5 nodes
node_t * head = NULL;
for (int i = 5; i > 0; i--) {
push(&head, i);
}
// split the list
node_t * second_half = split(head);
// print the first half
print_list(head);
// print the second half
print_list(second_half);
}

### 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;
}
//The if is there to:compare the values of the current nodes in "a" and "b". If the value in "a" is smaller, "a" is appended to the end of the result list and "a" is updated to point to the next node in its list. If the value in "b" is smaller (or equal), "b" is appended to the end of the result list and "b" is updated to point to the next node in its list. Finally, "result" is updated to point to the last node in the result list.
if (a != NULL) {
result->next = a; // append remaining nodes of a
} else {
result->next = b; // append remaining nodes of b
}
return temp.next;
}

### Activity 8: Implement merge sort

node_t * merge_sort(node_t * first) {
if (first == NULL || first->next == NULL) {
return first;
} else {
node_t * second = split(first);
first = merge_sort(first); // first half
second = merge_sort(second); // second half
return merge(first, second); // merge
}
}

void test_merge_sort() {
// list of 5 nodes
node_t * head = NULL;
for (int i = 5; i > 0; i--) {
push(&head, i);
}
// sort
head = merge_sort(head);
// print list
print_list(head);
}

### Activity 9: Merge sort: impact of order
int comparison_count = 0; // global variable to keep track of comparisons

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;
comparison_count++; // increment comparison count
}
if (a != NULL) {
result->next = a;
} else {
result->next = b;
}
return temp.next;
}
void test_merge_sort() {
node_t * head1 = create_list(5, 4, 3, 2, 1);
node_t * head2 = create_list(1, 2, 3, 4, 5);

printf("Before :\n");
printf(" 1: ");
print_list(head1);
printf(" 2: ");
print_list(head2);

merge_sort(head1);
printf("After:\n");
printf(" 1: ");
print_list(head1);
printf("comparisons: %d\n", comparison_count);

comparison_count = 0; // reset comparison count

merge_sort(head2);
printf("After 2:\n");
printf(" 2: ");
print_list(head2);
printf("comparisons: %d\n", comparison_count);
}
Before:
1: 5 4 3 2 1
2: 1 2 3 4 5
After 1:
1: 1 2 3 4 5
comparisons: 10
After 2:
2: 1 2 3 4 5
comparisons: 7
### Activity 10: Merge sort: determining efficiency
5 5 – 7
10 15 – 19
15 24 – 28
20 34 – 38
30 64 – 68
60 254 – 258
90 554 – 558
150 1249 – 1253
300 2999 – 3003
1000 9999 – 10003
10000 99999 – 100003

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

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

Record your answer here

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