Ex 07

Assignment Number 7 Given: 24/06/08 Due: 08/07/08

Before doing the exercise, please read very carefully the submission guidelines. If you have any questions about the exercise, please refer to the FAQ page first. If your question is not answered there send an email. If the user enters invalid input your program should print "error" and main should return the value -1.

Ex 7.1 – Merge Sort Write a program that recursively sorts an array of numbers. It first sorts the left half of the array, then the right half of the array and then merges to the two into a single sorted array. The program: Reads an integer number, which tells how many numbers are in the array Reads an array of integers. Sorts the array. Prints the sorted array.

• • • •

Assumptions: You will be given the first number. o You have to check that it is a valid number. o If it is valid then it gives the correct number of elements in the array. There are going to be up to 100 elements in the array. o If there are more than 100 characters then the input is invalid.

•

•

You must write the following functions: •

void mergeSort(int *arr, int size)

o The function recursively sorts the array.

•

void mergeArrays(int *leftArr, int leftSize, int *rightArr, int rightSize, int *destArr )

o The function merges the left and right arrays into destArr.

•

void copyArrays(int *srcArr, int *destArr, int size)

o The function copies the source array into the destination array. Example: Input:

10 10 9 8 7 6 5 4 3 2 1

Output:

1 2 3 4 5 6 7 8 9 10

The file name should be: mergeSort.c

Ex 7.2 – Binary Search Write a program that performs a binary search on a sorted array of integers.

Given a sorted array of elements and a query element, you compare the query against the element in the middle of the array (marked in green). If they are the same then there is nothing more to do. Otherwise, if the query is smaller than the element in the middle of the array, then it must appear before it in the array. So you need to search in the left half (marked in white). If it is bigger, then you need to search the right half (marked in yellow). You repeat this until, you find the element, or you can't divide the array no more. The program: • • • •

Reads an integer number, which tells how many numbers are in the array Reads the sorted array of integers. Reads an integer number, which will be the search query. Prints a message telling if the number appears in the array or not.

Assumptions: You will be given the first number. o You have to check that it is a valid number. o If it is valid then it gives the correct number of elements in the array. There are going to be up to 100 elements in the array. o If there are more than 100 characters then the input is invalid. o The numbers in the array are sorted. You will be given a query number.

•

•

•

You must write the following functions: •

int binarySearch(int *arr, int size, int query)

o The function performs a recursive binary search on the array. o It compares the query against the element in the center of the array. o The recursive call changes the pointer to the start of the array and the size of the array. o size represents the number of elements in the array pointed to by pointer. Example: Input:

13 10 15 23 26 28 31 33 36 42 49 57 101 437 57

Output:

Found it

Input:

13 10 15 23 26 28 31 33 36 42 49 57 101 437 39

Output:

Did not find it

The file name should be: binarySearch.c