zrównoleglone sortowanie przez wstawianie z użyciem OpenMP

Witajcie.
Mam problem ze zrównolegleniem insert sorta.

Pierwsze co zrobiłem to zaimplementowałem wersję sekwencyjną:

#include <stdio.h>
#include <stdlib.h>
#include <omp.h>

int main()
{
	int N = 10;
       double X[10] = {0.4, -1.7, 2.2, 3.4, 2.2, -8.1, 9.2, -100, 99.01, 9};
	double klucz = 0;
	int j = 0;
	int i = 0;
	int c=0;

	for (c = 0; c<N; c++)
	printf("%.2f, ", X[c]);
	printf("\n");
	
	for (i=1;i<N;i++)
	{
		j=i;
		klucz=X[i];
		while ((X[j-1] >  klucz)&&(j>0))
		{
			X[j]=X[j-1];
			j--;
		}
		X[j]=klucz;
	}

	for (c = 0; c<N; c++)
	printf("%.2f, ", X[c]);
	printf("\n");

	return 0;
} 

Następnie próbowałem ją zrównoleglić, ale nie bardzo wiem jak to zrobić:

 #include <stdio.h>
#include <stdlib.h>
#include <omp.h>

int main()
{
	int N = 10;
       double X[10] = {0.4, -1.7, 2.2, 3.4, 2.2, -8.1, 9.2, -100, 99.01, 9};
	double klucz = 0;
	int j = 0;
	int i = 0;
	int c=0;

	for (c = 0; c<N; c++)
	printf("%.2f, ", X[c]);
	printf("\n");
	
	#pragma omp parallel for num_threads(4) private(i)

	for (i=1;i<N;i++)
	{
		j=i;
		klucz=X[i];
		while ((X[j-1] >  klucz)&&(j>0))
		{
			#pragma omp critical			
			X[j]=X[j-1];
			j--;
		}
		X[j]=klucz;
	}

	for (c = 0; c<N; c++)
	printf("%.2f, ", X[c]);
	printf("\n");

	return 0;
}

Powyższy kod zadziała w 7 przypadkach na 10...

A jak niby miałoby działaś zrównoleglenie sortowania przez wstawianie? Co tam się wg ciebie może wykonywac równolegle?

Kilka wątków równolegle powinno móc jakoś wstawiać liczby w odpowiednie miejsca.
Dostałem takie zadanie, siedzę nad nim 3ci dzień i już nie mam pomysłu.

To bardzo ciekawe co mówisz, ale ciekawi mnie jak wg ciebie kilka wątków miałoby to zrobić. Bo mnie się jednak wydaje że tak sortować można tylko po jednej liczbie na raz...
Może ci się pomyliło z jakimś quicksortem albo mergesortem? ;]

Shalom napisał(a):

To bardzo ciekawe co mówisz, ale ciekawi mnie jak wg ciebie kilka wątków miałoby to zrobić. Bo mnie się jednak wydaje że tak sortować można tylko po jednej liczbie na raz...
Może ci się pomyliło z jakimś quicksortem albo mergesortem? ;]

Uwierz mi, że mam kartkę przed oczami, na której jest napisane "... metodą przez wstawianie".
Sam jestem w szoku. Doszedłem do wersji równoległej, która tak naprawdę czeka, co daje w efekcie algorytm sekwencyjny...

Może ma być sortowanie Shella i wtedy jako tako da się to zrobić.