Полезное:
Как сделать разговор полезным и приятным
Как сделать объемную звезду своими руками
Как сделать то, что делать не хочется?
Как сделать погремушку
Как сделать так чтобы женщины сами знакомились с вами
Как сделать идею коммерческой
Как сделать хорошую растяжку ног?
Как сделать наш разум здоровым?
Как сделать, чтобы люди обманывали меньше
Вопрос 4. Как сделать так, чтобы вас уважали и ценили?
Как сделать лучше себе и другим людям
Как сделать свидание интересным?
Категории:
АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника
|
Алгоритм простого выбораЭтот алгоритм является непосредственной реализацией идеи сортировки выбором: из ещё не отсортированных записей выбирается минимальная (максимальная) и добавляется последней (первой) к уже отсортированным записям. На рис. 1 схематично представлен i -й шаг алгоритма. К этому шагу первые i записей исходного массива уже отсортированы по возрастанию и на рисунке помечены серым цветом. Среди оставшихся (n – i) записей k (j), j = i, …, n, необходимо выбрать минимальный элемент и сохранить его индекс во вспомогательной переменной temp. С этой целью переменной temp присваивается значение i. Затем последовательно сравниваются k (j), j = i + 1, …, n – 1, со значением k (temp). В случае если k (j) < k (temp), переменной temp присваивается значение j. Шаг алгоритма завершается перестановкой местами элементов k (i) и k (temp). Пример работы алгоритма сортировки простым выбором последовательности 6, 1, 8, 2, 5, 3, хранящейся в массиве, представлен на рис. 2. Реализация на языке С++ алгоритма сортировки простым выбором на примере хранящихся n записей типа T в массиве k представлена в листинге 1. Комментарии в правой части листинга содержат число выполнения соответствующей строки алгоритма и поясняют определение его вычислительной сложности. В формулах через ui обозначено число записей k (j), j = i – 1, i – 2,..., 0, которые больше записи k (i), то есть составляют с ней инверсию.
|