2015-10-22
580
Чтобы поменять местами значения двух ячеек в памяти,
надо использовать временную переменную1. Пусть даны ячейки a и b, содержащие некоторые значения. После выполнения следующих команд их значения поменяются:
Эта цепочка операторов присваивания особая:
• она начинается и заканчивается временной переменной c;
• следующий оператор начинается с той переменной, на которую закончился предыдущий
Сортировка массивов
Сортировка – это расстановка элементов некоторого списка в заданном порядке.
Существуют разные виды сортировки (по алфавиту, по датам и т.д.), они отличаются лишь
процедурой сравнения элементов. Мы рассмотрим простейший вариант сортировки – расстановку элементов массива в порядке возрастания.Программисты придумали множество методов сортировки. Они делятся на две группы:
• понятные, но не эффективные
• эффективные, но непонятные (быстрая сортировка и т.п.).
Пока мы будем изучать только методы из первой группы, которых хватает для простых задач (когда размер массива не более 1000).
Метод пузырька
Название этого метода произошло от известного физического явления – пузырек воздуха
в воде поднимается вверх. В этом методе сначала поднимается «наверх» (к началу массива) самый «легкий» элемент (минимальный), затем следующий и т.д.
Сначала сравниваем последний элемент с предпоследним. Если они стоят неправильно, то
меняем их местами. Далее так же рассматриваем следующую пару элементов и т.д. Когда мы обработали пару (A[0], A[1]), минимальный элемент стоит на месте A[0]. Это значит, что на следующих этапах его можно не рассматривать
При следующем проходе наша задача – поставить на место элемент A[1]. Делаем это так же,но уже не рассматриваем A[0], который стоит на своем месте. Сделав N-1 проходов, мы установим на место элементы с A[0] по A[N-2]. Это значит, что последний элемент, A[N-1], уже тоже стоит на своем месте (другого у него нет).
Метод пузырька работает медленно, особенно на больших массивах. Можно показать, что при увеличении размера массива в 10 раз время выполнения программы увеличивается в 100 раз (метод имеет порядок N2). К сожалению, все простые алгоритмы сортировки имеют такой (квадратичный) порядок.
