Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > Общие вопросы по .NET и C# > подскажите алгоритм сортировки матрицы улиткой


Автор: 4YBAK 24.4.2013, 12:29
Привет!

Нужно отсортировать по возрастанию матрицу 4*4 как на картинке.
аглоритм желательно универсальный, чтоб можно было потом его переделать под любую размерность матрицы.
Я думаю, нужно сначала сформировать массив из этой матрицы, затем сортирнуть его функцией ниже, затем заслать обратно в матрицу.
Вот как сформировать массив из этой матрицы я и не понимаю.
Подскажите плиз

Код

 static int[] SortMassiv(int[] massiv, bool up = true)
        {
            int temp;
            bool NotReady = true;
            while (NotReady)
            {
                NotReady = false;

                for (int i = 0; i < massiv.Length - 1; i++)

                    if (up ? massiv[i] > massiv[i + 1] : massiv[i] < massiv[i + 1])
                    
                    {
                        temp = massiv[i];
                        massiv[i] = massiv[i + 1];
                        massiv[i + 1] = temp;
                        NotReady = true;

                    }
            }


            return massiv;
        }

Автор: avvo 24.4.2013, 14:13
Например так

Код

        private static void Sort(int[,] ints, int l)
        {

            var m = new int[l*l];
            int i;
            int j;
            for (i = 0; i < l; i++)
                for (j = 0; j < l; j++)
                    m[l*i + j] = ints[i, j];

            Array.Sort(m);
            var ub = 0;
            var db = l-1;
            var lb = 0;
            var rb = l-1;

            i = 0;
            j = 0;
            var st = 0;
            for (var q=0;q<l*l;q++)
            {
                ints[i, j] = m[q];
                switch (st)
                {
                    case 0:
                        j++;
                        if(j==rb)
                        {
                            st = 1;
                            ub++;
                        }
                        break;
                    case 1:
                        i++;
                        if(i==db)
                        {
                            st = 2;
                            rb--;
                        }
                        break;
                    case 2:
                        j--;
                        if(j==lb)
                        {
                            st = 3;
                            db--;
                        }
                        break;
                    case 3:
                        i--;
                        if(i==ub)
                        {
                            st = 0;
                            lb++;
                        }
                        break;
                }
            }
        }

Автор: 4YBAK 24.4.2013, 16:01
Цитата(avvo @ 24.4.2013,  14:13)
Например так

Код

        private static void Sort(int[,] ints, int l)
        {

            var m = new int[l*l];
            int i;
            int j;
            for (i = 0; i < l; i++)
                for (j = 0; j < l; j++)
                    m[l*i + j] = ints[i, j];

            Array.Sort(m);
            var ub = 0;
            var db = l-1;
            var lb = 0;
            var rb = l-1;

            i = 0;
            j = 0;
            var st = 0;
            for (var q=0;q<l*l;q++)
            {
                ints[i, j] = m[q];
                switch (st)
                {
                    case 0:
                        j++;
                        if(j==rb)
                        {
                            st = 1;
                            ub++;
                        }
                        break;
                    case 1:
                        i++;
                        if(i==db)
                        {
                            st = 2;
                            rb--;
                        }
                        break;
                    case 2:
                        j--;
                        if(j==lb)
                        {
                            st = 3;
                            db--;
                        }
                        break;
                    case 3:
                        i--;
                        if(i==ub)
                        {
                            st = 0;
                            lb++;
                        }
                        break;
                }
            }
        }

не понял...
вы сначала просто загнали каждую строку матрицы одну за другой массив.
А дальше-то что?
Нужно ведь не строки целиком загонять, а загнать так, чтобы было как на картинке прикрепленной. В форме улитки...
Или я че-то не понимаю?

Автор: avvo 24.4.2013, 20:09
smile
а какая разница, в каком порядке их "загонять" если их потом сортировать?
Более того, если Array.Sort будет сортировать quicksort-ом то элементы массива перед сортировкой будут перемешаны, чтобы ускорить сортировку (но там вроде сортировка инсертом или мерджем, в зависимости от размера массива).
Поэтому неважно, в каком порядке элементы в массиве перед сортировкой.

Нужно их после сортировки сложить в квадратную матрицу змейкой. И все.

Автор: avvo 24.4.2013, 20:59
Цитата(4YBAK @ 24.4.2013,  16:01)
Цитата(avvo @ 24.4.2013,  14:13)
Например так

Код

        private static void Sort(int[,] ints, int l)
        {

            var m = new int[l*l];
            int i;
            int j;
            for (i = 0; i < l; i++)
                for (j = 0; j < l; j++)
                    m[l*i + j] = ints[i, j];

            Array.Sort(m); 
            var ub = 0;  // верхняя граница
            var db = l-1; //нижняя
            var lb = 0;  // левая
            var rb = l-1; // правая

            i = 0; // текущие координаты в квадрате, строка
            j = 0; // столбец
            var st = 0; //направление заполнения
            for (var q=0;q<l*l;q++)  //берем все элементы в отсортированном порядке
            {
                ints[i, j] = m[q]; // ставим в нужную позицию
                switch (st)
                {
                    case 0:  //идем вправо
                        j++;
                        if(j==rb) //дошли до упора
                        {
                            st = 1; // теперь вниз
                            ub++; //сдвигаем верхнюю границу
                        }
                        break;
                    case 1:  //идем вниз
                        i++;
                        if(i==db)
                        {
                            st = 2;
                            rb--;
                        }
                        break;
                    case 2: //влево
                        j--;
                        if(j==lb)
                        {
                            st = 3;
                            db--;
                        }
                        break;
                    case 3:  // вверх
                        i--;
                        if(i==ub)
                        {
                            st = 0;
                            lb++;
                        }
                        break;
                }
            }
        }

не понял...
вы сначала просто загнали каждую строку матрицы одну за другой массив.
А дальше-то что?
Нужно ведь не строки целиком загонять, а загнать так, чтобы было как на картинке прикрепленной. В форме улитки...
Или я че-то не понимаю?

с ремарками

Автор: 4YBAK 25.4.2013, 09:57
Большое спасибо!

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)