Lab 3 - Parallel Sorting and Searching Algorithms

Introduction

In this laboratory, we will discuss some examples of parallel sorting algorithms.

📄️ Odd-Even Transposition Sort (OETS)

One of the most well-known (though not necessarily efficient) sorting algorithms is bubble sort. It operates based on the following pseudocode:

📄️ Shear Sort

Another example of a sorting algorithm designed for multi-processor systems where each processor is connected to only a portion of the other processors is shear sort (also known as row-column sort or snake-order sort). It assumes that we are working with processors connected in a matrix-like form. In this setup, a processor can communicate with neighbors to the left, right, above, and below. If we imagine that processors are arranged in a matrix, the two phases of the shear sort algorithm are as follows:

📄️ Merge Sort

Merge sort (or merge sorting) is a divide and conquer sorting algorithm that follows these general steps:

📄️ Parallel Binary Search

The parallel binary search algorithm is based on dividing the sequence in which the search is performed into P subsequences of the same length. At each step, each of the P processors checks whether a value x is present in the subsequence assigned to that processor by comparing the value of x with the values at the start and end positions, marking the boundaries of the processor's subsequence.

📄️ Exercises

1. Starting from the sequential implementation of the bubble sort algorithm found in the oets.c file from the lab skeleton, implement and parallelize the odd-even transposition sort algorithm.