Учебники

Параллельный алгоритм — сортировка

Сентябрь 28, 2018

Сортировка — это процесс расположения элементов в группе в определенном порядке, то есть в порядке возрастания, в порядке убывания, в алфавитном порядке и т. Д. Здесь мы обсудим следующее:

  • Перечень сортировки
  • Нечетно-четное транспонирование
  • Параллельная сортировка слиянием
  • Hyper Quick Sort

Сортировка списка элементов — очень распространенная операция. Алгоритм последовательной сортировки может быть недостаточно эффективным, когда нам приходится сортировать огромный объем данных. Поэтому в сортировке используются параллельные алгоритмы.

Перечень сортировки

Сортировка перечисления — это способ упорядочения всех элементов в списке путем нахождения конечной позиции каждого элемента в отсортированном списке. Это делается путем сравнения каждого элемента со всеми другими элементами и определения количества элементов, имеющих меньшее значение.

Следовательно, для любых двух элементов a i и a j любой из следующих случаев должен быть истинным:

  • а я <а ж
  • а я > а ж
  • a i = a j

Алгоритм 

procedure ENUM_SORTING (n)

begin
   for each process P 1,j do
      C[j] := 0;
		
   for each process P i, j do
	
      if (A[i] < A[j]) or A[i] = A[j] and i < j) then
         C[j] := 1;
      else
         C[j] := 0;
			
   for each process P1, j do
      A[C[j]] := A[j];
		
end ENUM_SORTING

Нечетно-четная транспонированная сортировка

Нечетно-четная транспонированная сортировка основана на методе Bubble Sort. Он сравнивает два соседних числа и переключает их, если первое число больше второго, чтобы получить список в порядке возрастания. Противоположный случай применяется для ряда в порядке убывания. Нечетно-четная транспонированная сортировка работает в двух фазах — нечетной и четной фазах . На обоих этапах процессы обмениваются номерами со смежными номерами справа.

Нечетно-четная транспонированная сортировка

Алгоритм 

procedure ODD-EVEN_PAR (n) 

begin 
   id := process's label 
	
   for i := 1 to n do 
   begin 
	
      if i is odd and id is odd then 
         compare-exchange_min(id + 1); 
      else 
         compare-exchange_max(id - 1);
			
      if i is even and id is even then 
         compare-exchange_min(id + 1); 
      else 
         compare-exchange_max(id - 1);
			
   end for
	
end ODD-EVEN_PAR

Параллельная сортировка слиянием

Сортировка слиянием сначала делит несортированный список на наименьшие возможные подсписки, сравнивает его со смежным списком и объединяет его в отсортированном порядке. Он очень хорошо реализует параллелизм, следуя алгоритму «разделяй и властвуй».

Параллельная сортировка слиянием

Алгоритм 

procedureparallelmergesort(id, n, data, newdata)

begin
   data = sequentialmergesort(data)
	
      for dim = 1 to n
         data = parallelmerge(id, dim, data)
      endfor
		
   newdata = data
end

Hyper Quick Sort

Hyper quick sort — это реализация быстрой сортировки на гиперкубе. Его шаги следующие:

47
Share: