Нечетно-четного слияния дозатора - PullRequest
Новая
       6

Нечетно-четного слияния дозатора

1 голос
/ 30 мая 2010

Привет, у меня есть вопрос о нечетно-четном слиянии Бэтчера. У меня есть следующий код: 

public class Batcher {
  public static void batchsort(int a[], int l, int r) {
    int n = r-l+1;

    for (int p=1; p<n; p+=p)
      for (int k=p; k>0; k/=2)
        for (int j=k%p; j+k<n; j+=(k+k))
          for (int i=0; i<n-j-k; i++)
            if ((j+i)/(p+p) == (j+i+k)/(p+p))
              exch(a, l+j+i, l+j+i+k);
  }

  public static void main(String[] args) {
    int a[] = new int[] {2, 4, 3, 4, 6, 5, 3};

    batchsort(a, 0, a.length - 1);

    for (int i=0; i<a.length; i++) {
      System.out.println(a[i]);
    }
  }

  public static void exch(int a[], int i, int j) {
    int t = a[i];
    a[i] = a[j];
    a[j] = t;
  }
}

Я приведу несколько комментариев о функции кода:
Он делится на фазы, индексируемые переменной p, последняя фаза - это когда p==n - это дозаторы нечетно-четное слияние следующая фаза - это когда p==n/2 нечетно-четное слияние с Первая стадия и все компараторы, которые пересекают n / 2, исключают третью-последнюю фазу, когда p==n/4 нечетно-четное слияние с первыми двумя стадиями и все компараторы, которые пересекают любое кратное число n / 4, исключаются и так далее.

Результаты: 

3
3
4
4
5
2
6

Что я пропустил?
Что не так?

Ответы [ 3 ]

1 голос
/ 30 мая 2010

Я не знаю алгоритм, но вам нужно сравнить значения в пакетной сортировке, прежде чем их переключать, например, 

if ((j + i) / (p + p) == (j + i + k) / (p + p))
{
    if (a[l + j + i] > a[l + j + i + k])
    {
        exch(a, l + j + i, l + j + i + k);
    }
}

или это может быть более читабельным, если вы используете временные переменные для комбинированных индексов, например 

if ((j + i) / (p + p) == (j + i + k) / (p + p))
{
    int i1 = l + j + i;
    int i2 = l + j + i + k;
    if (a[i1] > a[i2])
    {
        exch(a, i1, i2);
    }
}

но вышеприведенные комментарии правы - это на самом деле написано не совсем читабельно. Вы должны убедиться, что одинаковые скобки имеют одинаковый отступ, что вложенные для () имеют больший отступ, чем их содержащий для и т. Д., И вам, вероятно, следует также выбрать более описательные имена переменных.

0 голосов
/ 10 октября 2017

Это фиксированная подпрограмма. 

void sort(int n)
{
  for (int p = 1; p < n; p += p)
    for (int k = p; k > 0; k /= 2)
      for (int j = k % p; j + k < n; j += k + k)
        //for (int i = 0; i < n - (j + k); i++) // wrong line
        for (int i = 0; i < k; i++)
          if ((i + j)/(p + p) == (i + j + k)/(p + p))
            printf("%2i cmp %2i\n", i + j, i + j + k);
}
0 голосов
/ 28 марта 2013 
     '* this assumes array() is globally available
     '* Batcher Odd-even mergesort is limited to power of 2 size arrays. it will
     '* malfunction in any other case. coded from c source by codeguy (qb64.net)
     SUB batcherOddEvenMergeSort (Start&, Finish&)
     IF (Finish& > 1) THEN
         m& = (Finish&) \ 2
         batcherOddEvenMergeSort Start&, m&
         batcherOddEvenMergeSort Start& + m&, m&
         batcheroddEvenMerge Start&, Finish&, 1
     END IF
     END SUB

     SUB batcheroddEvenMerge (Start&, Finish&, r&)
     m& = r& * 2
     IF m& > 0 AND m& < Finish& THEN
        batcheroddEvenMerge Start&, Finish&, m&
        batcheroddEvenMerge Start& + r&, Finish&, m&
        i& = Start& + r&
        DO
           IF i& + m& > Start& + Finish& THEN
              EXIT DO
           ELSE
              IF array(i&) > array(i& + r&) THEN
                swap array(i&), array(i& + r&)
             END IF
             i& = i& + m&
           END IF
        LOOP
     ELSE
        IF array(Start&) > array(Start& + r&) THEN
           swap array(Start&), array(Start& + r&)
        END IF
    END IF
    END SUB
    '* this is adapted from c code and works correctly
...