Сортировка массивов. Тема Сортировка массивов К. Ю. Поляков, 20072009
 Скачать 124.52 Kb.
|
Программирование на языке Си Часть IIТема 4. Сортировка массивов© К.Ю. Поляков, 2007-2009 Сортировка Сортировка – это расстановка элементов массива в заданном порядке (по возрастанию, убыванию, последней цифре, сумме делителей, …). Задача: переставить элементы массива в порядке возрастания. Алгоритмы:
сложность O(N2) сложность O(N·logN) время N O(N2) O(N·logN) Метод пузырька Идея – пузырек воздуха в стакане воды поднимается со дна вверх. Для массивов – самый маленький («легкий») элемент перемещается вверх («всплывает»).
1-ый проход 2-ой проход 3-ий проход
Для сортировки массива из N элементов нужен N-1 проход (достаточно поставить на свои места N-1 элементов). Программа (1-ый проход)
сравниваются пары A[N-2] и A[N-1], A[N-3] и A[N-2] … A[0] и A[1] A[j] и A[j+1] for( j = N-2; j >= 0 ; j-- ) if ( A[j] > A[j+1] ) { c = A[j]; A[j] = A[j+1]; A[j+1] = c; } 0 Программа (следующие проходы) 2-ой проход A[0] уже на своем месте! ! for ( j = N-2; j >= 1 ; j-- ) if ( A[j] > A[j+1] ) { c = A[j]; A[j] = A[j+1]; A[j+1] = c; } 1 (i+1)-ый проход for ( j = N-2; j >= i ; j-- ) ... i
Программа main() { const int N = 10; int A[N], i, j, c; // заполнить массив // вывести исходный массив for (i = 0; i < N-1; i ++){ for (j = N-2; j >= i ; j --) if ( A[j] > A[j+1] ) { с = A[j]; A[j] = A[j+1]; A[j+1] = с; } } // вывести полученный массив } Почему цикл для i < N-1, а не i < N? ? элементы выше A[i] уже поставлены i меняем A[j] и A[j+1] Метод пузырька с флажком Идея – если при выполнении метода пузырька не было обменов, массив уже отсортирован и остальные проходы не нужны. Реализация: переменная-флаг, показывающая, был ли обмен; если она равна 0, то выход. do { flag = 0; // сбросить флаг for (j = N-2; j >= 0; j --) if ( A[j] > A[j+1] ) { с = A[j]; A[j] = A[j+1]; A[j+1] = с; flag = 1; // поднять флаг } } while ( flag ); // выход при flag = 0 flag = 0; flag = 1; ( flag ); int flag;
Как улучшить? ? Метод пузырька с флажком i = 0; do { flag = 0; // сбросить флаг for ( j = N-2; j >= i ; j -- ) if ( A[j] > A[j+1] ) { с = A[j]; A[j] = A[j+1]; A[j+1] = с; flag = 1; // поднять флаг } i ++; } while ( flag ); // выход при flag = 0 i = 0; i i ++; Метод выбора Идея:
Метод выбора N for( i = 0; i < N-1 ; i ++ ) { nMin = i ; for ( j = i+1; j < N; j ++) if( A[j] < A[nMin] ) nMin = j; if( nMin != i ) { c = A[i]; A[i] = A[nMin]; A[nMin] = c; } } N-1 нужно N-1 проходов поиск минимального от A[i] до A[N-1] если нужно, переставляем Можно ли убрать if? ? i+1 i Задания «4»: Заполнить массив из 10 элементов случайными числами в интервале [0..100] и отсортировать его по последней цифре. Пример: Исходный массив: 14 25 13 30 76 58 32 11 41 97 Результат: 30 11 41 32 13 14 25 76 97 58 «5»: Заполнить массив из 10 элементов случайными числами в интервале [0..100] и отсортировать первую половину по возрастанию, а вторую – по убыванию. Пример: Исходный массив: 14 25 13 30 76 58 32 11 41 97 Результат: 13 14 25 30 76 97 58 41 32 11 Формирование массива по условию Задача – найти в массиве элементы, удовлетворяющие некоторому условию (например, отрицательные), и скопировать их в другой массив. Примитивное решение: const int N = 5; int A[N], B[N]; // здесь заполнить массив A for( i = 0; i < N; i ++ ) if( A[i] < 0 ) B[i] = A[i];
A B
Формирование массива по условию Решение: ввести счетчик найденных элементов count, очередной элемент ставится на место B[count]. int A[N], B[N], count = 0; // здесь заполнить массив A for( i = 0; i < N; i ++ ) if( A[i] < 0 ) { B[count] = A[i]; count ++; } // вывод массива B for( i = 0; i < count; i ++ ) printf("%d\n", B[i]);
A B
count
Задания «4»: Заполнить массив случайными числами и отобрать в другой массив все числа, у которых вторая с конца цифра (число десятков) – ноль. Пример: Исходный массив: 40 105 203 1 14 Результат: 105 203 1 «5»: Заполнить массив случайными числами и выделить в другой массив все числа, которые встречаются более одного раза. Пример: Исходный массив: 4 1 2 1 11 2 34 Результат: 1 2 |