In this project, you will work with defining tasks. You will implement a divide-and-conquer algorithm where the conquer component will be performed through creating a separate task.

Quicksort

First, you will implement quicksort on an array of unsorted unsigned 8-bit integers (unsigned char). Each time there are two sub-arrays to sort, the current task will sort one, while a new task will be generated to start the second.

Now, while quicksort is very efficient at sorting large arrays (where the run-time is Θ(n ln(n))), it is not very efficient at sorting short lists (the coefficients swamp the higher-order coefficients of other algorithms). You will have to choose a more efficient non-recursive non-divide-and-conquer in-place algorithm for sorting very short lists. Short may be arrays of size 10 or arrays of size 50, depending on the efficiency of your implementation. You will have to determine at which point your algorithm should be calling the non-recursive function.

You are welcome to read up on the implementation of introsort; however, you are also welcome to use any other in-place sorting algorithms such as insertion sort, bubble sort, selection sort, or shell sort. Your code must document your choices.

Ten percent of your grade will be based on how long it takes to sort large arrays relative to your peers when you use the semaphore implementation of your algorithm.

You will be required to implement quicksort using two approaches:

1. One approach will use semaphores, and
2. The other will use whatever technique you wish, with options including:
   • using priorities to ensure the child tasks finish first, or
   • using round-robin scheduling.

In whichever approach you use in the second case, you will have to somehow signal to the parent that the child is finished. You may do this either by changing priorities or by assigning to a variable that is being watched by the parent.

Quicksort implementation

Normally, you simply choose one value to be a pivot; however, this is somewhat sub-optimal, as on average it divides the array into a ratio of 3:1. Ideally, you would want to divide the array into two that are equal in size, that is 1:1. However, if you choose a pivot just by picking one (say, the middle entry), you would then proceed as follows:

• Replace the pivot with the entry at the end of the list, leaving that last entry blank.
• From the front searching for a value greater than the pivot, and searching from the back until you found a value less than the pivot. Having found these two, you would swap them.
• You would then continue searching forward and back, respectively, until the indices you were inspecting switched order.
• Finally, one of those two indices is still pointing to a value greater than the pivot. Take that one and move it to the blank at the end, replacing it with the pivot.
• At this point, everything in the entries up to the pivot is less than the pivot, and everything after the pivot is greater than the pivot: call quicksort recursively on both halves.

To see how you can speed this up, please see my slides and notes on using the median-of-three for quicksort at at 8.06.Quicksort.pptx and 8.06.Quicksort.pdf.

Implementation

In the source directory, you will notice a number of files.

array_tools.c array_tools.h main.c quicksort.c quicksort.h uart.c

The uart.c is an updated version of that file. Please download it. The array_tools library consists of functions that we will use to generate random arrays and to check that the arrays you return are sorted.

The main.c file will be the one we use to test your code, and the quicksort library files will be what you use to implement your version of quicksort. Please note, that the function quicksort takes a structure as an argument: it is an array structure that has two fields: a pointer to a character array and the length of that character array. Please see the arraytools header file to see the actual field names.

You will have to use the RTX RTOS in this project, and therefore you will have become familiar with the use of the operating system. You can read about all of the functions in the

RL-ARM User's Guide Library Reference

Specifically, you will have to set up your μVision target options. In μVision, after you create your project, you must select the Project→Options for Target 'Target_name'... (Alt+F7 or the icon.) Here, you will select RTX Kernel in the Operating system: drop-down box. You will also need to select Use MicroLIB. We will not need the additional memory we did in Project 2, so you need not make any additional changes to the Read/Only or Read/Write Memory Areas.

#include <stdbool.h>

bool is_sorted( int *array, size_t n ) {
    int i;

    for ( i = 1; i < n; ++i ) {
        if ( array[i - 1] > array[i] ) {
            return false;
        }
    }

    return true;
}