10/19/2015
`
`users.cms.caltech.edu/~cs284/programs/quicksort/quicksort.c
`
`/*‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐*/
`/* Sequential and Multithreaded Quicksort Function Definitions                */
`/*                                                                            */
`/* Written by: John Thornley, Computer Science Dept., Caltech.                */
`/* Date: October, 1997.                                                       */
`/*                                                                            */
`/* Algorithm:                                                                 */
`/* ‐ recursive quicksort.                                                     */
`/* ‐ median of first, middle, and last item chosen as pivot in partitioning.  */
`/* ‐ insertion sort of base‐case arrays.                                      */
`/* ‐ separate threads for recursive quicksort calls.                          */
`/* ‐ sequential quicksort after enough threads created.                       */
`/*                                                                            */
`/* Copyright (c) 1997 by John Thornley.                                       */
`/*‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐*/
`
`#include <stdio.h>
`#include <assert.h>
`#include <sthreads.h>
`#include <bool.h>
`#include "quicksort.h"
`
`/*‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐*/
`/* Base‐case length (below which insertion sort is faster than quicksort)     */
`/*‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐*/
`
`#define BASE_LENGTH 64 /* 64 works well for 200 MHz Pentium Pro */ 
`
`/*‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐*/
`/* Handle errors from Sthreads function calls                                 */
`/*‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐*/
`
`void handle_sthread_error(int error_code)
`
`{ 
`
`   char error_message[100];
`
`    if (error_code != STHREAD_ERROR_NONE) {
`        sthread_sprint_error(error_message, error_code);
`        fprintf(stderr, "Sthread error: %s\n", error_message);
`        exit(EXIT_FAILURE);
`    }
`
`} /
`
`*‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐*/
`/* Insertion sort for sorting base‐case arrays                                */
`/*‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐*/
`
`static void insertion_sort(int n, item data[])
`
`{ 
`
`   int i, j, k;
`    item temp;
`
`    assert(n >= 0);
`
`    for (i = 1; i < n; i++) {
`        temp = data[i];
`        k = 0;
`        for (j = i ‐ 1; j >= 0; j‐‐)
`            if (temp < data[j])
`                data[j + 1] = data[j];
`
`http://users.cms.caltech.edu/~cs284/programs/quicksort/quicksort.c
`
`1/4
`
`1
`
`AMI/MSI/GBT EX 1009
`IPR of Pat. No. 6,282,641
`
`

`
`users.cms.caltech.edu/~cs284/programs/quicksort/quicksort.c
`
`10/19/2015
`            else {
`                k = j + 1;
`                break;
`            }
`        data[k] = temp;
`    }
`
`} /
`
`*‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐*/
`/* Swap two items                                                             */
`/*‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐*/
`
`#define SWAP(x, y) {item temp; temp = x; x = y; y = temp;}
`
`/*‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐*/
`/* Choose pivot value and partition data array                                */
`/*‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐*/
`
`static void partition(int n, item data[], int *pivot)
`
`{ 
`
`   item pivot_value;
`    int left, right;
`
`    assert(n >= 3);
`
`    SWAP(data[1], data[(n ‐ 1)/2])
`    if (data[1] > data[n ‐ 1])
`        SWAP(data[1], data[n ‐ 1])
`    if (data[0] > data[n ‐ 1])
`        SWAP(data[0], data[n ‐ 1])
`    if (data[1] > data[0])
`        SWAP(data[1], data[0])
`    pivot_value = data[0];
`    left = 1; right = n ‐ 1;
`    while (true) {
`        do left++; while (data[left] < pivot_value);
`        do right‐‐; while (data[right] > pivot_value);
`        if (right < left) break;
`        SWAP(data[left], data[right])
`    }
`    data[0] = data[right];
`    data[right] = pivot_value;
`    *pivot = right;
`
`} /
`
`*‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐*/
`/* Sequential quicksort                                                       */
`/*‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐*/
`
`void seq_quicksort(int n, item data[])
`
`{ 
`
`   assert(n >= 0);
`    assert(BASE_LENGTH >= 2);
`
`    if (n <= BASE_LENGTH)
`        insertion_sort(n, data);
`    else {
`        int pivot;
`
`        partition(n, data, &pivot);
`        seq_quicksort(pivot, &data[0]);
`http://users.cms.caltech.edu/~cs284/programs/quicksort/quicksort.c
`
`2/4
`
`2
`
`

`
`users.cms.caltech.edu/~cs284/programs/quicksort/quicksort.c
`10/19/2015
`        seq_quicksort(n ‐ pivot ‐ 1, &data[pivot + 1]);
`    }
`
`} /
`
`*‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐*/
`/* Multithreaded quicksort (pragma version)                                   */
`/*‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐*/
`/*
`void multi_quicksort(int n, item data[], int t)
`
`{ 
`
`   assert(n >= 0);
`    assert(BASE_LENGTH >= 2);
`    assert(t >= 1);
`
`    if (n <= BASE_LENGTH || t == 1)
`        seq_quicksort(n, data);
`    else {
`        int pivot;
`
`        partition(n, data, &pivot);
`        #pragma multithreadable
`        {
`            multi_quicksort(pivot, &data[0], t ‐ t/2);
`            multi_quicksort(n ‐ pivot ‐ 1, &data[pivot + 1], t/2);
`        }
`    }
`
`}*
`
`/
`/*‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐*/
`/* Multithreaded quicksort (Sthreads version)                                 */
`/*‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐*/
`
`typedef struct {
`    int n, t, pivot;
`    item *data;
`} block_args;
`
`static void statement_0(block_args *args)
`
`{ 
`
`   multi_quicksort(
`        args‐>pivot, &(args‐>data)[0], args‐>t ‐ args‐>t/2);
`
`} s
`
`{ 
`
`   multi_quicksort(
`        args‐>n ‐ args‐>pivot ‐ 1, &(args‐>data)[args‐>pivot + 1], args‐>t/2);
`
`tatic void statement_1(block_args *args)
`
`oid multi_quicksort(int n, item data[], int t)
`
`} v
`
`{ 
`
`   assert(n >= 0);
`    assert(BASE_LENGTH >= 2);
`    assert(t >= 1);
`
`    if (n <= BASE_LENGTH || t == 1)
`        seq_quicksort(n, data);
`    else {
`        int pivot;
`        void (*statement[2])(block_args *args);
`        block_args args;
`http://users.cms.caltech.edu/~cs284/programs/quicksort/quicksort.c
`
`3/4
`
`3
`
`

`
`10/19/2015
`        int error_code;
`
`users.cms.caltech.edu/~cs284/programs/quicksort/quicksort.c
`
`        partition(n, data, &pivot);
`        statement[0] = statement_0;
`        statement[1] = statement_1;
`        args.n = n; args.t = t; args.pivot = pivot; args.data = data;
`        error_code = sthread_block(
`            2, (void (**)(void *)) statement, (void *) &args,
`            STHREAD_MAPPING_SIMPLE, 0,
`            STHREAD_PRIORITY_PARENT, STHREAD_STACK_SIZE_DEFAULT);
`        handle_sthread_error(error_code);
`    }
`
`} /
`
`*‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐*/
`
`http://users.cms.caltech.edu/~cs284/programs/quicksort/quicksort.c
`
`4/4
`
`4