Question

Using pthread_create(), pthread_join(), and pthread_exit(), write a C or C++ program running on VirtualBox Debian VM shell to sort a list of signed integers in nondecreasing order using the sorting algorithm of your own choice from a text file containing the integers.

The input data should be stored in a file named p2data.txt

Sort a list of signed integers in nondecreasing order using three threads, among which two of them are sorting threads responsible for sorting each of the two sublists, while the third thread (i.e. the merging thread) is responsible for merging the two sorted sublists into a single sorted list. You may assume that the total number of integers in the list is less than or equal to 20.

Answer 1

Hi! :)

Here's the documented code to solve the assignment:

prog.c:

#include <stdio.h>
#include <pthread.h>

// reads in the list from p2data.txt and stores in A and stores the length of the list in the integer pointed to by N
void readList(int* A, int* N)
{
    FILE* file = fopen("p2data.txt", "r");

    int index = 0;

    while(!feof(file))
    {
        int number;
        fscanf(file, "%d ", A + index);
        ++index;
    }

    *N = index;

    fclose(file);
}

// swaps the content of the integers pointed by l and r
void swap(int* l, int* r)
{
    int temp = *l;
    *l = *r;
    *r = temp;
}

// struct for passing a sublist to sortSubList
struct SubList
{
    int* A;
    int l;
    int r;
};

// sorts a sublist using selection sort
void* sortSubList(void* varargp)
{
    // getting the array from the arguments
    struct SubList* subList = (struct SubList*) varargp;
    int* A = subList->A;
    int l = subList->l;
    int r = subList->r;

    // selection sort
    for(int i = l; i <= r; ++i)
    {
        int smallestIndex = i;

        for(int j = i + 1; j <= r; ++j)
        {
            if(A[j] < A[smallestIndex])
            {
                smallestIndex = j;
            }
        }

        swap(A + i, A + smallestIndex);
    }

    return NULL;
}

// merges two sorted sublists
// left sublist: A[0...N/2]
// right sublist: A[N/2-1...N-1]
void merge(int* A, int N)
{
    int temp[N];

    int l = 0;
    int r = N / 2 + 1;
    int k = 0;

    while(l <= N / 2 && r <= N - 1)
    {
        if(A[l] < A[r])
        {
            temp[k++] = A[l++];
        }
        else
        {
            temp[k++] = A[r++];
        }
    }

    while(l <= N / 2)
    {
        temp[k++] = A[l++];
    }

    while(r <= N - 1)
    {
        temp[k++] = A[r++];
    }

    for(k = 0; k < N; ++k)
    {
        A[k] = temp[k];
    }
}

// sorts the list using three threads
void sortList(int* A, int N)
{
    // the sublists
    struct SubList leftSubList = {A: A, l: 0, r: N / 2};
    struct SubList rightSubList = {A: A, l: N / 2 + 1, r: N - 1};

    // these two threads store the thread ids
    pthread_t left_thread_id;
    pthread_t right_thread_id;

    // threads for sorting the sublists
    pthread_create(&left_thread_id, NULL, sortSubList, (void*) &leftSubList);
    pthread_create(&right_thread_id, NULL, sortSubList, (void*) &rightSubList);

    // joining the threads after sorting is done
    pthread_join(left_thread_id, NULL);
    pthread_join(right_thread_id, NULL);

    // the third thread, i.e., the main thread merges the sorted sublists
    merge(A, N);
}

// prints the list
void printList(int* A, int N)
{
    puts("Sorted list:");

    for(int i = 0; i < N; ++i)
    {
        printf("%d\n", A[i]);
    }
}

int main()
{
    int A[20]; // stores the list
    int N; // stores the length of the list

    readList(A, &N);
    sortList(A, N);
    printList(A, N);

    return 0;
}

Here's the screenshot of a demo run:

Hope this helps! :)