Even$-$Odd Sort:

This is the compare and swap function. Pass $=0==>$ even pass. Pass $=1==>$ odd pass.

int Sort$($int Pass, int x$[],$ int n$)$

$\{$

int i$,$ temp, Swapped $=$ FALSE;

for $($i $=1+$ Pass; i $$ n$,$ i $+=2)$

if $($x$[$i$-1]>$ x$[$i$])\{$

temp $=$ x$[$i$-1]$;

x$[$i$-1]=$ x$[$i$]$;

x$[$i$]=$ temp;

Swapped $=$ TRUE;

$\}$

$\}$

return Swapped;

$\}$

$/*$ This is the even$-$odd sorting function $*/$

#define Even $0$

#define Odd $1$

int Swapped, i$,$ n;

Swapped $=$ TRUE;

while $($Swapped$)\{$

Swapped $=$ Sort$($Even$,$ x$,$ n$)$;

Swapped $=$ Swapped $||$ Sort$($Odd$,$ x$,$ n$)$;

$\}$

The number of comparisons in each iteration is n$.$ The total number of comparisons to sort the array is O$($n$2).$

Making the Even$-$Odd Sort Concurrent:

The Even$-$Odd sort can easily be converted to a concurrent version. All of the n$/2$ comparisons in each pass are independent of each other, and can be executed concurrently. For each even or odd pass, create n$/2$ threads, each compares two adjacent entries of the array and swaps them if needed. Once a pass completes, either kill all threads and create another n$/2$ new threads to perform the next pass or use the original n$/2$ threads to sort a different pair of adjacent elements. Be very careful so that race conditions do not occur.

The Algorithm:

Suppose the input array x$[*]$ has n numbers. Use a while loop that iterates at most n times as shown earlier. In each iteration, do the following until no swaps occur.

Even Pass:

Create at most n$/2$ threads: T$1,$ T$3,$ T$5,$ etc. Thread Tk compares x$[$k$-1]$ and x$[$k$].$ If x$[$k$1]$ and x$[$k$]$ are out of order, thread Tk swaps them and sets a flag to indicate a swap has occurred. Wait until all threads finish their work. This completes an even pass of this iteration.

Odd Pass:

Create at most n$/2$ threads: T$2,$ T$4,$ T$6,$ etc. Thread Tk compares x$[$k$-1]$ and x$[$k$].$ If x$[$k$1]$ and x$[$k$]$ are out of order, thread Tk swaps them and sets a flag to indicate a swap has occurred. Wait until all threads finish their work. This completes an odd pass of this iteration.

Final Test: Break this while loop if no swaps occurred because the array has been sorted.

In this concurrent version, if we ignore the cost of all thread creation and termination, we need at most n$/2$ even passes and n$/2$ odd passes $($i$.$e$.,$ O$($n$)$ passes$).$ In each even or odd pass, all comparisons are done concurrently, so each pass only takes the time of comparing one pair of numbers $($i$.$e$.,$ O$(1)$ time$).$

Program Logic

Write a program $($i$.$e$.,$ the main$)$ to read in n integers into the array x$[*],$ and iterate at most n times. In each iteration, the main creates at most n$/2$ threads to execute an even pass and then another n$/2$ threads to execute an odd pass. The main must wait until all created threads of this pass complete before going for the next pass. If none of the even pass and odd pass swapped any numbers, the main prints out the sorted array.

The input array should be read in from stdin. The input array x$[*]$ and the flag that indicated if any numbers have been swapped are global variables shared by all threads. You can only use the above program structure and the indicated thread creation and thread join. No other thread and$/$or process functions can be used for this program.

The input to your program should be taken from stdin. Your executable must be named as prog$3.$ The command line looks like the following, where input$-$filename is a file from which prog$3$ reads in the input values:

$./$prog$3$ input$-$filename

The input file has the following format, where n is a positive integer, and x$0,$ x$1,...,$ xn$-1,$ are n distinct integers. Assume all input values being correct small numbers $($i$.$e$.,$ in the range of $0$ and $999).$

n

x$0$ x$1$ x$2...$ xn$-1$

Suppose the command line is

$./$prog$3$ in$.$txt

and the file in$.$txt has the following lines:

$8$

$71328459$

View the picture

$1.$ All programs must be written in C$++.$

$2.$ The following approach will be used to compile and test programs:

make noVisual make your program w$/$o visualization

$./$prog$3$ in$.$txt test your program

This procedure may be repeated a number of times with different input files to see if your program works correctly.

$3.$ Your implementation should fulfill the program specifications as stated.

README.txt is required to answer the following questions:

$1.$ Are there any race conditions in this even$-$odd sort?

$2.$ In each iteration, main$()$ does the creation and join for the completion of n$/2$ threads twice, one for even pass and one for odd pass. It requires a significant amount of time in creating and joining threads. If you use extra variables$/$arrays and busy waiting, can you create n$/2$ threads and let them do even pass and odd pass in the same iteration without race conditions and still deliver correct results?

$3.$ Can you create n$/2$ threads at the very beginning and let them do all the even pass and odd pass comparisons? This saves time on creating and joining threads. Suggest a solution and discuss its correctness.

Elaborate each answer and provide details.