Сортировки массивов

Особенности обработки двумерных массивов

Вывод значений элементов массивов на экран

Для вывода значений массивов на экран используется цикл: для одномерного массива – один цикл, для двумерного массива – два цикла и так далее.

Примеры для одномерного массива	Примеры для двумерного массива
int array[5], i; … printf(“Array: ”); for(i=0; i<5; i++) printf(“%d ”, array[i]); printf(“ ”);	float m[2][2]; int i, j; … printf(“Massiv: ”); for(i=0; i<2; i++) { for(j=0; j<2; j++) printf(“%.2f ”, mas[i][j]); printf(“ ”); }

При работе с двумерными массивами следует учитывать, что в памяти компьютера такой массив представляется как одномерный. Поэтому следует помнить, что представление массива как двумерного – это внешнее представление и правильное оперирование индексацией.

При работе с матрицами часто рассматриваются вопросы, связанные с элементами, лежащими на диагоналях. Такие матрицы называются квадратными и количество строк и столбцов в них одинаково. Например: матрица array[5][5] – квадратная, т.к. у не ее количество строк равно количеству столбцов и равно 5.

Для главной диагонали возможны два способа заполнения:

Пример – способ 1	Пример – способ 2
for(i=0; i<n; i++) for(j=0; j<n; j++) if(i == j) array[i][j] = 1;	for(i=0; i<n; i++) array[i][i] = 1;

Для побочной диагонали возможны два способа заполнения:

Пример – способ 1	Пример – способ 2
for(i=0; i<n; i++) for(j=0; j<n; j++) if(i+j == n-1) array[i][j] = -1;	for(i=0; i<n; i++) array[i][n-1-i] = -1;

Сортировка - это процесс перегруппировки однотипных элементов структуры данных в некотором определенном порядке. Цель сортировки - облегчить последующие поиск, обновление, исключение, включение элементов в структуру данных. Сортировка является важным средством для ускорения работы практически любого алгоритма, в котором требуется частое обращение к определенным элементам структуры данных.

Эффективность алгоритма сортировки может зависеть от ряда факторов, таких, как: количество сортируемых элементов; диапазон значений элементов; степень первоначальной отсортированности элементов; сложность алгоритма; время сортировки; количество произведенных сравнений; место размещения элементов в памяти и т. д.

В зависимости от последнего фактора все методы сортировки разбивают на два класса:

1. внутренняя сортировка (сортировка массивов);

2. внешняя сортировка (сортировка файлов или сортировка последовательностей).

Здесь обязательно требуется дать следующее определение: метод сортировки называется устойчивым, если в процессе сортировки относительное расположение элементов с одинаковыми (равными) значениями не изменяется. Устойчивость метода сортировки желательна, если речь идет об элементах, уже отсортированных по некоторым другим свойствам, не влияющим на ключ, по которому осуществляется сортировка.

Основными требованиями к алгоритмам сортировки, как и ко всяким алгоритмам, являются требования по памяти и по времени выполнения. Это предполагает, что сортировка элементов массива выполняется на месте, без передачи их в результирующий массив.

Самыми простыми методами сортировки являются прямые методы сортировки, они требуют порядка O(n₂)сравнений значений. Прямые методы можно разбить на три категории:

1. сортировка методом прямого включения;

2. сортировка методом прямого выбора;

3. сортировка методом прямого обмена.

Дата добавления: 2014-01-20