Как отсортировать двумерный массив
Перейти к содержимому

Как отсортировать двумерный массив

  • автор:

4. Сортировка двумерных массивов

Пусть a [ M ][ N ] – некоторая матрица. На множестве строк данной матрицы ( a [0], a [1],…, a [ M -1]) определим числовую функцию F . Например, функция F может возвращать значение первого элемента строки ( F ( a [ i ]) = a [ i ][0]), сумму элементов строки ( F ( a [ i ]) = a [ i ][0] + a [ i ][1] + … + a [ i ][ N -1]) и т.д. Задача состоит в том, чтобы упорядочить строки матрицы таким образом, чтобы последовательность F ( b [0]), F ( b [1]),…, F ( b [ M -1]) была неубывающей, где символом b обозначена новая матрица, полученная из матрицы a путем перестановки строк.

Для решения данной задачи имеется несколько подходов. Вопервых, можно действительно переставлять строки матрицы a , но для матриц с большим значением числа N (число столбцов) это неэффективно. Во-вторых, можно завести массив индексов int ind[M] = <0, 1,…, M-1>и переставлять в нем элементы таким образом, что-

бы последовательность F ( a [ind[0]]), F ( a [ind[1]]),…, F ( a [ind[ M -1]])

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

a [ind[ i ]][ j ], 0 ≤ i < M , 0 ≤ j < N .

Такой подход для одномерных массивов мы уже рассматривали выше. Поэтому (для разнообразия) остановимся на третьем подхо-

де (сопряженным со вторым), который заключается в рассмотрении дополнительного массива указателей int * pa [ M ], где pa [ i ] содержит адрес i -ой строки матрицы a , i = 0,…, M -1.

Изначально массив pa инициализируется следующим обра-

for(i = 0; i < M; i++) pa[i] = a[i];

Затем с помощью алгоритма быстрой сортировки происходит преобразование массива указателей pa так, чтобы последовательность F ( pa [0]), F ( pa [1]),…, F ( pa [ M -1]) удовлетворяла начальному условию. В алгоритме ниже в качестве функции F выступает функция, которая возвращает первый элемент строки. Поэтому вместо записи F ( pa [ i ]) будем использовать запись * pa [ i ].

#define M 5 /* Число строк матрицы */ #define N 10 /* Число столбцов матрицы */

/* вывод матрицы на экран через массив индексов pa */ void Print(int *pa[], int m, int n)

for (i = 0; i < m; i++)

for (j = 0; j < n; j++) printf(«%5d», pa[i][j]);

/* сортировка массива pa по первым элементам массива a: */ void QuickSort (int *pa[], int left, int right)

Сортировка двумерного массива на PHP

Сортировка двумерного массива на PHP

Не так давно передо мной встала задача сортировки двумерного массива на PHP, причём внутренний массив был ассоциативным. Я было хотел сортировать, как уже привык, методом пузырька, но потом решил поискать в Интернете более оригинальный способ и нашёл. И сейчас я с Вами поделюсь этим методом сортировки двумерного массива на PHP.

Давайте с Вами разберёмся в коде, в котором есть массив с несколькими пользователями, и нам необходимо отсортировать их по дате регистрации.

<?php
/* Двумерный массив с пользователями (например, из БД) */
$array = array();
$array[5] = array(«email» => «[email protected]», «date_reg» => 1272895531);
$array[10] = array(«email» => «[email protected]», «date_reg» => 1274429353);
$array[3] = array(«email» => «[email protected]», «date_reg» => 1274277050);
usort($array, «compare»); // Вызываем пользовательскую сортировку
/* Функция для нашей сортировки */
function compare ($v1, $v2) <
/* Сравниваем значение по ключу date_reg */
if ($v1[«date_reg»] == $v2[«date_reg»]) return 0;
return ($v1[«date_reg»] < $v2[«date_reg»])? -1: 1;
>
print_r($array); // Выводим отсортированный массив
?>

В основе лежит usort() — функция пользовательской сортировки. А сама сортировка происходит по правилам, описанным в функции compare().

Вот таким простым способом можно отсортировать двумерный массив на PHP.

Копирование материалов разрешается только с указанием автора (Михаил Русаков) и индексируемой прямой ссылкой на сайт (http://myrusakov.ru)!

Добавляйтесь ко мне в друзья ВКонтакте: http://vk.com/myrusakov.
Если Вы хотите дать оценку мне и моей работе, то напишите её в моей группе: http://vk.com/rusakovmy.

Если Вы не хотите пропустить новые материалы на сайте,
то Вы можете подписаться на обновления: Подписаться на обновления

Если у Вас остались какие-либо вопросы, либо у Вас есть желание высказаться по поводу этой статьи, то Вы можете оставить свой комментарий внизу страницы.

Порекомендуйте эту статью друзьям:

Если Вам понравился сайт, то разместите ссылку на него (у себя на сайте, на форуме, в контакте):

Сортировка двумерного массива по возрастанию

Помогите, пожалуйста с задачей.
Необходимо отсортировать двумерный массив по возрастанию (не переводя его в одномерный).

Должно получиться примерно так:
0 0 1 1
2 3 4 5
7 8 9 9

С помощью одномерного массива — у меня получилось. А как без него не представляю даже:'(

Сортировка строк двумерного массива по возрастанию значений первого столбца
Люди добрые помогите, пожалуйста! Суть задачи такова: 1. Создать двумерный массив 2.

Сортировка массива: сначала положительные по возрастанию, потом отрицательные по возрастанию
Пользователь вводит массив чисел,нужно отсортировать его методом выбора,что бы сначала шли.

Ошибка при сортировке двумерного массива по возрастанию
По убыванию сортировка работает полноценно,а по возрастанию первое число НЕ понимаю откуда.

Упорядочить строки двумерного массива по возрастанию их наибольших элементов.
Нужно упорядочить его строки по возрастанию их наибольших элементов. #include &quot;stdafx.h&quot;.

Но я понимаю, как пробежать по двумерному массиву в нужном порядке. У меня проблема в том что я не могу придумать как связать это с этим алгоритмом сортировки для одномерного массива:

Если двумерный перевести в одномерный, отсортировать по этому алгоритму и потом перевести назад в двумерный — нет проблем. А как без перевода?

P.S. Извините за код. Не разобралась пока, как делать вложения

Сообщение от Lyric

Но я понимаю, как пробежать по двумерному массиву в нужном порядке. У меня проблема в том что я не могу придумать как связать это с этим алгоритмом сортировки для одномерного массива

XuTPbIu_MuHTAu, я понимаю, для Вас это легко. А я начала учить программирование два месяца назад — сейчас рассматриваю задачки месячной давности и смеюсь над тем, как я над ними корпела.

Но все равно — спасибо за пинок!
Ушла думать

Сообщение от Lyric

Ой, это я кажется, неправильно объяснила условие

Сообщение от Бартимеус

Если сделать как ты говоришь, массив отсортируется по строкам — каждая строка отдельно (или по столбцам). Это действительно просто.

А мне нужно отсортировать весь массив. Например:

3 2 9 0
7 1 0 8
5 9 4 1 массив

0 2 3 9
0 1 7 8
1 4 5 9 сортировка по строкам

0 0 1 1
2 3 4 5
7 8 9 9 сортировка всего массива

Лучший ответСообщение было отмечено как решение

Решение

Сообщение от Olgert
Сообщение от KoMaTo3Huk

Это много циклов + вырвиглазное оформление.

Добавлено через 8 минут
//сортировка пузырьком по аналогии с сортировкой одномерного массива
//перебираем элементы по очереди, начиная с a[0][1]
//в двойном вложенном цикле, словно выводим 2д массив
//и сравниваем в цикле элемент с предыдущим, а не со следующим
i=inext, j=jnext; //а в роли индекса предыдущего элемента выступает значение,
//запомненное в конце предыдущей итерации цикла! в этом вся моя фишка.
//Благодаря этому не нужно лишних условий на границах массива
//и мучительных попыток выбора то ли a[i+1][j] то ли a[0][j+1] на роль следующего элемента

How do I sort a two-dimensional (rectangular) array in C#?

I have a two-dimensional array (of Strings) which make up my data table (of rows and columns). I want to sort this array by any column. I tried to find an algorithm for doing this in C#, but have not been successful.

Any help is appreciated.

Adam's user avatar

Jack's user avatar

15 Answers 15

Can I check — do you mean a rectangular array ( [,] )or a jagged array ( [][] )?

It is quite easy to sort a jagged array; I have a discussion on that here. Obviously in this case the Comparison<T> would involve a column instead of sorting by ordinal — but very similar.

Sorting a rectangular array is trickier. I’d probably be tempted to copy the data out into either a rectangular array or a List<T[]> , and sort there, then copy back.

Here’s an example using a jagged array:

For working with a rectangular array. well, here is some code to swap between the two on the fly.

Marc Gravell's user avatar

Load your two-dimensional string array into an actual DataTable (System.Data.DataTable), and then use the DataTable object’s Select() method to generate a sorted array of DataRow objects (or use a DataView for a similar effect).

You could also write your own method to sort a two-dimensional array. Both approaches would be useful learning experiences, but the DataTable approach would get you started on learning a better way of handling tables of data in a C# application.

Boris Sokolov's user avatar

Here is an archived article from Jim Mischel at InformIt that handles sorting for both rectangular and jagged multi-dimensional arrays.

takrl's user avatar

This code should do what you are after, I haven’t generalised it for n by n, but that is straight forward. That said — I agree with MusiGenesis, using another object that is a little better suited to this (especially if you intend to do any sort of binding)

(I found the code here)

No_Nick777's user avatar

So your array is structured like this (I’m gonna talk in pseudocode because my C#-fu is weak, but I hope you get the gist of what I’m saying)

So value[1][3] is the value at row 1, column 3.

You want to sort by column, so the problem is that your array is off by 90 degrees.

As a first cut, could you just rotate it?

If you know you only want to sort one column at a time, you could optimize this a lot by just extracting the data you want to sort:

In C++ you could play tricks with how to calculate offsets into the array (since you could treat your two-dimensional array as a one-d array) but I’m not sure how to do that in c#.

Try this out. The basic strategy is to sort the particular column independently and remember the original row of the entry. The rest of the code will cycle through the sorted column data and swap out the rows in the array. The tricky part is remembing to update the original column as the swap portion will effectively alter the original column.

If you could get the data as a generic tuple when you read it in or retrieved it, it would be a lot easier; then you would just have to write a Sort function that compares the desired column of the tuple, and you have a single dimension array of tuples.

This is an old question, but here’s a class I just built based on the article from Jim Mischel at InformIt linked by Doug L.

Given an unsorted 2D array data of arbitrary size that you want to sort on column 5 you just do this:

Note the virtual Compare method and protected SortArray so you can create specialized subclasses that always sort on a particular column or do specialized sorting on multiple columns or whatever you want to do. That’s also why CompareStrings is broken out and protected — any subclasses can use it for simple comparisons instead of typing out the full SortArray[x, col].CompareTo(SortArray[y, col]) syntax.

I like the DataTable approach proposed by MusiGenesis above. The nice thing about it is that you can sort by any valid SQL ‘order by’ string that uses column names, e.g. «x, y desc, z» for ‘order by x, y desc, z’. (FWIW, I could not get it to work using column ordinals, e.g. «3,2,1 » for ‘order by 3,2,1’) I used only integers, but clearly you could add mixed type data into the DataTable and sort it any which way.

In the example below, I first loaded some unsorted integer data into a tblToBeSorted in Sandbox (not shown). With the table and its data already existing, I load it (unsorted) into a 2D integer array, then to a DataTable. The array of DataRows is the sorted version of DataTable. The example is a little odd in that I load my array from the DB and could have sorted it then, but I just wanted to get an unsorted array into C# to use with the DataTable object.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *