Я кодирую сортировку слиянием, которая разбивается на 3, я понятия не имею, почему это не работает - PullRequest
Новая
       27

Я кодирую сортировку слиянием, которая разбивается на 3, я понятия не имею, почему это не работает

0 голосов
/ 19 сентября 2019

Это все, что у меня есть в коде, оно должно отображать расположенные числа.Код должен разбивать массив чисел на 3, а не на 2, как это делает обычная сортировка слиянием.Я проверил каждую его часть, и я не могу найти, почему она не работает 

#include <iostream>

using namespace std;

void merge(int*,int*,int,int,int,int);

//mergesort
void mergesort(int *a, int*b, int low, int high)
{

    if(high - low <2)
      return;

    int pivot1 = low+((high-low)/3);
    int pivot2 = low+2*((high-low)/3)+1;
    mergesort(a,b,low,pivot1);
    mergesort(a,b,pivot1,pivot2);
    mergesort(a,b,pivot2,high);
    merge(a,b,low,pivot1,pivot2,high);
}

//merge
void merge(int *a, int *b, int low, int pivot1, int pivot2, int high)
{
    int h,i,j,l;
    h=low;
    i=low;
    j=pivot1;
    l=pivot2;

    while((h<pivot1)&&(j<pivot2)&&(l<high))
    {
        if(a[h]<a[j])
        {
          if(a[h] < a[l]){
            b[i] = a[h];
            i++;
            h++;
          }
          else{
            b[i] = a[l];
            i++;
            l++;
          }
       }
       else{
         if(a[j] < a[l]){
          b[i] = a[j];
          i++;
          j++;
         }
         else{
           b[i] = a[l];
           i++;
           l++;
         }
       }
    }

    while((h < pivot1) && (j < pivot2)){
      if(a[h] < a[j]){
    b[i] = a[h];
    i++;
    h++;
      }
      else{
    b[i] = a[j];
    i++;
    j++;
      }
    }

    while((j < pivot2) && (l < high)){
      if(a[j] < a[l]){
    b[i] = a[j];
    i++;
    j++;
      }
      else{
    b[i] = a[l];
    i++;
    l++;
      }
    }

    while((h < pivot1) && (l < high)){
      if(a[h] < a[l]){
    b[i] = a[h];
    i++;
    h++;
      }
      else{
    b[i] = a[l];
    i++;
    l++;
      }
    }
    while(h < pivot1){
      b[i] = a[h];
      i++;
      h++;
    }
    while(j < pivot2){
      b[i] = a[j];
      i++;
      j++;
    }
    while(l < high){
      b[i] = a[l];
      i++;
      l++;
    }
}

int main()
{
    int a[] = {12,10,43,23,-78,45,123,56,98,41,90,24};
    int num;

    num = sizeof(a)/sizeof(int);

    int b[num];

    mergesort(a,b,0,num-1);

    for(int i=0; i<num; i++)
        cout<<b[i]<<" ";
    cout<<endl;
}

она должна отображать отсортированную версию массива

1 Ответ

0 голосов
/ 19 сентября 2019

Ваш код не компилируется.Чтобы перейти к g++ -Wall -Werror, мне нужно было добавить следующие строки в начало файла: 

#include <iostream>

using namespace std;

Ваш код читает только из массива a и записывает в массив b.Нигде «отсортированное» содержимое из b не копируется обратно в a.

Я предполагаю, что вы хотите, чтобы это произошло в merge(), то есть путем добавления в конец функции: 

for(int i=low; i<high; i++)
    a[i] = b[i];

Кроме того, имеется ошибка off-by-one в main(): mergesort() ожидает, что high будет общим количеством сортируемых элементов, а нет индекс самого высокого элемента в массиве: 

mergesort(a,b,0,num);

С этими изменениями код компилирует и выводит правильный результат 

-78 10 12 23 24 41 43 45 56 90 98 123

РЕДАКТИРОВАТЬ

Передача массива b также не требуется, поскольку в действительности это необходимо только для выполнения слияния.Следовательно, код может быть обновлен следующим образом: 

void merge(int*,int,int,int,int);

//mergesort
void mergesort(int *a, int low, int high)
{
    ...
    mergesort(a,low,pivot1);
    mergesort(a,pivot1,pivot2);
    mergesort(a,pivot2,high);
    merge(a,low,pivot1,pivot2,high);
}

//merge
void merge(int *a, int low, int pivot1, int pivot2, int high)
{
    int b[high];
    ...
}

int main()
{
    int a[] = {12,10,43,23,-78,45,123,56,98,41,90,24};
    int num = sizeof(a) / sizeof(*a);

    mergesort(a,0,num);

    for(int i=0; i<num; i++)
        cout<<a[i]<<" ";
    cout<<endl;
}

РЕДАКТИРОВАТЬ 2

Потребление памяти на merge() может быть уменьшено, поскольку при каждом вызове он сортирует только срез a[low..high-1].Следовательно, код можно обновить следующим образом: 

//merge
void merge(int *a, int low, int pivot1, int pivot2, int high)
{
    int b[high - low]; // slice a[low..high - 1] to be sorted
    int i = 0;         // running index in b[]
    ...
    // replace slice a[low.. high - 1] with sorted result
    for (i = low; i < high; i++)
       a[i] = b[i - low];
}

БОНУС

Полный код упрощен и более читабелен: 

#include <iostream>

using namespace std;

static void merge(int *a,
                  const unsigned int low,    const unsigned int pivot1,
                  const unsigned int pivot2, const unsigned int high);

// mergesort (recursive)
static void mergesort(int *a, const unsigned int low, const unsigned int high)
{
    const unsigned int slice = high - low;

    // terminate recursion
    if (slice < 2)
        return;
    if (slice < 3) {
        // can't recurse for slice of length 2; just sort using 2 partitions
        merge(a, low, low, low + 1, high);
        return;
    }

    const unsigned int third  = slice / 3;
    const unsigned int pivot1 = low  + third;
    const unsigned int pivot2 = high - third;

    // recurse
    mergesort(a, low,    pivot1);
    mergesort(a, pivot1, pivot2);
    mergesort(a, pivot2, high);

    // merge
    merge(a, low, pivot1, pivot2, high);
}

// merge
static void merge(int *a,
                  const unsigned int low,    const unsigned int pivot1,
                  const unsigned int pivot2, const unsigned int high)
{
    int sorted[high - low];           // slice a[low..high - 1] to be sorted
    int *store = sorted;              // running pointer into sorted[]
    unsigned int partition1 = low;    // running index a[low    .. pivot1 - 1]
    unsigned int partition2 = pivot1; // running index a[pivot1 .. pivot2 - 1]
    unsigned int partition3 = pivot2; // running index a[pivot2 .. high   - 1]

    while ((partition1 < pivot1) &&
           (partition2 < pivot2) &&
           (partition3 < high)) {
        if (a[partition1] < a[partition2])
            *store++ = a[partition1] < a[partition3] ? a[partition1++] : a[partition3++];
        else
            *store++ = a[partition2] < a[partition3] ? a[partition2++] : a[partition3++];
    }

    while ((partition1 < pivot1) &&
           (partition2 < pivot2)) {
        *store++ = a[partition1] < a[partition2] ? a[partition1++] : a[partition2++];
    }

    while ((partition2 < pivot2) &&
           (partition3 < high)) {
        *store++ = a[partition2] < a[partition3] ? a[partition2++] : a[partition3++];
    }

    while ((partition1 < pivot1) &&
           (partition3 < high)) {
        *store++ = a[partition1] < a[partition3] ? a[partition1++] : a[partition3++];
    }

    while (partition1 < pivot1)
        *store++ = a[partition1++];

    while (partition2 < pivot2)
        *store++ = a[partition2++];

    while (partition3 < high)
        *store++ = a[partition3++];

    // replace slice a[low.. high - 1] with sorted result
    for (unsigned int i = low; i < high; i++)
        a[i] = sorted[i - low];
}

int main()
{
    int a[] = {12,10,43,23,-78,45,123,56,98,41,90,24};
    // int a[] = {-78,10,12,23,24,41,43,45,56,90,98,123};
    // int a[] = { 4, 3, 2, 1, 0};
    // int a[] = { 3, 2, 1, 0};
    // int a[] = { 2, 1, 0};
    // int a[] = { 1, 0};
    // int a[] = { 0};
    const unsigned int num = sizeof(a) / sizeof(*a);

    mergesort(a, 0, num);

    for (unsigned int i = 0; i < num; i++)
        cout << a[i] <<" ";
    cout << endl;
}

БОНУС 2

Повторно реализованоmerge() функция: 

static void merge(int *a,
                  const unsigned int low,    const unsigned int pivot1,
                  const unsigned int pivot2, const unsigned int high)
{

    unsigned int slice = high - low;
    int sorted[slice];                // slice a[low..high - 1] to be sorted
    unsigned int store      = 0;      // running pointer into sorted[]
    unsigned int partition1 = low;    // running index a[low    .. pivot1 - 1]
    unsigned int partition2 = pivot1; // running index a[pivot1 .. pivot2 - 1]
    unsigned int partition3 = pivot2; // running index a[pivot2 .. high   - 1]

    while (store < slice) {
        int next;

        if (partition1 < pivot1) {
            // partition1 is not exhausted yet
            next = a[partition1];

            if (partition2 < pivot2) {

                // partitions 1 & 2 are not exhausted yet
                if (partition3 < high) {

                    // all partitions are not exhausted yet
                    if (next < a[partition2]) {
                        if (a[partition2] < a[partition3])
                            partition1++;           // p1 <  p2 <  p3
                        else if (next < a[partition3])
                            partition1++;           // p1 <  (p3 || p2)
                        else
                            next = a[partition3++]; // p3 <= p1 <  p2

                    } else if (a[partition2] < a[partition3])
                          next = a[partition2++];   // p2 <  p3 <= p1
                    else
                        next = a[partition3++];     // p3 <= p2 <= p1

                } else if (next < a[partition2])
                    partition1++;                   // p1 <  p2 [p3]
                else
                    next = a[partition2++];         // p2 <= p1 [p3]

            } else if (partition3 < high) {
                // partition2 is exhausted, compare p1 & p3 only
                if (next < a[partition3])
                    partition1++;                   // p1 <  p3 [p2]
                else
                    next = a[partition3++];         // p3 <= p1 [p2]

            } else
                // partitions 2 & 3 are exhausted, copy from p1
                partition1++;                       // p1 [p2, p3]

        } else if (partition2 < pivot2) {
            // partition1 is exhausted, compare p2 & p3 only
            next = a[partition2];

            if (partition3 < high) {

                // partitions 2 & 3 are not exhausted
                if (next < a[partition3])
                    partition2++;                   // p2 <  p3 [p1]
                else
                    next = a[partition3++];         // p3 <= p2 [p1]

            } else
                // partitions 1 & 3 are exhausted, copy from p2
                partition2++;                       // p2 [p1, p3]

        } else {
            // partitions 1 & 2 are exhausted, copy from p3
            next = a[partition3++];                 // p3 [p1, p2]
        }

        // store smallest entry
        sorted[store++] = next;
    }

    // replace slice a[low.. high - 1] with sorted result
    for (unsigned int i = low; i < high; i++)
        a[i] = sorted[i - low];
}
...