Description
Question 1 [25 points]
– Implement this part in assignment3.c
Recall the Quick Sort algorithm and its rearrange function.
[15 points] Implement the rearrange function.
// used for QuickSort:
// the function rearranges the elements, and
// returns the index of the pivot after the rearrangement
int rearrange(int* array, int n, int pivot_index);
[10 points] Implement the QuickSort algorithm. Use your rearrange function as a
subroutine. For the pivot choose 3 random elements, and let the pivot be their median.
// QuickSort algorithm
void quick_sort(int* array, int n);
Question 2 [25 points]
– Implement this part in assignment3.c
Recall the MergeSort algorithm and its merging function.
[15 points] Implement the merging function.
// used for MergeSort:
// the function gets an array of length n
// and the index of the midpoint.
// the assumption is that ar[0…mid-1] is sorted
// and ar[mid…n-1] is sorted
// the function merges the two halves into a sorted array
void merge(int* array, int n, int mid);
[10 points] Implement the MergeSort algorithm. Use your merge() function as a subroutine.
// MergeSort algorithm
void merge_sort(int* array, int n);
Question 3 [30 points (15 points each item)]
– Implement this part in stack.c.
– In this question you may only use the following functions to access the (unbounded)
stack of ints. The interface for stack is provided in stack.h.
– The stack functions are implemented in stack.c, but you should not make
assumptions about the exact implementation details. You may use only the
signatures of the functions from stack.h.
typedef struct {
// not known
} stack3_t;
// creates a new stack
stack3_t* stack_create();
// pushes a given item to the stack
void stack_push(stack3_t* s, int item);
// pops the top element from the stack
// Pre condition: stack is not empty
int stack_pop(stack3_t* s);
// checks if the stack is empty
bool stack_is_empty(stack3_t* s);
// frees the stack
void stack_free(stack3_t* s);
a) Write a function that gets a stack and returns the number of elements in it. When the
function returns the stack must be in its initial state.
// returns the number of elements in the stack
int stack_length(stack3_t* s)
b) Write a function that gets two stacks and checks if all elements in s1 are strictly less
than all elements in s2. When the function returns the stacks must be in their initial
state. (If s1 or s2 is empty, the function returns true)
// checks if all elements in s1 are < than all elements in s2
bool stack_strictly_less(stack3_t* s1, stack3_t* s2)
Question 4 [30 points – struct 6 points, each function 4 points]
– Implement this part in queue.h and queue.c
In this question you need to implement the ADT queue of ints.
Use the idea with 2 pointers we saw in class.
Implement the struct in the header file queue.h.
Implement the functions in queue.c.
typedef struct {
// implement me
} queue_t;
// creates a new queue
// if malloc fails, returns NULL
queue_t* queue_create();
// add a given item to the queue
// if everything works ok, returns same q as the input
// if malloc fails, returns NULL
queue_t* enqueue(queue_t* q, int item);
// removes an element from the queue
// Pre condition: queue is not empty
int dequeue(queue_t* q);
// checks if the queue is empty
bool queue_is_empty(queue_t* q);
// returns the length of the queue
// if q==NULL, returns -1
int queue_length(queue_t* q);
// frees the queue
// if q==NULL, returns -1
void queue_free(queue_t* q);