АльфаОмега

база знаний!

Приветствую Вас, Гость | RSS
Форма входа
Логин:
Пароль:
...


1с бухгалтерия [12]Английский язык [6]
Банковское дело [22]Безопасность жизнедеятельности [12]
Биология [7]Бухгалтерское дело [166]
Бухгалтерский учет [129]Информатика [91]
Инновационный менеджмент [12]История экономики [80]
История экономических учений [162]Концепции современного естествознания [54]
Конфликтология [18]Культурология [45]
Линейная алгебра [72]Линейное программирование [7]
Макроэкономика [43]Маркетинг и реклама [68]
Математическая статистика [21]Математический анализ [50]
Менеджмент [141]Микроэкономика [39]
Мировая экономика [85]Моделирование портфеля ценных бумаг [19]
Основы предпринимательства [44]Отечественная история [39]
Политология [27]Правоведение [74]
Прикладные программы [21]Психология и педагогика [159]
Региональная экономика [81]Социология [58]
Теория вероятностей [53]Теория оптимального управления [3]
Управление организацией [35]Физическая культура [42]
Философия [157]Финансовый анализ [99]
Финансы и кредит [236]Численные методы [8]
Эконометрика [15]Экономика предприятия [70]
Экономико математическое моделирование [48]Экономическая география [69]
Экономическая теория [99]Экономическая политика [23]
Юриспруденция [20]Другие предметы [39]

Основы программирования: Простейшие алгоритмы сортировки

http://belgorod-vorota.ru ворота сдвижные гаражные. Раздвижные гаражные ворота.

(19.6 Kb), 05.03.2012, 15:07
Простейшие алгоритмы сортировки, закрепление навыков работы с массивами, освоение простейших алгоритмов сортировки

Теоретические сведения
Сортировка выбором
Алгоритм упорядочивания по возрастанию:
1. Найти минимальное значение в текущем списке.
2. Найденное минимальное значение меняется местом с элементом на первой позиции.
3. Повторяем сортировку, исключив из рассмотрения уже отсортированный первый элемент, то есть, начиная со второй позиции.
Последовательность шагов при n=7 показана на рисунке.

Алгоритм не использует дополнительной памяти: все операции происходят "на месте".

Метод простого обмена (метод пузырька).
Алгоритм состоит в повторяющихся проходах по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по массиву повторяются до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает — массив отсортирован. При проходе алгоритма, элемент, стоящий не на своём месте, «всплывает» до нужной позиции как пузырёк в воде, отсюда и название алгоритма.
Алгоритм сортировки методом пузырька
1. Сравниваем первый и второй элементы массива. Если первый элемент больше, чем второй, то меняем их местами.
2. Сравниваем второй и третий элементы массива. Если второй элемент больше, чем третий, то меняем их местами.
3. ...
4. Сравниваем предпоследний (N-1) и последний (N) элементы массива. Если предпоследний элемент больше, чем последний, то меняем их местами.

В результате самым последним элементом в массиве у нас окажется самый большой элемент.
Второй шаг сортировки методом пузырька - повторяем вышеуказанные действия для части массива, начиная с 1 позиции до N-1:
1. Сравниваем первый и второй элементы массива. Если первый элемент больше, чем второй, то меняем их местами.
2. Сравниваем второй и третий элементы массива. Если второй элемент больше, чем третий, то меняем их местами.
3. ...
4. Сравниваем элемент N-2 и элемент N-1 массива. Если (N-2)-й элемент больше, чем элемент N-1, то меняем их местами.
В результате предпоследний элемент в массиве у нас тоже будет на своем, "отсортированном" месте.
На последующих шагах сортировки методом пузырька вышеуказанные действия повторяются для части массива, начиная с 1 позиции до N-2 (шаг 3), а потом для диапазона 1..N-3 и так далее до диапазона 1..2.
После завершения последнего шага массив будет отсортирован по возрастанию.

Среднее число сравнений и обменов имеют квадратичный порядок роста, отсюда можно заключить, что алгоритм пузырька достаточно медленен, однако он прост и его можно улучшить простыми средствами.
Во-первых, рассмотрим ситуацию, когда на каком-либо из проходов не произошло ни одного обмена. Это значит, что все пары расположены в правильном порядке, так что массив уже отсортирован. Одно из возможных улучшений алгоритма заключается в запоминании, производился ли на данном проходе какой-либо обмен. Если нет - алгоритм заканчивает работу.
Процесс улучшения можно продолжить, если запоминать не только сам факт обмена, но и индекс последнего обмена k. Действительно: все пары соседних элементов с индексами, большими k, уже расположены в нужном порядке. Дальнейшие проходы можно заканчивать на индексе k, вместо того чтобы двигаться до установленной заранее верхней границы i.



Похожие материалы
Язык программирования
Уровни языков программирования
Поколения языков программирования
Объектно-ориентированное программирование (ООП)
Теоретические основы информатики. Информатика как наука

Категория: Информатика | Добавил: RuStudent
Просмотров:1514 | Загрузок: 200 | Рейтинг: 5.0/1
  
Всего комментариев: 0
 
Добавлять комментарии могут только зарегистрированные пользователи.
[ Регистрация | Вход ]
Меню сайта

ПОДЕЛИТЬСЯ
...