Метод сортировки, который многие обычно осваивают раньше других из-за его исключительной простоты, называется пузырьковой сортировкой (bubble sort), в рамках которой выполняются следующие действия: проход по файлу с обменом местами соседних элементов, нарушающих заданный порядок, до тех пор, пока файл не будет окончательно отсортирован. Основное достоинство пузырьковой сортировки заключается в том, что его легко реализовать в виде программы. Для понимания и реализации этот алгоритм — простейший, но эффективен он лишь для небольших массивов. Сложность алгоритма:
O(n2)O(n2).Суть алгоритма пузырьковой сортировки состоит в сравнении соседних элементов и их обмене, если они находятся не в надлежащем порядке. Неоднократно выполняя это действие, мы заставляем наибольший элемент "всплывать" к концу массива. Следующий проход приведет к всплыванию второго наибольшего элемента, и так до тех пор, пока после
n−1n−1 итерации массив не будет полностью отсортирован.Сортировка выбором начинается с поиска наименьшего элемента в списке и обмена его с первым элементом (таким образом, наименьший элемент помещается в окончательную позицию в отсортированном массиве). Затем мы сканируем массив, начиная со второго элемента, в поисках наименьшего среди оставшихся
n−1n−1элементов и обмениваем найденный наименьший элемент со вторым, т.е. помещаем второй наименьший элемент в окончательную позицию в отсортированном массиве. В общем случае, при i-ом проходе по списку (0⩽i⩽n−2)(0⩽i⩽n−2) алгоритм ищет наименьший элемент среди последних n−in−i элементов и обменивает его с A[i]A[i]. После выполнения n−1n−1 проходов список оказывается отсортирован.На каждом шаге алгоритма сортировки встаками выбирается один из элементов входного массива и вставляется на нужную позицию в уже отсортированном массиве, до тех пор, пока входных элементы не будут исчерпана. Метод выбора очередного элемента из исходного массива произволен; может использоваться практически любой алгоритм выбора. Обычно (и с целью получения устойчивого алгоритма сортировки), элементы вставляются по порядку их появления во входном массиве. В приведённой ниже реализации на JavaScript алгоритма сортировки встаками используется именно эта стратегия выбора.
Вначале для каждого элемента массива подсчитывается количество элементов, меньших, чем он, и на основе этой информации текущий элемент помещается в соответствующее место отсортированного массива. Ниже приведёна простая реализация алгоритм сортировки массива методом подсчета на JavaScript.
type
Human = class
public
q: integer; // 1 класс
e: integer; // 2 класс
r: integer; // 3 класс
t: integer; // 4 класс
y: integer // 5 класс
u: integer; // 6 класс
i: integer; // 7 класс
o: integer; // 8 класс
p: integer; // 9 класс
a: integer; // 10 класс
s: integer; // 11 класс
d: integer; // 12 класс
f: integer; // 13 класс
g: integer; // 14 класс
j: integer; // 15 класс
end;
var
H: human;
begin
H:= new Human;
writeln('Введите кол-во хорошистов в 1 классе');
readln(h.q);
writeln('Введите кол-во хорошистов в 2 классе');
readln(h.e);
writeln('Введите кол-во хорошистов в 3 классе');
readln(h.r);
writeln('Введите кол-во хорошистов в 4 классе');
readln(h.t);
writeln('Введите кол-во хорошистов в 5 классе');
readln(h.y);
writeln('Введите кол-во хорошистов в 6 классе');
readln(h.u);
writeln('Введите кол-во хорошистов в 7 классе');
readln(h.i);
writeln('Введите кол-во хорошистов в 8 классе');
readln(h.o);
writeln('Введите кол-во хорошистов в 9 классе');
readln(h.p);
writeln('Введите кол-во хорошистов в 10 классе');
readln(h.a);
writeln('Введите кол-во хорошистов в 11 классе');
readln(h.s);
writeln('Введите кол-во хорошистов в 12 классе');
readln(h.d);
writeln('Введите кол-во хорошистов в 13 классе');
readln(h.f);
writeln('Введите кол-во хорошистов в 14 классе');
readln(h.g);
writeln('Введите кол-во хорошистов в 15 классе');
readln(h.j);
writeln('Мы сорали информацию о классах');
writeln('В 1 классе: ', h.q, ' хорошист(а/ов)');
writeln('В 2 классе: ', h.e, ' хорошист(а/ов)');
writeln('В 3 классе: ', h.r, ' хорошист(а/ов)');
writeln('В 4 классе: ', h.t, ' хорошист(а/ов)');
writeln('В 5 классе: ', h.y, ' хорошист(а/ов)');
writeln('В 6 классе: ', h.u, ' хорошист(а/ов)');
writeln('В 7 классе: ', h.i, ' хорошист(а/ов)');
writeln('В 8 классе: ', h.o, ' хорошист(а/ов)');
writeln('В 9 классе: ', h.p, ' хорошист(а/ов)');
writeln('В 10 классе: ', h.a, ' хорошист(а/ов)');
writeln('В 11 классе: ', h.s, ' хорошист(а/ов)');
writeln('В 12 классе: ', h.d, ' хорошист(а/ов)');
writeln('В 13 классе: ', h.f, ' хорошист(а/ов)');
writeln('В 14 классе: ', h.g, ' хорошист(а/ов)');
writeln('В 15 классе: ', h.j, ' хорошист(а/ов)');
end.