Процесс обработки и поиска информации при решении многих задач проходит быстрее и эффективнее, если данные расположены в определенном порядке. Например, различные списки студентов, учащихся, сотрудников — в алфавитном порядке, числовые данные от большего значения к меньшему (или наоборот) и т.д.
Существует довольно много различных методов сортировки массивов, отличающихся друг от друга степенью эффективности, под которой понимается количество сравнений и количество обменов, произведенных в процессе сортировки. Рассмотрим подробно некоторые из них.
Сортировка массива методом простого выбора
При сортировке массива методом выбора применяется базовый алгоритм поиска максимального (минимального) элемента и его номера.
Алгоритм сортировки массива методом выбора:
- Для исходного массива выбрать максимальный элемент.
- Поменять его местами с последним элементом (после этого самый большой элемент будет стоять на своем месте).
- Повторить п.п. 1-2 с оставшимися n-1 элементами, то есть рассмотреть часть массива, начиная с первого элемента до предпоследнего, найти в нем максимальный элемент и поменять его местамис предпоследним (n-1)- м элементом массива, затем с оставшиеся (n-2)-мя элементами и так далее, пока не останется один элемент, уже стоящий на своем месте.
Для упорядочения массива потребуется (n-1) просмотров массива. В процессе сортировки будет увеличиваться отсортированная часть массива, а неотсортированная, соответственно, уменьшаться.
Сортировка массива в Javascript
При сортировке данных выполняется обмен содержимого переменных. Для обмена необходимо создавать временную переменную, в которой будет храниться содержимое одной из переменных. В противном случае ее содержимое окажется утерянным.
Задача 1. Массив из 10 элементов отсортировать по возрастанию методом простого перебора.
Напишем процедуру. Входным параметром для неё будет массив. Он же будет и выходным параметром. Поэтому описываем его как параметр-переменная (с ключевым словом var).
В процедуре внешний цикл по i — определяет длину рассматриваемой части массива. Она будет изменяться от n до 2.
Внутренний цикл по j используется для поиска максимального элемента и его номера. В качестве начального значения максимума разумно взять значение последнего элемента рассматриваемой части массива.
Программный код процедуры:
Procedure sorting1(var a:myarray); var i,j:integer; k,m:integer; begin for i:= n downto 2 do begin k:=i; m:=a[i]; for j:= 1 to i-1 do if a[j] > m then begin k:=j; m:=a[k] end; if k <> i then begin a[k]:=a[i]; a[i]:= m; end; end; end; end;
Программный код основной программы:
program primer_1;
const n = 10; type myarray = array[1..n] of integer; var a:myarray; Procedure sorting1(var a:myarray); . begin writeln(‘Введите исходный массив:’); for i:=1 to n do read(a[i]); sorting1(a); writeln(‘Отсортированный массив:’); for i:=1 to 10 do write(a[i],’ ‘); writeln; end.
Процесс упорядочения элементов в массиве по возрастанию методом отбора:
Язык C++ с нуля | #32 Сортировка массива в c++
| Номер элемента | 1 | 2 | 3 | 4 | 5 |
| Исходный массив | 8 | 7 | 5 | 4 | 2 |
| Первый просмотр | 2 | 7 | 5 | 4 | 8 |
| Второй просмотр | 2 | 4 | 5 | 7 | 8 |
| Третий просмотр | 2 | 4 | 5 | 7 | 8 |
| Четвертый просмотр | 2 | 4 | 5 | 7 | 8 |
При упорядочивании массива по убыванию необходимо перемещать минимальный элемент. Для чего в алгоритме нахождения максимального элемента достаточно знак «>» поменять на знак «
Сортировка массива методом простого обмена (методом пузырька)
Наиболее известным методом сортировки является сортировка пузырьковым методом. Его популярность объясняется запоминающимся названием и простым алгоритмом.
Метод основан на том, что в процессе исполнения алгоритма более «легкие» элементы массива постепенно «всплывают».
Особенностью данного метода является сравнение не каждого элемента со всеми, а сравнение в парах соседних элементов. Выполняется несколько последовательных просмотров массива от начала к концу. Если соседние элементы расположены «неправильно», то они меняются местами.
Алгоритм сортировки массива по возрастанию методом простого обмена:
- Начнем просмотр с первой пары элементов ( a[1] и a[2] ). Если первый элемент этой пары больше второго, то меняем их местами, иначе оставляем без изменения. Затем берем вторую пару элементов ( a[2] и a[3] ), если второй больше третьего, то также меняем их, далее сравниваем третий и четвертый, и если третий больше четвертого, меняем их местами, и т.д. Последними сравниваем (n-1)-ый и n-ый элементы.При первом обходе массива будут просмотрены все пары элементов массива a[i] и a[i+1] для i от 1 до (n-1). В результате максимальный элемент массива переместится в конец массива.
- Поскольку самый большой элемент находится на своем месте, рассмотрим часть массива без него, то есть с первого до (n-1) — го элемента.Повторим предыдущие действия для этой части массива, в результате чего второй по величине элемент массива переместится на последнее место рассматриваемой части массива, то есть на ( n-1 ) — е место во всем массиве.
- Эти действия продолжают до тех пор, пока количество элементов в текущей части массива не уменьшится до двух. В этом случае необходимо выполнить последнее сравнение и упорядочить последние два элемента.
Нетрудно заметить, что для преобразования массива, состоящего из n элементов, необходимо просмотреть его n–1 раз, каждый раз уменьшая диапазон просмотра на один элемент.
Ниже приведен текст процедуры сортировки массива по возрастанию методом пузырька.
procedure sorting2(var a:myarray); var k,i,t:integer; begin for k := 1 to n-1 do for i:=1 to n-k do if a[i] > a[i+1] then begin t:=a[i]; a[i]:=a[i+1]; a[i+1]:=t; end; end;
Для упорядочения элементов массива по убыванию их значений необходимо при сравнении элементов массива знак «>» заменить на «
Процесс упорядочения элементов в массиве по возрастанию методом обмена:
| Номер элемента | 1 | 2 | 3 | 4 | 5 |
| Исходный массив | 8 | 7 | 5 | 4 | 2 |
| Первый просмотр | 7 | 5 | 4 | 2 | 8 |
| Второй просмотр | 5 | 4 | 2 | 7 | 8 |
| Третий просмотр | 4 | 2 | 5 | 7 | 8 |
| Четвертый просмотр | 2 | 4 | 5 | 7 | 8 |
Источник: gospodaretsva.com
ГДЗ по информатике 9 класс учебник Поляков, Еремин § 23. Поиск и сортировка
При поиске в массиве, если нужного элемента нет, то поиск завершится неудачей и обычно возвращается специальное значение (например, -1), чтобы указать на отсутствие элемента в массиве.
2. Вспомните, как вы ищете слово в словаре. Попробуйте описать алгоритм, который позволит ускорить поиск, если все значения отсортированы (например, по возрастанию).
Для ускорения поиска, когда значения отсортированы, можно использовать бинарный поиск. Алгоритм бинарного поиска заключается в том, что на каждом шаге ищется средний элемент в отсортированной последовательности, и сравнивается с искомым значением. Если искомое значение больше, чем средний элемент, поиск продолжается в правой половине последовательности, иначе в левой половине.
3. Объясните, почему при поиске максимального элемента и его номера не нужно запоминать само значение максимального элемента.
При поиске максимального элемента и его номера не нужно запоминать само значение максимального элемента, так как можно использовать переменную-счетчик для хранения номера максимального элемента, и обновлять значение этой переменной, если встречается элемент, больший, чем текущий максимальный элемент.
4. На какой идее основан метод сортировки выбором?
Метод сортировки выбором основан на поиске минимального элемента в неотсортированной части массива и перестановке его в начало этой части, пока не будет отсортирован весь массив.
5. Объясните, зачем нужен вложенный цикл в алгоритме сортировки.
В алгоритме сортировки выбором вложенный цикл используется для нахождения минимального элемента в неотсортированной части массива. Внешний цикл используется для перебора всех элементов массива и установки границы между отсортированной и неотсортированной частями массива.
6. Как нужно изменить программу сортировки, чтобы элементы массива были отсортированы по убыванию?
Для изменения программы сортировки, чтобы элементы массива были отсортированы по убыванию, необходимо изменить условие сравнения на знак «больше» (>) вместо «меньше» (<) при нахождении минимального элемента в неотсортированной части массива.
Источник: izi-otvet.ru
Обработка массивов.
Современные компьютеры работают с огромными массивами данных. При этом размер программы не зависит от размера массива: можно написать очень короткую программу, которая обрабатывает миллиарды чисел.
Из курса 8 класса вы уже знаете, как найти сумму элементов массива и его максимальный (минимальный) элемент, определить количество элементов, удовлетворяющих условию. В этом параграфе мы изучим некоторые более сложные алгоритмы.
Вспомните и запишите в тетрадь, как:
• объявить целочисленный массив из N элементов;
• заполнить массив нулями;
• заполнить массив натуральными числами от 1 до N;
• заполнить массив случайными числами в диапазоне [50, 100];
• найти сумму значений всех элементов массива;
• найти сумму значений чётных элементов массива;
• найти количество отрицательных элементов массива;
• найти максимальный элемент массива.
Перестановка элементов массива
Во многих задачах нужно переставлять элементы массива, т. е. требуется менять местами значения двух ячеек памяти.
Представьте себе, что в кофейной чашке налит сок, а в стакане — кофе, и вы хотите, чтобы было наоборот. Что вы сделаете?
Вернёмся к программированию. Чтобы поменять местами значения двух переменных — а и b, нужно использовать третью переменную того же типа:
Перестановка двух элементов массива, например А [i] и А [к], выполняется так же:
Теперь рассмотрим несколько задач, в которых требуется переставить элементы массива в другом порядке.
Задача 1. Массив А содержит чётное количество элементов N. Нужно поменять местами пары соседних элементов: первый со вторым, третий — с четвёртым и т.д. (рис. 4.1).
Рис. 4.1
С каким элементом нужно поменять местами элемент А [i]? Зависит ли ваш ответ от свойств числа i?
Сергей написал такой алгоритм для решения задачи 1:
нц для i от 1 до N
поменять местами A[i] и A[i+1]
кц
Выполните его вручную для массива (N = 4). Объясните результат. Найдите ошибки в этом алгоритме.
Обратите внимание, что на последнем шаге цикла мы будем менять местами элемент А [ N ] с несуществующим элементом A [N+1 ]. Это вызовет ошибку, которая называется выход за границы массива. Но даже если изменить наибольшее значение переменной цикла на N-1, программа всё равно будет работать неправильно, т. е. приведёт к неверному решению задачи 1. Получится, что первый элемент просто «переедет» на место последнего.
Для того чтобы исправить программу, нужно изменять переменную i с шагом 2:
Решение на языке Паскаль получилось немного более сложным, потому что в этом языке можно изменять переменную цикла только с шагом 1 или -1, а нам нужен шаг 2. В этой ситуации можно, например, использовать цикл с условием (цикл while).
Предложите другое решение этой задачи, записав нужные операторы в теле цикла.
Реверс массива
Задача 2. Требуется выполнить реверс массива, т. е. переставить элементы массива в обратном порядке, так чтобы первый элемент стал последним, а последний — первым (рис. 4.2).
Рис. 4.2
С каким элементом нужно поменять местами элемент А [1] ? Элемент А [2]? Элемент А [i]?
Если индекс первого элемента в паре увеличивается на 1, а индекс второго элемента уменьшается на 1, что можно сказать о сумме индексов этих элементов?
В этой задаче сумма индексов элементов, участвующих в обмене, для всех пар равна N+1, поэтому элемент с номером i должен меняться местами с (N+l-i)-M элементом.
Выполните вручную следующий алгоритм для массива (N = 4). Объясните результат. Найдите ошибки в этом алгоритме (почему он не решает задачу 2?).
нц для i от 1 до N
поменять местами A[i] и А[N+1-i]
кц
Для того чтобы не выполнять реверс дважды, нужно остановить цикл на середине массива:
нц для i от 1 до div(N, 2)
поменять местами А[i] и A[N+l-i]
кц
Запишите в тетради операторы, которые нужно добавить в тело цикла. Для обмена используйте вспомогательную переменную с.
нц для i от 1 до div(N, 2) for i:=l to N div 2 do begin
• • • • • •
КЦ end;
Запишите в тетради другое решение задачи реверса массива, которое использует цикл с условием (пока, while).
Линейный поиск в массиве
Очень часто требуется найти в массиве заданное значение или определить, что его там нет. Для этого нужно просмотреть все элементы массива с первого до последнего. Как только будет найден элемент, равный заданному значению X, надо завершить цикл и вывести результат. Такой поиск называется линейным.
Сколько операций сравнения придётся выполнить, если в массиве N элементов? В каком случае количество сравнений будет наименьшим? Наибольшим?
Катя торопилась и написала такой алгоритм линейного поиска:
i:=1
нц пока A[i]<>Х i:=i+l
кц
вывод ‘А [‘, i,’] = ‘,X
Проверьте: правильно ли сработает алгоритм, если искать в массиве число 2? Число 4?
Этот алгоритм хорошо работает, если нужный элемент в массиве есть, однако приведёт к ошибке, если такого элемента нет, — получится зацикливание и выход за границы массива. Чтобы этого не произошло, в условие нужно добавить ещё одно ограничение: i
В сложном условии i X первым должно проверяться именно отношение i N, проверка условия А [i] <> X приводит к выходу за границы массива, и программа может завершиться аварийно.
Возможен ещё один поход к решению этой задачи: используя цикл с переменной, перебрать все элементы массива и досрочно завершить цикл, если найдено требуемое значение:
Для выхода из цикла используется оператор выход (в Паскале — break), номер найденного элемента сохраняется в переменной nХ. Если её значение осталось равным нулю (не изменилось в ходе выполнения цикла), то в массиве нет элемента, равного X.
Сортировка массивов
Сортировка — это расстановка элементов списка (массива) в заданном порядке.
Возникает естественный вопрос: зачем сортировать данные? На него легко ответить, вспомнив, например, работу со словарями: сортировка слов по алфавиту облегчает поиск нужной информации.
Для чисел обычно используют сортировку по возрастанию (каждый следующий элемент больше предыдущего) или убыванию (следующий элемент меньше предыдущего). Если в массиве есть одинаковые элементы, их можно расставить по неубыванию (каждый следующий элемент не меньше предыдущего) или невозрастанию.
Математики и программисты изобрели множество способов сортировки. В целом их можно разделить на две группы: 1) простые, но медленно работающие (на больших массивах), и 2) сложные, но быстрые.