# 14.5. Exercises#

Many of these exercises are taken from past exams of APS105 Computer Fundamentals courses at University of Toronto. The solutions are provided in the answer boxes.

Headings in this page classify the exercises into different categories: [Easy], [Intermediate], and [Challenging]. I suggest you start by easy exercises and work your way up to the challenging ones.

Question 3 in Winter 2019 Final Exam[Easy]

The following array of integers is the result of the first round of partitioning, used in the Quicksort algorithm to sort the array in ascending order. Identify the possible array element or elements that could have been used as the pivot in the first partitioning round. Justify your answer; guessing an answer with no justifications will result in a mark of zero.

{15, 6, 45, 60, 32, 71, 102, 81}


Question 5 in Winter 2019 Final Exam[Easy]

We have a number of TAs who have carefully marked a large number of final exams and now must sort them alphabetically.

[PLEASE NOTE that this question is not worth many marks, so answer with a phrase! Do not spend time elaborating.]

(a) Here are some sorting methods you know about. Which ones would work well, and which not well to allow the TAs to most quickly sort the exams? Why or why not would the particular method work well or not?

Method

OK?

Reason

Insertion Sort

Selection Sort

Bubble Sort

Quicksort

(b) What may be a better sorting method?

Question 15 in Winter 2018 Final Exam[Intermediate]

Write a C function called sortOddEven() that rearranges the order of the elements in an integer array such that all odd numbers are to the left of all even numbers. The function has two parameters: a pointer to the integer array and an integer specifying the number of elements in the array. The odd numbers can be in any order, as long as they are all to the left of any even number, and the even numbers can be in any order, as long as they are all to the right of any odd number.

For example, if the elements of the array initially are:

1 4 6 5 9 3 8 2


then after sortOddEven() processes the array, the elements may become:

1 3 9 5 6 4 8 2


Note: In your solution, you may not declare or use another array

Question 10 in Fall 2015 Final Exam[Intermediate]

Consider the following C struct and typedef declarations:

struct studentRecord {
char *name;
double GPA;
};

typedef struct studentRecord Record;


Write a complete C function bubbleSortRecords, for which the prototype is given below, that uses the bubble sort algorithm to sort an array of n elements of type Record. The function should sort the elements in ascending order of GPA, and in the event of a tie, should break ties in alphabetical order of name, where name is a pointer to a string. You may use a function from the string library, string.h, in your answer. Hint: use the library function to compare two strings.

void bubbleSortRecords(Record records[], int n);


Question 13 in Winter 2017 Final Exam[Intermediate]

Quicksort is considered one of the fastest sorting algorithms in practice. However, it turns out that insertion sort is faster than quicksort for smaller arrays; e.g., for arrays with 10 or fewer elements. Because of this, many implementations use a combination of both algorithms: they use quicksort when the size of the array segment to be sorted is larger than 10, but switch over to insertion sort when the size of the array segment to be sorted is less than or equal to 10.

Your job is to implement quicksort for an array of doubles that automatically switches over to insertion sort for the small array segments with less than or equal to 10 elements. To make your job easier, you can assume the following function is available:

int selectPivotAndPartition(double list[], int from, int to);


This function processes the segment of array list from index from to index to. It selects a pivot in a smart way, and then partitions all elements in the [from, to] segment so that all elements less than or equal to pivot are located to the left of the pivot element and all elements greater than or equal to pivot are located to the right of the pivot element. The function then returns the index of the array where the pivot is located. Hence, after you call

int pIndex = selectPivotAndPartition(list, from, to);


you are guaranteed that

list[i] <= list[pIndex] when fromipIndex

and

list[i] >= list[pIndex] when pIndexito

Question 11 in Winter 2019 Final Exam[Challenging]

In general, the bubble sort algorithm can be explained in two steps.

1. For each pair of adjacent elements: if they are out-of-order, then swap.

2. Repeat the first step until no swaps are done.

Write a function, bubbleSortLinkedList, that sorts a linked list using the bubble sort algorithm. The function has one parameter: a pointer to a LinkedList (assume that this pointer is not NULL). The function will modify the linked list in-place so that the values are in ascending order (i.e., 1 comes before 2). The definitions for a LinkedList and Node are shown below.

You must abide by the following constraints. Failure to meet a constraint will result in a grade of zero for this question.

1. Your function must not modify the next pointer of any node.

2. You cannot create any other data structures (e.g., an array, another linked list, etc.).

3. Your function cannot call any other functions.

4. Your function must not cause a segmentation fault.

typedef struct node {
int data;
struct node *next;
} Node;