I want to try to understand the method of using POSIX threads to interact with a sorting algorithm such as the odd-even transposition sort.

I have written my program to do a odd-even transposition sort without threads and this is my current result:

./sort data
File opened successfully.
The numbers are:
Before sort::
20 19 18 17 16 15

After phase 0:
19 20 17 18 15 16

After phase 1:
19 17 20 15 18 16

After phase 2:
17 19 15 20 16 18

After phase 3:
17 15 19 16 20 18

After phase 4:
15 17 16 19 18 20

After phase 5:
15 16 17 18 19 20

After sort::
15 16 17 18 19 20

This is the current part of my code where I am trying to make the threads correctly and do the start function from pthread_create():

int list[20];
int n = 20;
int param[10];
pthread_t threads[10];

void *startPoint( void *arg )
   //threads interact with odd-even sorting here

int main(int argc, char** argv)
        pthread_attr_t tattr; // thread attributes
        pthread_t tid;
	readLINE(argv[1]); //reads the data file and loads it into the list array

        pthread_attr_init (&tattr);
        pthread_attr_setscope (&tattr, PTHREAD_SCOPE_SYSTEM);
		display(list, n, "Before sort:");
		for(int count = 0; count < n/2; count++)
			param[count] = count*2;
		        pthread_create( &threads[ count], NULL, startPoint, (void*) &param[count]);	
                //Regular sort w/o multi-threading
		//Odd_even_sort(list, n);
		display(list, n, "After sort:");


I am not really sure how many threads I need to create for each phase of sorting. I can see it visually with a picture, but to implement it is confusing.

Here's a picture:


Also, how do I make the threads interact with the actual sorting procedure after I've created them?

7 Years
Discussion Span
Last Post by Banfa

I think you will find it very hard to code this sorting algorithm as anything other than single threaded. The problem is that every phase of your algorithm depends on the previous phase so no phase can be done independently of any other.

If you want to use multiple threads for sorting you will need to choose an algorithm that is suited to rather than the simple sort you appear to be using. For example a merge sort that sorts a list by recursively into 2 lists sorting each of those lists and then merging the 2 sorted lists back into 1.

Sorting the 2 halfs of a list could easily be done by 2 threads.

Merge sort is by no means the only algorithm that leads itself to multiple threads in this manor.

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.