Сортировка массива по диагонали

Question

Я искал некоторые веб-сайты, но я не мог найти ответ на свою проблему.

Вот мой код:

#include "stdafx.h" 
#include <iostream> 
#include <math.h> 
#include <time.h> 
#include<iomanip> 
#include<array> 
#include <algorithm> 

using namespace std; 
const int AS = 6; 
int filling(void); 
void printing(int[AS][AS]); 
int forsorting(int[][AS], int); 


int main() 

{ 
    int funny = 0; 
    int timpa = 0; 
    int counter = 0; 
    int Array[AS][AS]; 
    srand(time(0)); 

    for (int i = 0; i<AS; i++) 
    { 
     for (int j = 0; j<AS; j++) 
      Array[i][j] = filling(); 
    } 

    cout << "The unsorted array is" << endl << endl; 

    printing(Array); 


    cout << "The sorted array is" << endl << endl; 



    for (int il = 0; il<AS; il++) 
    { 
     for (int elle = 0; elle<AS; elle++) 
      Array[il][elle] =forsorting(Array, funny); 

     printing(Array); 

    } 

    system("PAUSE"); 


    return 0; 

} 

int filling(void) 
{ 
    int kira; 
    kira = rand() % 87 + 12; 
    return kira; 
} 


void printing(int Array[AS][AS]) 
{ 
    int counter = 0; 
    for (int i = 0; i<AS; i++) 
    { 
     for (int j = 0; j<AS; j++) 
     { 
      cout << setw(5) << Array[i][j]; 
      counter++; 
      if (counter%AS == 0) 
       cout << endl << endl; 
     } 
    } 
} 

int forsorting(int Array[AS][AS], int funny) 
{ 
    int c, tmp, x; 
    int dice = 0; 
    int Brray[AS*AS]; 
    int timpa = 0; 
    int super = 0; 


    //Transofrming Array[][] into Brray[] 
    for (int i = 0; i < AS; i++) 
    { 
     for (int k = 0; k < AS; k++) 
     { 
      Brray[timpa] = Array[i][k]; 
      timpa++; 
     } 
    } 


    //Bubble sorting in Brray[] 

    for (int passer = 1; passer <= AS-1; passer++) 
    { 
     for (int timon = 1; timon <= AS-1; timon++) 
     { 
      if (Brray[timpa]>Brray[timpa + 1]) 
      { 
       super = Brray[timpa]; 
       Brray[timpa] = Brray[timpa + 1]; 
       Brray[timpa + 1] = super; 
      } 
     } 
    } 

    //Transforming Brray[] into Array[][] 

    for (int e = 0; e<AS; e++) 
    { 
     for (int d = 0; d<AS; d++) 
     { 
      Brray[dice] = Array[e][d]; 

      dice++; 
     } 
    } 

    ***There's a part missing here*** 


} 

Что я должен сделать, написать программу, используя 3 функции.

• 1-функция не будет заполнить мой 2D массив случайным образом (без проблем с этой частью)
• 2-ая функция будет печатать несортированный массив на экране (без проблем с этой частью)
• и 3-й функции буду сортировать мой массив по диагонали, как показано на рисунке:

Затем нужно вызвать 2-ую функцию для печати отсортированного массива. Моя проблема связана с 3-й функцией, когда я превратил свой 2D-массив в 1D-массив и отсортировал его с помощью сортировки Bubble, но то, что я не могу сделать, это вернуть его в двумерную диагональ 2D-массива.

Answer 1

Предположим, у вас есть 0-основанный 1-мерный массив A из n = m^2 элементов.Я расскажу вам, как получить индекс в A, заданный и пару индексов в 2D-массив, в соответствии с вашим методом диагонализации. Я назову i индекс (0) в A и x и y индексы (на основе 0) в 2D-массиве.

---

Во-первых, давайте предположим, что мы знаем x и y. Все записи в диагонали, содержащие (x,y), имеют одинаковую сумму их координат. Пусть sum = x + y. Перед тем, как попасть в диагональ, содержащую эту запись, вы повторили предыдущие диагонали sum (проверьте, что это правильно, из-за индексации с нулевой отметкой). Диагональ с суммой k имеет в общей сложности k + 1 записей. Итак, прежде чем перейти к этой диагонали, вы выполнили следующие записи: 1 + 2 + ... + (sum - 1). Существует формула для суммы вида 1 + 2 + ... + N, а именно N * (N + 1)/2. Итак, прежде чем перейти к этой диагонали, вы выполнили следующие записи: (sum - 1) * sum/2.

Теперь, прежде чем перейти к записи на (x,y), вы прошли через несколько записей в этой самой диагонали, не так ли? Сколько? Да, это точно y! Вы начинаете с верхней записи и спускаетесь по одному за раз. Таким образом, запись в (x,y) является ((sum - 1) * sum/2 + y + 1)-й записью, но массив также основан на нуле, поэтому нам нужно вычесть его. Таким образом, мы получаем следующую формулу:

• i = (sum - 1) * sum/2 + y = (x + y - 1) * (x + y)/2 + y

---

Для перехода в обратном направлении, мы хотим начать с i, и выяснить (x,y) пару в 2D массив, в котором элемент A[i] идет. Поскольку мы решаем для двух переменных (x и y), начиная с одного (только i) и ограничения, сложнее записать замкнутую формулу. На самом деле я не уверен, что закрытая форма возможна и, конечно, не без каких-либо floor и т. Д. Я начал пытаться найти ее и сдался! Удачи!

Возможно, правильно и просто создать пары (x,y) итерационно по мере того, как вы увеличиваете i, имея в виду, что суммы пар координат постоянны в пределах одной из ваших диагоналей.

Answer 2

Если вы можете преобразовать из 2D-массива в 1D-массив, то преобразование обратно - это обратный процесс. Возьмите тот же цикл и измените назначение.

Однако в вашем случае само преобразование неверно. Он должен принимать индексы в порядке (0; 0), (0; 1), (1; 0). Но то, что он делает, - это взять индексы в порядке (0; 0), (0; 1), (1; 1).

Мое предложение состоит в использовании того факта, что сумма координат X и Y на каждой диагонали одна и та же, и она идет от 0 до AS * 2-2.

Затем с помощью другого цикла вы можете проверить все возможные допустимые комбинации x/y. Что-то вроде этого:

for (int sum = 0; sum < AS*2-1; sum++) 
{ 
    for (int y = sum >= AS ? sum-AS+1 : 0; y < AS; y++) 
    { 
     x = sum - y; 
     // Here assign either from Array to Brray or from Brray to Array 
    } 
} 

P.S. Если вы хотите быть действительно умным, я уверен, что вы можете создать математическую (неитеративную) функцию, которая преобразуется из индекса в Brray в пара индексов в массиве и наоборот. Затем вы можете применить сортировку пузырьков на месте. Но это немного сложнее, чем я сейчас хочу разобраться. Тем не менее, вы можете получить дополнительный кредит.

P.P.S. Реализация следующего утра: вы можете использовать этот подход для реализации сортировки пузырьков непосредственно в 2D-массиве. Нет необходимости в копировании. Подумайте об этом так: если вы знаете пару координат (x; y), вы можете легко вычислить следующую (x; y) координату в списке. Таким образом, вы можете перемещаться вперед по массиву из любой точки. В любом случае, это все зависит от типа пузырьков.

Answer 3

Храните «диагонально отсортированные» номера в массиве и используйте это, чтобы отобразить отсортированный массив. Для простоты предположим, индексирование 0 на основе:

char order[] = { 0, 1, 3, 6, 10, 2, 4, 7, 11, 15, .. (etc) 

Затем цикл по этому массиву и дисплей как

printf ("%d", Array[order[x]]); 

Обратите внимание, что это будет проще, если ваш отсортирован Array еще одномерное на этом шаге. Вы добавляете второе измерение только при печати.

Answer 4

вам может помочь:

#include <algorithm> 
#include <iomanip> 
#include <iostream> 
#include <vector> 

template<typename T> 
class DiagArray 
{ 
public: 
    DiagArray(int size) : width(size), data(size * size), orders(size * size) 
    { 
     buildTableOrder(size); 
    } 

    const T& operator() (int x, int y) const { return data[orders[width * y + x]]; } 
    T& operator() (int x, int y) { return data[orders[width * y + x]]; } 

    void sort() { std::sort(data.begin(), data.end()); } 

    void display() const { 
     int counter = 0; 

     for (auto index : orders) { 
      std::cout << std::setw(5) << data[index]; 
      counter++; 
      if (counter % width == 0) { 
       std::cout << std::endl; 
      } 
     } 
    } 

private: 
    void buildTableOrder(int size) 
    { 
     int diag = 0; 
     int x = 0; 
     int y = 0; 
     for (int i = 0; i != size * size; ++i) { 
      orders[y * size + x] = i; 
      ++y; 
      --x; 
      if (x < 0 || y >= size) { 
       ++diag; 
       x = std::min(diag, size - 1); 
       y = diag - x; 
      } 
     } 
    } 

private: 
    int width; 
    std::vector<T> data; 
    std::vector<int> orders; 
}; 

int main(int argc, char *argv[]) 
{ 
    const int size = 5; 
    DiagArray<int> da(size); 

    for (int y = 0; y != size; ++y) { 
     for (int x = 0; x != size; ++x) { 
      da(x, y) = size * y + x; 
     } 
    } 
    da.display(); 
    std::cout << std::endl; 
    da.sort(); 
    da.display(); 
    return 0; 
} 

Answer 5

Благодарим Вас за помощь всем, что вы сказали, было очень полезно для меня. Я на самом деле смог четко подумать и придумал способ начать заполнение массива на основе вашей рекомендации, но сейчас одна проблема, я почти уверен, что моя логика на 99% правильная, но где-то есть недостаток. После запуска моего кода 2-й массив не печатается на экране. Любая помощь в этом? снова

#include "stdafx.h" 
#include <iostream> 
#include <math.h> 
#include <time.h> 
#include<iomanip> 
#include<array> 
#include <algorithm> 

using namespace std; 
const int AS = 5; 
int filling(void); 
void printing(int[AS][AS]); 
int forsorting(int[][AS], int); 


int main() 

{ 
    int funny = 0; 
    int timpa = 0; 
    int counter = 0; 
    int Array[AS][AS]; 
    srand(time(0)); 

    for (int i = 0; i<AS; i++) 
    { 
     for (int j = 0; j<AS; j++) 
      Array[i][j] = filling(); 
    } 

    cout << "The unsorted array is" << endl << endl; 

    printing(Array); 


    cout << "The sorted array is" << endl << endl; 



    for (int il = 0; il<AS; il++) 
    { 
     for (int elle = 0; elle<AS; elle++) 
      Array[il][elle] =forsorting(Array, funny); 



    } 
    printing(Array); 
    system("PAUSE"); 


    return 0; 

} 

int filling(void) 
{ 
    int kira; 
    kira = rand() % 87 + 12; 
    return kira; 
} 


void printing(int Array[AS][AS]) 
{ 
    int counter = 0; 
    for (int i = 0; i<AS; i++) 
    { 
     for (int j = 0; j<AS; j++) 
     { 
      cout << setw(5) << Array[i][j]; 
      counter++; 
      if (counter%AS == 0) 
       cout << endl << endl; 
     } 
    } 
} 

int forsorting(int Array[AS][AS], int funny) 
{int n; 
    int real; 
    int dice = 0; 
    int Brray[AS*AS]; 
    int timpa = 0; 
    int super = 0; 
    int median; 
    int row=0; 
    int col=AS-1; 


    //Transofrming Array[][] into Brray[] 
    for (int i = 0; i < AS; i++) 
    { 
     for (int k = 0; k < AS; k++) 
     { 
      Brray[timpa] = Array[i][k]; 
      timpa++; 
     } 
    } 


    //Bubble sorting in Brray[] 

    for (int passer = 1; passer <= AS-1; passer++) 
    { 
     for (int timon = 1; timon <= AS-1; timon++) 
     { 
      if (Brray[timpa]>Brray[timpa + 1]) 
      { 
       super = Brray[timpa]; 
       Brray[timpa] = Brray[timpa + 1]; 
       Brray[timpa + 1] = super; 
      } 
     } 
    } 

    //Transforming Brray[] into sorted Array[][] 


    for(int e=4;e>=0;e--)//e is the index of the diagonal we're working in 
    { 


     if(AS%2==0) 
      {median=0.5*(Brray[AS*AS/2]+Brray[AS*AS/2-1]); 
     //We start filling at median - Brray[AS*AS/2-1] 

     while(row<5 && col>=0) 

      {real=median-Brray[AS*AS/2-1]; 
     Array[row][col]=Brray[real]; 
     real++; 
     col--; 
     row++;} 
     } 

     else { 
      median=Brray[AS*AS/2]; 
      //We start filling at Brray[AS*AS/2-AS/2] 

      while(row<5 && col>=0) 
      {real=Brray[AS*AS/2-AS/2]; 
      n=Array[row][col]=Brray[real]; 
     real++; 
     col--; 
     row++;} 

     } 

    } 



    return n; 
} 

Спасибо за вашу помощь