Сортировка Шелл.
Представляет собой модификацию метода вставок. Используются сравнения и перестановки элементов, но в отличие от метода вставок, в сравнении участвуют не соседние, а отстоящие друг от друга на определенном расстоянии элементы. При необходимости перестановки, элементы перемещаются скачком на данное расстояние, а не на одну позицию.
В одной из модификаций метода (в случае, предложенном Д. Шеллом) шаг кратен степеням двойки. Вначале последовательность из N элементов делится на N/2 групп, если N – четно, и на (N-1)/2 групп, если N – нечетно. Каждая группа содержит по два элемента, если количество элементов было нечетным, одна из групп содержит три элемента. Элементы каждой группы отстоят друг от друга на расстоянии N/2 или (N-1)/2. В течение первого прохода осуществляется упорядочение элементов каждой группы методом вставок. Для осуществления следующего прохода шаг уменьшается вдвое (как и число групп), по отношению к предыдущему шагу (у дробных чисел берется целая часть). Процесс повторяется до тех пор, пока шаг не станет равным единице. В этом случае методом вставок сортируется весь список (одна группа). С точки зрения программной реализации потребуется неоднократный вызов сортировки вставками с указанием, в качестве параметров (помимо исходного списка и числа элементов), индекса начального элемента группы и шага. Приблизительное число сравнений составляет N log 2 N.
// Функция сортировки Шелла целочисленного массива
// Аргументы:
// arr - сортируемый массив
// size - размер сортируемого массива
void SortShell(int* arr, int size) {
int step = size / 2;
while (step != 0) {
// Сортируем группы элементов отстоящих друг от друга на значение шага вставками
for (int i = step; i < size; ++i) {
int tmp = arr[i];
for (j = i - step; j >= 0 && arr[j] > tmp; j -= step)
arr = arr[j];
arr = tmp;
Сортировка выбором
В процессе первого прохода в исходном массиве находятся минимальный элемент, который помещается на место первого элемента. Первый элемент помещается на место минимального. На втором и последующих проходах поиск и обмен повторяются для оставшихся после предыдущего прохода элементов (с позициями: на втором проходе – со второй по последнюю, на третьем проходе – с третьей по последнюю и т.д.) до тех пор, пока не будет отсортирована вся последовательность. Общее число сравнений составляет приблизительно 0,5 N 2 , N – здесь и далее число элементов.
void selectSort(int a, long size) {
for(i=0; i < size; i++) { // i - номер текущего шага
for(j=i+1; j < size; j++) // цикл выбора наименьшего элемента
if (a[j] < x) {
k=j; x=a[j]; // k - индекс наименьшего элемента
a[k] = a[i]; a[i] = x; // меняем местами наименьший с a[i]
Сортировка пузырьком
В процессе сортировки производится попарное сравнение соседних элементов. Если порядок следования соседних элементов нарушен, то они меняются местами. В процессе первого прохода максимальный элемент попадает на последнее место и, следовательно, в последующих сравнениях не участвует. Остальные элементы "всплывают" на одну позицию вверх (поэтому метод часто называют сортировкой "пузырьком"). На каждом следующем проходе рассматривается последовательность для N-1, N-2 и т.д. элементов. Если при каком-либо проходе не было произведено ни одной перестановки, последовательность отсортирована. Максимальное число сравнений составляет приблизительно 0,5 N 2 , среднее число сравнений пропорционально 0,25 N 2 , среднее число обменов – 0,25 N 2 .
void bubbleSort(int a, long size) {
for(i=0; i < size; i++) { // i - номер прохода
for(j = size-1; j > i; j--) { // внутренний цикл прохода
if (a > a[j]) {
x=a; a=a[j]; a[j]=x;
Сортировка вставками
Первый элемент исходного списка считается отсортированным списком длины 1. Двухэлементный отсортированный список создается добавлением второго элемента исходного списка в нужное место одноэлементного списка, содержащего первый элемент. В целом, каждый новый элемент вставляется в подходящее место среди ранее упорядоченных элементов. Среднее число сравнений пропорционально N 2 .
void insertSort(int a, long size) {
for (i=0; i < size; i++) { // цикл проходов, i - номер прохода
// поиск места элемента в готовой последовательности
for (j=i-1; j>=0 && a[j] > x; j--)
a = a[j]; // сдвигаем элемент направо, пока не дошли
// место найдено, вставить элемент
Метод подсчёта
Метод основан на том, что k+1-ый элемент упорядоченной последовательности превышает ровно k элементов, и следовательно занимает k+1-ую позицию. В процессе сортировки на каждом i-ом проходе i-ый элемент исходной последовательности попарно сравнивается со всеми остальными элементами. Инициализированный нулем перед началом прохода счетчик k увеличивается, если i-ый элемент оказался больше текущего. Таким образом, порядковый номер i-го элемента, по окончанию i-го прохода, равен k+1. Для сортировки последовательности из N элементов требуется N проходов, на каждом из которых выполняется N сравнений. Число сравнений равно N 2 . Приведенный метод подсчета можно использовать,
void insertSort(int a, long size)
int *b=new int;
for
(int
i=0;i for
(int
j=0;j if
(a[i]>a[j]){ Сортировка
по дереву (6)
Процесс
сортировки состоит из: фазы построения
двоичного дерева поиска и фазы обхода.
Структура двоичного дерева задается с
помощью связного списка, каждый элемент
которого может иметь, максимум, двух
потомков (две ссылки). Двоичное дерево
формируется по всем исходным элементам,
по следующему правилу. Первый элемент
исходной последовательности является
первым узлом дерева. Следующий элемент
последовательности сравнивается со
значениями в узлах строящегося дерева,
начиная с корня. Если значение текущего
элемента больше значения элемента в
узле дерева, следует переместиться вниз
по правой ссылке от текущего узла, в
противном случае – по левой ссылке.
Перемещение по дереву продолжается до
тех пор, пока не будет достигнута
свободная ссылка, после чего осуществляется
вставка элемента в дерево. После
формирования дерева необходимо провести
процедуру смешанного обхода. Он
заключается в рекурсивном посещении
(чтении) узлов, начиная с корня: левого
поддерева, узла, правого поддерева. В
результате получается отсортированная
последовательность. Среднее число
сравнений aN log 2
N, 1 < a < 2. Сбалансированное
N-ленточное слияние
Общей
формой внешней сортировки является
N-ленточное слияние. Для N-ленточного
слияния потребуется 2N магнитных лент
и 2N лентопротяжных устройств (которые
можно заменить 2N файлами на устройстве
внешней памяти). Исходная неупорядоченная
последовательность размещается на
первой магнитной ленте. Затем она
разносится на N магнитных лент по
следующему правилу: первая запись – на
первую из N лент, вторая – на вторую,
(N+1)-ая – снова на первую из N лент. Сбалансированное
N-ленточное слияние осуществляется в
два этапа. На первом этапе из записей,
хранящихся на каждой магнитной ленте,
формируются упорядоченные цепочки. Так
как все цепочки имеют одинаковую длину,
слияние называется сбалансированным.
Упорядочение цепочки происходит в
оперативной памяти одним из методов
внутренней сортировки. Упорядоченные
цепочки размещаются на N свободных
магнитных лентах, после чего начинается
второй этап сортировки – слияние.
Процесс слияния осуществляется в
несколько циклов. После каждого цикла
слияния длина упорядоченных цепочек
увеличивается на N.
В конечном итоге, формируется упорядоченная
последовательность из N составляющих.
Собственно слияние осуществляется
следующим образом. Пусть имеются две
цепочки длиной l
,
изначально упорядоченные. Необходимо
получить одну упорядоченную цепочку.
Для этого: сравниваются первые элементы
двух цепочек, меньшая переписывается
в результирующую цепочку; операция
осуществляется с помощью трех счетчиков;
после записи в результирующую
последовательность увеличивается на
единицу счетчик результирующей
последовательности и счетчик
последовательности, в которой был
обнаружен меньший элемент; действие
повторяется до тех пор, пока один из
счетчиков исходной последовательности
не достигнет значения конца
последовательности, после чего оставшиеся
элементы другой последовательности
дописываются в конец результирующей.
Таким образом, будут упорядочены каждая
из N магнитных лент. В статье рассмотрены одни из самых популярных алгоритмов сортировки для массивов, применяемых как практически, так и в учебных целях. Сразу хочу оговориться, что все рассмотренные алгоритмы медленнее, чем метод классической сортировки массива через список значений, но тем не менее, заслуживают внимания. Текста получается много, поэтому по каждому алгоритму описываю самое основное.
1.Алгоритм "Сортировка выбором".
Является одним из самых простых алгоритмов сортировки массива. Смысл в том, чтобы идти по массиву и каждый раз искать минимальный элемент массива, обменивая его с начальным элементом неотсортированной части массива. На небольших массивах может оказаться даже эффективнее, чем более сложные алгоритмы сортировки, но в любом случае проигрывает на больших массивах. Число обменов элементов по сравнению с "пузырьковым" алгоритмом N/2, где N - число элементов массива. Алгоритм:
//Сортировка выбором {---
Функция СортировкаВыбором(Знач Массив)
Мин = 0;
Для i = 0 По Массив.ВГраница() Цикл
Мин = i;
Для j = i + 1 ПО Массив.ВГраница() Цикл //Ищем минимальный элемент в массиве
Если Массив[j] < Массив[Мин] Тогда
Мин = j;
КонецЕсли;
КонецЦикла;
Если Массив [Мин] = Массив [i] Тогда //Если мин. элемент массива = первому элементу неотс. части массива, то пропускаем.
Продолжить;
КонецЕсли;
Смена = Массив[i]; //Производим замену элементов массива.
Массив[i] = Массив[Мин];
Массив[Мин] = Смена;
КонецЦикла;
Возврат Массив;
КонецФункции
2.Алгоритм "Сортировка пузырьком".
Пожалуй самый известный алгоритм, применяемый в учебных целях, для практического же применения является слишком медленным. Алгоритм лежит в основе более сложных алгоритмов: "Шейкерная сортировка", "Пирамидальная сортировка", "Быстрая сортировка". Примечательно то, что один из самых быстрых алгоритмов "Быстрый алгоритм" был разработан путем модернизации одного из самых худших алгоритмов "Сортировки пузырьком"."Быстрая" и "Шейкерная" сортировки будут рассмотрены далее. Смысл алгоритма заключается в том, что самые "легкие" элементы массива как бы "всплывают" , а самые "тяжелые" "тонут". Отсюда и название "Сортировка пузырьком" Алгоритм:
//Сортировка пузырьком {---
Функция СортировкаПузырьком(Знач Массив)
Для i = 0 По Массив.ВГраница() Цикл
Для j = 0 ПО Массив.Вграница() - i - 1 Цикл
Если Массив[j] > Массив Тогда
Замена = Массив[j];
Массив[j] = Массив;
Массив = Замена;
КонецЕсли;
КонецЦикла;
КонецЦикла;
Возврат Массив;
КонецФункции
//---}
3.Алгоритм "Шейкерная сортировка"(Сортировка перемешиванием,Двунаправленная пузырьковая сортировка).
Алгоритм представляет собой одну из версий предыдущей сортировки - "сортировки пузырьком". Главное отличие в том, что в классической сортировке пузырьком происходит однонаправленное движение элементов снизу - вверх, то в шейкерной сортировке сначало происходит движение снизу-вверху, а затем сверху-вниз. Алгоритм такой же, что и у пузырьковой сортировки + добавляется цикл пробега сверху-вниз. В приведенном ниже примере, есть усовершенствование в шейкерной сортировке. В отличие от классической, используется в 2 раза меньше итераций.
//Сортировка перемешивание (Шейкер-Сортировка) {---
Функция СортировкаПеремешиванием(Знач Массив)
Для i = 0 ПО Массив.ВГраница()/2 Цикл
нИтер = 0;
конИтер = Массив.ВГраница();
Пока нИтер Массив[нИтер+1] Тогда
Замена = Массив[нИтер];
Массив[нИтер] = Массив[нИтер + 1];
Массив[нИтер + 1] = Замена;
КонецЕсли;
нИтер = нИтер + 1;//Двигаем позицию на шаг вперед
//Проходим с конца
Если Массив[конИтер - 1] > Массив[конИтер] Тогда
Замена = Массив[конИтер - 1];
Массив[конИтер-1] = Массив[конИтер];
Массив[конИтер] = Замена;
КонецЕсли;
конИтер = конИтер - 1;//Двигаем позицию на шаг назад
КонецЦикла;
КонецЦикла;
Возврат Массив;
КонецФункции
//---}
4. Алгоритм "Гномья сортировка".
Алгоритм так странно назван благодаря голландскому ученому Дику Груну. Гномья сортировка основана на технике, используемой обычным голландским садовым гномом (нидерл. tuinkabouter). Это метод, которым садовый гном сортирует линию цветочных горшков. По существу он смотрит на следующий и предыдущий садовые горшки: если они в правильном порядке, он шагает на один горшок вперёд, иначе он меняет их местами и шагает на один горшок назад. Граничные условия: если нет предыдущего горшка, он шагает вперёд; если нет следующего горшка, он закончил.
Вот собственно и все описание алгоритма "Гномья сортировка". Что интересно, алгоритм не содержит вложенных циклов, а сортирует весь массив за один проход.
//Гномья сортировка {---
Функция ГномьяСортировка(Знач Массив)
i = 1;
j = 2;
Пока i < Массив.Количество() Цикл // Сравнение < - Сортировка по возрастанию, > - по убыванию
Если Массив
i = j;
j = j + 1;
Иначе
Замена = Массив[i];
Массив[i] = Массив;
Массив = Замена;
i = i - 1;
Если i = 0 Тогда
i = j;
j = j + 1;
КонецЕсли;
КонецЕсли;
КонецЦикла;
Возврат Массив;
КонецФункции
//---}
5. Алгоритм "Сортировка вставками".
Представляет собой простой алгоритм сортировки. Смысл заключается в том, что на каждом шаге мы берем элемент, ищем для него позицию и вставляем в нужное место. 6. Алгортим "Сортировка слиянием".
Интересный в плане реализации и идеи алгоритм. Смысл его в том, чтобы разбивать массив на подмассивы, пока длина каждого подмассива не будет равна 1. Тогда мы утверждаем, что такой подмассив отсортирован. Затем сливаем получившиеся подмассивы воедино, одновременно сравнивая и сортируя
поэлементно значения подмассивов. p/s не смог вставить сюда рисунок с более наглядной схемой, постоянно размазывается. Зато хорошо видна в блоке скриншотов внизу. Можно посмотреть как работает алгоритм. //Сортировка слиянием {---
Функция СортировкаСлиянием(Знач Массив)
Если Массив.Количество() = 1 Тогда
Возврат Массив;
КонецЕсли;
ТочкаРазрыв = Массив.Количество() / 2;
лМассив = Новый Массив;
прМассив = Новый Массив;
Для Сч = 0 ПО Массив.ВГраница() Цикл
Если Сч < ТочкаРазрыв Тогда
лМассив.Добавить(Массив[Сч]);
Иначе
прМассив.Добавить(Массив[Сч]);
КонецЕсли;
КонецЦикла;
Возврат Слияние(СортировкаСлиянием(лМассив),СортировкаСлиянием(прМассив));
КонецФункции
Функция Слияние(массив1,массив2)
a = 0;
b = 0;
слМассив = Новый Массив;
Для Сч = 0 ПО (Массив1.Количество() + Массив2.Количество())-1 Цикл
слМассив.Добавить();
КонецЦикла;
Для i = 0 ПО (массив1.Количество() + массив2.Количество())-1 Цикл
Если b < массив2.Количество() И a < массив1.Количество() Тогда
Если (массив1[a] > массив2[b]) И (b < массив2.Количество()) Тогда
слМассив[i] = массив2[b];
b = b + 1;
Иначе
слМассив[i] = массив1[a];
a = a + 1;
КонецЕсли;
Иначе
Если b < массив2.количество() Тогда
слМассив[i] = массив2[b];
b = b + 1;
Иначе
слМассив[i] = массив1[a];
a = a + 1;
КонецЕсли;
КонецЕсли;
КонецЦикла;
Возврат слМассив;
КонецФункции
//---}
7. Алгортим "Сортировка Шелла".
Алгоритм назван так в честь американского ученого Дональда Шелла. По своей сути этот алгоритм является усовершенствованным алгоритмом "Сортировка вставками". Смысл алгоритма заключается в том, чтобы сравнивать не только элементы, стоящие рядом друг с другом, но и на некотором удалении. Сначало выбирается Шаг - некий промежуток, через который будут сравниваться элементы массива на каждой итерации. Обычно его определяют так: Пример: 10
,2
,3
,1,14
,5
,7
,12 2. Шаг = 2 3
,1
,7
,2
,10
,5
,14
,12
3. Шаг = 1 1,2,3,5,7,10,12,14 8. Алгортим "Быстрая сортировка".
Наиболее популярный и применяемый алгоритм на практике. Является одним из самых эффективных алгоритмов сортировки данных.
//Алгоритм "Быстрая сортировка" {
Процедура б_Сортировка(Массив,НижнийПредел,ВерхнийПредел)
i = НижнийПредел;
j = ВерхнийПредел;
m = Массив[Цел((i+j)/2)];
Пока Истина Цикл
Пока Массив[i] < m Цикл
i = i + 1;
КонецЦикла;
Пока Массив[j] > m Цикл
j = j - 1;
КонецЦикла;
Если i > j Тогда
Прервать;
КонецЕсли;
КонецЦикла;
Если НижнийПредел < j Тогда
б_Сортировка(Массив,НижнийПредел,j);
КонецЕсли;
Если i < ВерхнийПредел Тогда
б_Сортировка(Массив,i,ВерхнийПредел);
КонецЕсли;
КонецПроцедуры
Функция БыстраяСортировка(Массив)
НижняяГраница = 0;
ВерхняяГраница = Массив.ВГраница();
б_Сортировка(Массив,НижняяГраница,ВерхняяГраница);
Возврат Массив;
КонецФункции
//---}
9. Классическая сортировка массива в 1с.
Передаем массив в список значений. Сортируем стандартным методом "Сортировать".
//Сортировка списком значений {---
Функция СортировкаСпискомЗначений(Знач Массив)
мСписокЗнч = Новый СписокЗначений;
мСписокЗнч.ЗагрузитьЗначения(Массив);
мСписокЗнч.СортироватьПоЗначению(НаправлениеСортировки.Возр);
Возврат мСписокЗнч.ВыгрузитьЗначения();
КонецФункции
//---}
Все сортировки можно ускорить расположив код в циклах в 1 строку. Но для читабельности, оставил так.
Написал обработку в которой реализованы все вышеперечисленные алгоритмы, также поддерживается динамическая анимация процесса сортировки
(Кроме стандартной сортировки 1с).
-При запуске обработки автоматически происходит формирование массива случайных чисел от 0 до 100 размерностью 100 элементов. Динамическая отрисовка процесса сортировки очень сильно снижает производительность, зато наглядно видно как работает алгоритм.
8 Сортировка вставкой
9 А N Пусть нужно отсортировать массив А по возрастанию, в котором N элементов методом вставки Вспомогательные переменные j j – номер первого элемента остатка. i i – номер перемещаемого элемента. f f=1 f – условие выхода из цикла (если f=1, то выход) Val Val – промежуточное значение, используемое для перемещения элементов массив Постановка задачи
A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма." title="10 Начало алгоритма. Шаг 1 Шаг 1 j:=2, Шаг 2 Шаг 2 Пока j=2 и f=0 выполнять: Шаг 2.2.1 Шаг 2.2.1 Если A>A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма." class="link_thumb">
10
10 Начало алгоритма. Шаг 1 Шаг 1 j:=2, Шаг 2 Шаг 2 Пока j=2 и f=0 выполнять: Шаг Шаг Если A>A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг Шаг i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма.
A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма.">
A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма.">
A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма." title="10 Начало алгоритма. Шаг 1 Шаг 1 j:=2, Шаг 2 Шаг 2 Пока j=2 и f=0 выполнять: Шаг 2.2.1 Шаг 2.2.1 Если A>A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма.">
title="10 Начало алгоритма. Шаг 1 Шаг 1 j:=2, Шаг 2 Шаг 2 Пока j=2 и f=0 выполнять: Шаг 2.2.1 Шаг 2.2.1 Если A>A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма.">
A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Что обозначает" title="11 Начало алгоритма. Шаг 1 Шаг 1 j:=2, Шаг 2 Шаг 2 Пока j=2 и f=0 выполнять: Шаг 2.2.1 Шаг 2.2.1 Если A>A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Что обозначает" class="link_thumb">
11
11 Начало алгоритма. Шаг 1 Шаг 1 j:=2, Шаг 2 Шаг 2 Пока j=2 и f=0 выполнять: Шаг Шаг Если A>A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг Шаг i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Что обозначает данное условие?
A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Что обозначает">
A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Что обозначает данное условие?">
A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Что обозначает" title="11 Начало алгоритма. Шаг 1 Шаг 1 j:=2, Шаг 2 Шаг 2 Пока j=2 и f=0 выполнять: Шаг 2.2.1 Шаг 2.2.1 Если A>A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Что обозначает">
title="11 Начало алгоритма. Шаг 1 Шаг 1 j:=2, Шаг 2 Шаг 2 Пока j=2 и f=0 выполнять: Шаг 2.2.1 Шаг 2.2.1 Если A>A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Что обозначает">
A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Почему стартов" title="12 Начало алгоритма. Шаг 1 Шаг 1 j:=2, Шаг 2 Шаг 2 Пока j=2 и f=0 выполнять: Шаг 2.2.1 Шаг 2.2.1 Если A>A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Почему стартов" class="link_thumb">
12
12 Начало алгоритма. Шаг 1 Шаг 1 j:=2, Шаг 2 Шаг 2 Пока j=2 и f=0 выполнять: Шаг Шаг Если A>A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг Шаг i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Почему стартовое значение j =2 ?
A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Почему стартов">
A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Почему стартовое значение j =2 ?">
A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Почему стартов" title="12 Начало алгоритма. Шаг 1 Шаг 1 j:=2, Шаг 2 Шаг 2 Пока j=2 и f=0 выполнять: Шаг 2.2.1 Шаг 2.2.1 Если A>A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Почему стартов">
title="12 Начало алгоритма. Шаг 1 Шаг 1 j:=2, Шаг 2 Шаг 2 Пока j=2 и f=0 выполнять: Шаг 2.2.1 Шаг 2.2.1 Если A>A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Почему стартов">
A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Почему стартов" title="13 Начало алгоритма. Шаг 1 Шаг 1 j:=2, Шаг 2 Шаг 2 Пока j=2 и f=0 выполнять: Шаг 2.2.1 Шаг 2.2.1 Если A>A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Почему стартов" class="link_thumb">
13
13 Начало алгоритма. Шаг 1 Шаг 1 j:=2, Шаг 2 Шаг 2 Пока j=2 и f=0 выполнять: Шаг Шаг Если A>A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг Шаг i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Почему стартовое значение i =2 ?
A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Почему стартов">
A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Почему стартовое значение i =2 ?">
A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Почему стартов" title="13 Начало алгоритма. Шаг 1 Шаг 1 j:=2, Шаг 2 Шаг 2 Пока j=2 и f=0 выполнять: Шаг 2.2.1 Шаг 2.2.1 Если A>A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Почему стартов">
title="13 Начало алгоритма. Шаг 1 Шаг 1 j:=2, Шаг 2 Шаг 2 Пока j=2 и f=0 выполнять: Шаг 2.2.1 Шаг 2.2.1 Если A>A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Почему стартов">
A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Всегда ли прои" title="14 Начало алгоритма. Шаг 1 Шаг 1 j:=2, Шаг 2 Шаг 2 Пока j=2 и f=0 выполнять: Шаг 2.2.1 Шаг 2.2.1 Если A>A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Всегда ли прои" class="link_thumb">
14
14 Начало алгоритма. Шаг 1 Шаг 1 j:=2, Шаг 2 Шаг 2 Пока j=2 и f=0 выполнять: Шаг Шаг Если A>A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг Шаг i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Всегда ли происходит обмен входного j элемента с отсортированным элементом?
A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Всегда ли прои">
A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Всегда ли происходит обмен входного j элемента с отсортированным элементом?">
A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Всегда ли прои" title="14 Начало алгоритма. Шаг 1 Шаг 1 j:=2, Шаг 2 Шаг 2 Пока j=2 и f=0 выполнять: Шаг 2.2.1 Шаг 2.2.1 Если A>A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Всегда ли прои">
title="14 Начало алгоритма. Шаг 1 Шаг 1 j:=2, Шаг 2 Шаг 2 Пока j=2 и f=0 выполнять: Шаг 2.2.1 Шаг 2.2.1 Если A>A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Всегда ли прои">
A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Возможно ли за" title="15 Начало алгоритма. Шаг 1 Шаг 1 j:=2, Шаг 2 Шаг 2 Пока j=2 и f=0 выполнять: Шаг 2.2.1 Шаг 2.2.1 Если A>A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Возможно ли за" class="link_thumb">
15
15 Начало алгоритма. Шаг 1 Шаг 1 j:=2, Шаг 2 Шаг 2 Пока j=2 и f=0 выполнять: Шаг Шаг Если A>A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг Шаг i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Возможно ли заменить цикл ПОКА и ЕСЛИ одним циклом ПОКА с условием i>=2 и A>A[i] ?
A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Возможно ли за">
A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Возможно ли заменить цикл ПОКА и ЕСЛИ одним циклом ПОКА с условием i>=2 и A>A[i] ?">
A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Возможно ли за" title="15 Начало алгоритма. Шаг 1 Шаг 1 j:=2, Шаг 2 Шаг 2 Пока j=2 и f=0 выполнять: Шаг 2.2.1 Шаг 2.2.1 Если A>A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Возможно ли за">
title="15 Начало алгоритма. Шаг 1 Шаг 1 j:=2, Шаг 2 Шаг 2 Пока j=2 и f=0 выполнять: Шаг 2.2.1 Шаг 2.2.1 Если A>A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Возможно ли за">
A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Для чего нужен" title="16 Начало алгоритма. Шаг 1 Шаг 1 j:=2, Шаг 2 Шаг 2 Пока j=2 и f=0 выполнять: Шаг 2.2.1 Шаг 2.2.1 Если A>A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Для чего нужен" class="link_thumb">
16
16 Начало алгоритма. Шаг 1 Шаг 1 j:=2, Шаг 2 Шаг 2 Пока j=2 и f=0 выполнять: Шаг Шаг Если A>A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг Шаг i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Для чего нужен этот оператор?
A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Для чего нужен">
A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Для чего нужен этот оператор?">
A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Для чего нужен" title="16 Начало алгоритма. Шаг 1 Шаг 1 j:=2, Шаг 2 Шаг 2 Пока j=2 и f=0 выполнять: Шаг 2.2.1 Шаг 2.2.1 Если A>A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Для чего нужен">
title="16 Начало алгоритма. Шаг 1 Шаг 1 j:=2, Шаг 2 Шаг 2 Пока j=2 и f=0 выполнять: Шаг 2.2.1 Шаг 2.2.1 Если A>A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Для чего нужен">
18 Суть сортировки: Выбирается элемент с наименьшим значением и делается его обмен с первым элементом массива. Затем находится элемент с наименьшим значением из оставшихся n-1 элементов и делается его обмен со вторым элементом и т.д. до обмена двух последних элементов.
Сортировка выбором Отсортиро- ванная часть Отсортированная часть Массив отсортирован по возрастанию
20 Постановка задачи А N Пусть нужно отсортировать массив А по возрастанию, в котором N элементов методом выбора. Вспомогательные переменные j j – номер первого элемента остатка. i i – номер перемещаемого элемента. min min – минимальное число в массиве. Imin Imin – номер минимального числа в массиве
25 Суть сортировки: Последовательно просматривается массив и сравнивается каждая пара элементов между собой. При этом "неправильное" расположение элементов устраняется путем их перестановки. Процесс просмотра и сравнения элементов повторяется до просмотра всего массива.
26 Сортировка обменом
27 А N Пусть нужно отсортировать массив А по возрастанию, в котором N элементов методом обмена Вспомогательные переменные j j – номер первого элемента остатка. i i – номер перемещаемого элемента. Val Val – промежуточное значение, используемое для перемещения элементов массива Постановка задачи
2 выполнять: Шаг 2.1 Шаг 2.1 i:=1;, Шаг 2.2 Шаг 2.2 Пока iA то Val:=A[i]; A[i]:=A; A:=Val, Шаг 2.2.2 Шаг 2.2.2 i=i+1, Шаг 2.3 Шаг 2.3 j:=j-1. Конец алгоритма. Сравнение соседни" title="28 Начало алгоритма. Шаг 1 Шаг 1 j:=N, Шаг 2 Шаг 2 Пока j>=2 выполнять: Шаг 2.1 Шаг 2.1 i:=1;, Шаг 2.2 Шаг 2.2 Пока iA то Val:=A[i]; A[i]:=A; A:=Val, Шаг 2.2.2 Шаг 2.2.2 i=i+1, Шаг 2.3 Шаг 2.3 j:=j-1. Конец алгоритма. Сравнение соседни" class="link_thumb">
28
28 Начало алгоритма. Шаг 1 Шаг 1 j:=N, Шаг 2 Шаг 2 Пока j>=2 выполнять: Шаг 2.1 Шаг 2.1 i:=1;, Шаг 2.2 Шаг 2.2 Пока iA то Val:=A[i]; A[i]:=A; A:=Val, Шаг Шаг i=i+1, Шаг 2.3 Шаг 2.3 j:=j-1. Конец алгоритма. Сравнение соседних элементов Обмен соседних элементов местами, в случае если левый больше правого Формируется отсортированная часть
=2 выполнять: Шаг 2.1 Шаг 2.1 i:=1;, Шаг 2.2 Шаг 2.2 Пока iA то Val:=A[i]; A[i]:=A; A:=Val, Шаг 2.2.2 Шаг 2.2.2 i=i+1, Шаг 2.3 Шаг 2.3 j:=j-1. Конец алгоритма. Сравнение соседни">
=2 выполнять: Шаг 2.1 Шаг 2.1 i:=1;, Шаг 2.2 Шаг 2.2 Пока iA то Val:=A[i]; A[i]:=A; A:=Val, Шаг 2.2.2 Шаг 2.2.2 i=i+1, Шаг 2.3 Шаг 2.3 j:=j-1. Конец алгоритма. Сравнение соседних элементов Обмен соседних элементов местами, в случае если левый больше правого Формируется отсортированная часть">
=2 выполнять: Шаг 2.1 Шаг 2.1 i:=1;, Шаг 2.2 Шаг 2.2 Пока iA то Val:=A[i]; A[i]:=A; A:=Val, Шаг 2.2.2 Шаг 2.2.2 i=i+1, Шаг 2.3 Шаг 2.3 j:=j-1. Конец алгоритма. Сравнение соседни" title="28 Начало алгоритма. Шаг 1 Шаг 1 j:=N, Шаг 2 Шаг 2 Пока j>=2 выполнять: Шаг 2.1 Шаг 2.1 i:=1;, Шаг 2.2 Шаг 2.2 Пока iA то Val:=A[i]; A[i]:=A; A:=Val, Шаг 2.2.2 Шаг 2.2.2 i=i+1, Шаг 2.3 Шаг 2.3 j:=j-1. Конец алгоритма. Сравнение соседни">
title="28 Начало алгоритма. Шаг 1 Шаг 1 j:=N, Шаг 2 Шаг 2 Пока j>=2 выполнять: Шаг 2.1 Шаг 2.1 i:=1;, Шаг 2.2 Шаг 2.2 Пока iA то Val:=A[i]; A[i]:=A; A:=Val, Шаг 2.2.2 Шаг 2.2.2 i=i+1, Шаг 2.3 Шаг 2.3 j:=j-1. Конец алгоритма. Сравнение соседни">
2 выполнять: Шаг 2.1 Шаг 2.1 i:=1;, Шаг 2.2 Шаг 2.2 Пока iA то Val:=A[i]; A[i]:=A; A:=Val, Шаг 2.2.2 Шаг 2.2.2 i=i+1, Шаг 2.3 Шаг 2.3 j:=j-1. Конец алгоритма. Почему условие та" title="29 Начало алгоритма. Шаг 1 Шаг 1 j:=N, Шаг 2 Шаг 2 Пока j>=2 выполнять: Шаг 2.1 Шаг 2.1 i:=1;, Шаг 2.2 Шаг 2.2 Пока iA то Val:=A[i]; A[i]:=A; A:=Val, Шаг 2.2.2 Шаг 2.2.2 i=i+1, Шаг 2.3 Шаг 2.3 j:=j-1. Конец алгоритма. Почему условие та" class="link_thumb">
29
29 Начало алгоритма. Шаг 1 Шаг 1 j:=N, Шаг 2 Шаг 2 Пока j>=2 выполнять: Шаг 2.1 Шаг 2.1 i:=1;, Шаг 2.2 Шаг 2.2 Пока iA то Val:=A[i]; A[i]:=A; A:=Val, Шаг Шаг i=i+1, Шаг 2.3 Шаг 2.3 j:=j-1. Конец алгоритма. Почему условие такое?
=2 выполнять: Шаг 2.1 Шаг 2.1 i:=1;, Шаг 2.2 Шаг 2.2 Пока iA то Val:=A[i]; A[i]:=A; A:=Val, Шаг 2.2.2 Шаг 2.2.2 i=i+1, Шаг 2.3 Шаг 2.3 j:=j-1. Конец алгоритма. Почему условие та">
=2 выполнять: Шаг 2.1 Шаг 2.1 i:=1;, Шаг 2.2 Шаг 2.2 Пока iA то Val:=A[i]; A[i]:=A; A:=Val, Шаг 2.2.2 Шаг 2.2.2 i=i+1, Шаг 2.3 Шаг 2.3 j:=j-1. Конец алгоритма. Почему условие такое?">
=2 выполнять: Шаг 2.1 Шаг 2.1 i:=1;, Шаг 2.2 Шаг 2.2 Пока iA то Val:=A[i]; A[i]:=A; A:=Val, Шаг 2.2.2 Шаг 2.2.2 i=i+1, Шаг 2.3 Шаг 2.3 j:=j-1. Конец алгоритма. Почему условие та" title="29 Начало алгоритма. Шаг 1 Шаг 1 j:=N, Шаг 2 Шаг 2 Пока j>=2 выполнять: Шаг 2.1 Шаг 2.1 i:=1;, Шаг 2.2 Шаг 2.2 Пока iA то Val:=A[i]; A[i]:=A; A:=Val, Шаг 2.2.2 Шаг 2.2.2 i=i+1, Шаг 2.3 Шаг 2.3 j:=j-1. Конец алгоритма. Почему условие та">
title="29 Начало алгоритма. Шаг 1 Шаг 1 j:=N, Шаг 2 Шаг 2 Пока j>=2 выполнять: Шаг 2.1 Шаг 2.1 i:=1;, Шаг 2.2 Шаг 2.2 Пока iA то Val:=A[i]; A[i]:=A; A:=Val, Шаг 2.2.2 Шаг 2.2.2 i=i+1, Шаг 2.3 Шаг 2.3 j:=j-1. Конец алгоритма. Почему условие та">
2 выполнять: Шаг 2.1 Шаг 2.1 i:=1;, Шаг 2.2 Шаг 2.2 Пока iA то Val:=A[i]; A[i]:=A; A:=Val, Шаг 2.2.2 Шаг 2.2.2 i=i+1, Шаг 2.3 Шаг 2.3 j:=j-1. Конец алгоритма. Почему значение j" title="30 Начало алгоритма. Шаг 1 Шаг 1 j:=N, Шаг 2 Шаг 2 Пока j>=2 выполнять: Шаг 2.1 Шаг 2.1 i:=1;, Шаг 2.2 Шаг 2.2 Пока iA то Val:=A[i]; A[i]:=A; A:=Val, Шаг 2.2.2 Шаг 2.2.2 i=i+1, Шаг 2.3 Шаг 2.3 j:=j-1. Конец алгоритма. Почему значение j" class="link_thumb">
30
30 Начало алгоритма. Шаг 1 Шаг 1 j:=N, Шаг 2 Шаг 2 Пока j>=2 выполнять: Шаг 2.1 Шаг 2.1 i:=1;, Шаг 2.2 Шаг 2.2 Пока iA то Val:=A[i]; A[i]:=A; A:=Val, Шаг Шаг i=i+1, Шаг 2.3 Шаг 2.3 j:=j-1. Конец алгоритма. Почему значение j уменьшается? Можно ли увеличивать? Что нужно изменить?
=2 выполнять: Шаг 2.1 Шаг 2.1 i:=1;, Шаг 2.2 Шаг 2.2 Пока iA то Val:=A[i]; A[i]:=A; A:=Val, Шаг 2.2.2 Шаг 2.2.2 i=i+1, Шаг 2.3 Шаг 2.3 j:=j-1. Конец алгоритма. Почему значение j">
=2 выполнять: Шаг 2.1 Шаг 2.1 i:=1;, Шаг 2.2 Шаг 2.2 Пока iA то Val:=A[i]; A[i]:=A; A:=Val, Шаг 2.2.2 Шаг 2.2.2 i=i+1, Шаг 2.3 Шаг 2.3 j:=j-1. Конец алгоритма. Почему значение j уменьшается? Можно ли увеличивать? Что нужно изменить?">
=2 выполнять: Шаг 2.1 Шаг 2.1 i:=1;, Шаг 2.2 Шаг 2.2 Пока iA то Val:=A[i]; A[i]:=A; A:=Val, Шаг 2.2.2 Шаг 2.2.2 i=i+1, Шаг 2.3 Шаг 2.3 j:=j-1. Конец алгоритма. Почему значение j" title="30 Начало алгоритма. Шаг 1 Шаг 1 j:=N, Шаг 2 Шаг 2 Пока j>=2 выполнять: Шаг 2.1 Шаг 2.1 i:=1;, Шаг 2.2 Шаг 2.2 Пока iA то Val:=A[i]; A[i]:=A; A:=Val, Шаг 2.2.2 Шаг 2.2.2 i=i+1, Шаг 2.3 Шаг 2.3 j:=j-1. Конец алгоритма. Почему значение j">
title="30 Начало алгоритма. Шаг 1 Шаг 1 j:=N, Шаг 2 Шаг 2 Пока j>=2 выполнять: Шаг 2.1 Шаг 2.1 i:=1;, Шаг 2.2 Шаг 2.2 Пока iA то Val:=A[i]; A[i]:=A; A:=Val, Шаг 2.2.2 Шаг 2.2.2 i=i+1, Шаг 2.3 Шаг 2.3 j:=j-1. Конец алгоритма. Почему значение j">
35 12 Сортировка Шелла шаг. 4 группы из 2-х элементов шаг. 2 группы из 4-х элементов 36 Сортировка Шелла шаг. 1 группа из 8-ми элементов Массив отсортирован по возрастанию 37 А N Пусть нужно отсортировать массив А по возрастанию, в котором N элементов методом Шелла Вспомогательные переменные j j – номер первого элемента остатка. i i – номер перемещаемого элемента. M M- оптимальный шаг P P– промежуточное значение, используемое для перемещения элементов массива Постановка задачи
45 Суть сортировки: Выбирается некоторое значение (x)- барьерный элемент, который определяется округлением до целого деления количества сортируемых элементов на 2; Просматриваем массив, двигаясь слева направо, пока не найдется элемент, больший x Затем просматриваем его справа налево, пока не найдется элемент, меньший x
46 Суть сортировки: Меняем найденные элементы местами. В случае, если не найден наибольший или наименьший элементы, местами меняется средний элемент с найденным наибольшим или наименьшим элементом; Дойдя до середины имеем 2 части массива; Процесс продолжается для каждой части, пока массив не будет отсортирован
7 переносим в правую часть, т. к. 16>7 не переносим, 47 переносим в правую часть, т. к. 16>7, 8>7,11>7, 19>7 не переносим, 7=7 поэт" title="47 Быстрая сортировка 812371911416 Барьерный элемент 4378123 4 Барьерный элемент 8121119 Барьерный элемент 1219 1619 8>7 переносим в правую часть, т. к. 16>7 не переносим, 47 переносим в правую часть, т. к. 16>7, 8>7,11>7, 19>7 не переносим, 7=7 поэт" class="link_thumb">
47
47 Быстрая сортировка Барьерный элемент Барьерный элемент Барьерный элемент >7 переносим в правую часть, т. к. 16>7 не переносим, 47 переносим в правую часть, т. к. 16>7, 8>7,11>7, 19>7 не переносим, 7=7 поэтому меняем местами 7 и 12 4>3 Отсортиро- ванная часть 12>11 переносим в правую часть, т. к >11 не переносим, 811 переносим в правую часть, т. к. 16>11, 12>11,не переносим, 11 11=11 поэтому меняем местами 11 и 19 Отсортированная часть 19>12 переносим в правую часть, т. к. 16>12,не переносим, 12 12=12 поэтому меняем местами 12 и 19 19>16 Массив отсортирован по возрастанию Меньше равно 7 Больше 7
7 переносим в правую часть, т. к. 16>7 не переносим, 47 переносим в правую часть, т. к. 16>7, 8>7,11>7, 19>7 не переносим, 7=7 поэт">
7 переносим в правую часть, т. к. 16>7 не переносим, 47 переносим в правую часть, т. к. 16>7, 8>7,11>7, 19>7 не переносим, 7=7 поэтому меняем местами 7 и 12 4>3 Отсортиро- ванная часть 12>11 переносим в правую часть, т. к. 8 12 16>11 не переносим, 811 переносим в правую часть, т. к. 16>11, 12>11,не переносим, 11 11=11 поэтому меняем местами 11 и 19 Отсортированная часть 19>12 переносим в правую часть, т. к. 16>12,не переносим, 12 12=12 поэтому меняем местами 12 и 19 19>16 Массив отсортирован по возрастанию Меньше равно 7 Больше 7">
7 переносим в правую часть, т. к. 16>7 не переносим, 47 переносим в правую часть, т. к. 16>7, 8>7,11>7, 19>7 не переносим, 7=7 поэт" title="47 Быстрая сортировка 812371911416 Барьерный элемент 4378123 4 Барьерный элемент 8121119 Барьерный элемент 1219 1619 8>7 переносим в правую часть, т. к. 16>7 не переносим, 47 переносим в правую часть, т. к. 16>7, 8>7,11>7, 19>7 не переносим, 7=7 поэт">
title="47 Быстрая сортировка 812371911416 Барьерный элемент 4378123 4 Барьерный элемент 8121119 Барьерный элемент 1219 1619 8>7 переносим в правую часть, т. к. 16>7 не переносим, 47 переносим в правую часть, т. к. 16>7, 8>7,11>7, 19>7 не переносим, 7=7 поэт">
48 А n Пусть нужно отсортировать массив А по возрастанию, в котором n элементов быстрым методом Вспомогательные переменные: t – t –конечный элемент массива m - m - начальный элемент массива x – x – элемент относительно которого перемещаются все остальные элементы. w – w – промежуточное значение, используемое для перемещения элементов массива Постановка задачи
58 Устойчивость – отсортированный массив не меняет порядок элементов с одинаковыми значениями. Взаимное расположение равных элементов с ключом 1 и дополнительными полями "a", "b", "c" Параметры оценки алгоритмов
59 Естественность поведения - эффективность метода при обработке уже отсортированных, или частично отсортированных данных. Алгоритм ведет себя естественно, если учитывает эту характеристику входной последовательности и работает лучше Параметры оценки алгоритмов 60 Оценка алгоритма сортировки выбором Общее количество сравнений C =N-l + N = (N 2 -N)/2 Общее количество операций n + (n-1) + (n-2) + (n-3) = 1/2 * (n 2 +n) = Theta(n 2) Число обменов
63 Оценка алгоритма сортировки вставкой Для массива потребуется N-1 сравнение. Для массива потребуется (N 2 -N)/2 сравнение. Общее количество операций Theta(n 2)
66 Не эффективный метод, так как включение элемента связано со сдвигом всех предшествующих элементов на одну позицию, а эта операция неэкономна В совокупности устойчивость и естественность поведения алгоритма, делает метод хорошим выбором в соответствующих ситуациях
70 Сравнение методов простой сортировки N N – количество элементов, M M – кол-во пересылок, C – кол-во сравнений МинимумМаксимум Простые включения M=2(n-1) C = n-1 M=2(n-1) С=(n 2 -n)/2 М=(n+3n-4)/2 М=(n 2 +3n-4)/2 Простой обмен C=(n 2 -n)/2M=3(n-1) С=(n 2 -n)/2 М=n/4+3(n-1) М=n 2 /4+3(n-1) Простой выбор C=(n 2 -n)/2 M = 0 С=(n 2 -n)/2 М=(n-n)*1,5 М=(n 2 -n)*1,5 ? Чему будет равно количество пересылок
72 Оценка алгоритма Шелла n 1.2 Время выполнения пропорционально n 1.2, т. к. при каждом проходе используется небольшое число элементов или элементы массива уже находятся в относительном порядке, а упорядоченность увеличивается при каждом новом просмотре данных
73 Оценка алгоритма быстрой сортировки N=2g X N N/2N/2 Если размер массива равен числу, являющемуся степенью двойки (N=2g), и при каждом разделении элемент X находится точно в середине массива, тогда при первом просмотре выполняется N сравнений и массив разделится на две части размерами N/2. Для каждой из этих частей N/2 сравнений и т. д. Следовательно C=N+2*(N/2)+4*(N/4)+...+N*(N/N). N Если N не является степенью двойки, то оценка будет иметь тот же порядок
74 Theta(n). Общее количество операций Theta(n). log n O(n log n) Количество шагов деления (глубина рекурсии) составляет приблизительно log n, если массив делится на более-менее равные части. Таким образом, общее быстродействие: O(n log n) O(n 2) Если каждый раз в качестве центрального элемента выбирается максимум или минимум входной последовательности, тогда быстродействие O(n 2)
77 Контрольные вопросы? Что такое «сортировка»? ? В чем заключается метод сортировки отбором? ? В чем заключается метод сортировки вставками? ? В чем заключается метод пузырьковой сортировки? ? В чем заключается метод быстрой сортировки? ? В чем заключается метод сортировки Шелла?
78 Контрольные вопросы? Какой алгоритм сортировки считается самым простым? ? Какой алгоритм сортировки считается самым эффективным? ? Сколько существует групп алгоритмов сортировки? ? По каким признакам характеризуются алгоритмы сортировки? ? Что нужно учитывать при выборе алгоритма сортировки?
В данной статье рассматриваются алгоритмы сортировки массивов. Для начала представляются выбранные для тестирования алгоритмы с кратким описанием их работы, после чего производится непосредственно тестирование, результаты которого заносятся в таблицу и производятся окончательные выводы. Алгоритмы сортировок очень широко применяются в программировании, но иногда программисты даже не задумываются какой алгоритм работает лучше всех (под понятием «лучше всех» имеется ввиду сочетание быстродействия и сложности как написания, так и выполнения). В данной статье постараемся это выяснить. Для обеспечения наилучших результатов все представленные алгоритмы будут сортировать целочисленный массив из 200 элементов. Компьютер, на котором будет проводится тестирование имеет следующие характеристики: процессор AMD A6-3400M 4x1.4 GHz, оперативная память 8 GB, операционная система Windows 10 x64 build 10586.36. Selection sort (сортировка выбором)
– суть алгоритма заключается в проходе по массиву от начала до конца в поиске минимального элемента массива и перемещении его в начало. Сложность такого алгоритма O(n2). Bubble sort (сортировка пузырьком)
– данный алгоритм меняет местами два соседних элемента, если первый элемент массива больше второго. Так происходит до тех пор, пока алгоритм не обменяет местами все неотсортированные элементы. Сложность данного алгоритма сортировки равна O(n^2). Insertion sort (сортировка вставками)
– алгоритм сортирует массив по мере прохождения по его элементам. На каждой итерации берется элемент и сравнивается с каждым элементом в уже отсортированной части массива, таким образом находя «свое место», после чего элемент вставляется на свою позицию. Так происходит до тех пор, пока алгоритм не пройдет по всему массиву. На выходе получим отсортированный массив. Сложность данного алгоритма равна O(n^2). Quick sort (быстрая сортировка)
– суть алгоритма заключается в разделении массива на два под-массива, средней линией считается элемент, который находится в самом центре массива. В ходе работы алгоритма элементы, меньшие чем средний будут перемещены в лево, а большие в право. Такое же действие будет происходить рекурсивно и с под-массива, они будут разделяться на еще два под-массива до тех пор, пока не будет чего разделать (останется один элемент). На выходе получим отсортированный массив. Сложность алгоритма зависит от входных данных и в лучшем случае будет равняться O(n×2log2n). В худшем случае O(n^2). Существует также среднее значение, это O(n×log2n). Comb sort (сортировка расческой)
– идея работы алгоритма крайне похожа на сортировку обменом, но главным отличием является то, что сравниваются не два соседних элемента, а элементы на промежутке, к примеру, в пять элементов. Это обеспечивает от избавления мелких значений в конце, что способствует ускорению сортировки в крупных массивах. Первая итерация совершается с шагом, рассчитанным по формуле (размер массива)/(фактор уменьшения), где фактор уменьшения равен приблизительно 1,247330950103979, или округлено до 1,3. Вторая и последующие итерации будут проходить с шагом (текущий шаг)/(фактор уменьшения) и будут происходить до тех пор, пока шаг не будет равен единице. Практически в любом случае сложность алгоритма равняется O(n×log2n). Для проведения тестирования будет произведено по 5 запусков каждого алгоритма и выбрано наилучшее время. Наилучшее время и используемая при этом память будут занесены в таблицу. Также будет проведено тестирование скорости сортировки массива размером в 10, 50, 200 и 1000 элементов чтобы определить для каких задач предназначен конкретный алгоритм. Полностью неотсортированный массив: Частично отсортированный массив (половина элементов упорядочена): Результаты, предоставленые в графиках: В результате проведенного исследования и полученных данных, для сортировки неотсортированного массива, наиболее оптимальным из представленных алгоритмов для сортировки массива является быстрая сортировка. Несмотря на более длительное время выполнения алгоритм потребляет меньше памяти, что может быть важным в крупных проектах. Однако такие алгоритмы как сортировка выбором, обменом и вставками могут лучше подойти для научных целей, например, в обучении, где не нужно обрабатывать огромное количество данных. При частично отсортированном массиве результаты не сильно отличаются, все алгоритмы сортировки показывают время примерно на 2-3 миллисекунды меньше. Однако при сортировке частично отсортированного массива быстрая сортировка срабатывает намного быстрее и потребляет меньшее количество памяти. Если вы программируете и ваш код уходит дальше написания калькулятора, ты вы не раз столкнётесь или сталкивались с необходимостью отсортировать тот или иной массив данных. Существует множество способов сортировки. В этой статье мы разберём основные из них и сделаем акцент на быстрой сортировке. Быстрая сортировка - Quick Sort или qsort. По названию становится понятно, что это и для чего. Но если не понятно, то это алгоритм по быстрой сортировке массива, алгоритм имеет эффективность O(n log n) в среднем. Что это значит? Это значит, что среднее время работы алгоритма повышается по той же траектории, что и график данной функции. В некоторых популярных языках имеются встроенные библиотеки с этим алгоритмом, а это уже говорит о том, что он крайне эффективен. Это такие языки, как Java, C++, C#. Метод быстрой сортировки использует рекурсию и стратегию "Разделяй и властвуй". 1. В массиве ищется некий опорный элемент, для простоты лучше взять центральный, но если вы хотите поработать над оптимизацией, то придётся попробовать разные варианты. 2. Слева от опоры ищется элемент больший, чем опорный, справа - меньший, чем опорный, затем меняем их местами. Делаем это, пока максимальный справа не будет меньше, чем минимальный слева. Таким образом, все маленькие элементы кидаем в начало, большие - в конец. 3. Рекурсивно применяем данный алгоритм к левой и правой части нашего алгоритма отдельно, затем ещё и ещё, до достижения одного элемента или определённого количества элементов. Что же это за количество элементов? Есть ещё один способ оптимизировать данный алгоритм. Когда сортируемая часть становится примерно равной 8 или 16, то можно обработать её обычной сортировкой, например пузырьковой. Так мы повысим эффективность нашего алгоритма, т.к. маленькие массивы он обрабатывает не так быстро, как хотелось бы. Таким образом, будет обработан и отсортирован весь массив. А теперь наглядно изучим данный алгоритм Является ли быстрая сортировка самым быстрым алгоритмом сортировки? Однозначно нет. Сейчас появляется всё больше и больше сортировок, на данный момент самая быстрая сортировка - это Timsort, она работает крайне быстро для массивов, изначально отсортированных по-разному. Но не стоит забывать, что метод быстрой сортировки является одним из самых простых в написании, это очень важно, ведь, как правило, для рядового проекта нужно именно простое написание, а не громадный алгоритм, который сам ты и не напишешь. Timsort - тоже не самый сложный алгоритм, но звание самого простого ему точно не светит. Ну вот мы и дошли до самого "вкусного". Теперь разберём, как реализовывается данный алгоритм. Как говорилось ранее, он не слишком сложен в реализации, скорее, даже прост. Но мы всё равно полностью разберём каждое действие нашего кода, чтобы вы поняли, как работает быстрая сортировка. Наш метод называется quickSort. В нём запускается основной алгоритм, в который мы передаём массив, первый и последний его элементы. Запоминаем в переменные i и k первый и последний элемент сортируемого отрезка, чтобы не изменять эти переменные, так как они нам нужны. Затем проверяем расстояние между первым и последним проверяемым: оно больше или равно единице? Если нет, значит, мы пришли к центру и нужно выйти из сортировки этого отрезка, а если да, то продолжаем сортировку. Затем за опорный элемент берём первый элемент в сортируемом отрезке. Следующий цикл делаем до того момента, пока не дойдём до центра. В нём делаем ещё два цикла: первый - для левой части, а второй - для правой. Их мы выполняем, пока есть элементы, подходящие под условие, или пока не дойдём до опорного элемента. Затем, если минимальный элемент всё же справа, а максимальный - слева, меняем их местами. Когда цикл заканчивается, меняем первый элемент и опорный, если опорный меньше. Затем мы рекурсивно делаем наш алгоритм для правого и левого участка массива и так продолжаем, пока не дойдём до отрезка длиной в 1 элемент. Тогда все наши рекурсивные алгоритмы будут return, и мы полностью выйдем из сортировки. Также внизу имеется метод swap - вполне стандартный метод при сортировке массива заменами. Чтобы несколько раз не писать замену элементов, пишем один раз и меняем элементы в данном массиве. В заключение можно сказать, что по соотношению "качество-сложность" быстрая сортировка находится на лидирующей позиции среди всех алгоритмов, поэтому вам стоит однозначно взять метод на заметку и использовать при необходимости в своих проектах.
1. Находим минимальный элемент в массиве.
2. Меняем местами минимальный и первый элемент местами.
3. Опять ищем минимальный элемент в неотсортированной части массива
4. Меняем местами уже второй элемент массива и минимальный найденный, потому как первый элемент массива является отсортированной частью.
5. Ищем минимальные значения и меняем местами элементы,пока массив не будет отсортирован до конца.
1. Каждый элемент массива сравнивается с последующим и если элемент[i] > элемент происходит замена. Таким образом самые "легкие" элементы "всплывают" - перемещаются к началу списка,а самые тяжелые "тонут" - перемещаются к концу.
2. Повторяем Шаг 1 n-1 раз, где n - Массив.Количество ().
Дик Грун
Элементарный пример: При игре в дурака, вы тянете из колоды карту и вставляете ее в соответствующее место по возрастанию в имеющихся у вас картах. Или
в магазине вам дали сдачу 550 рублей- одна купюра 500, другая 50. Заглядываете в кошелек, а там купюры достоинством 10,100,1000. Вы вставляете купюру
достоинсвом 50р. между купюрами достоинством 10р и 100р, а купюру в 500 рублей между купюрами 100р и 1000р. Получается 10,50,100,500,1000 - Вот вам
и алгоритм "Сортировка вставками".
Таким образом с каждым шагом алгоритма, вам необходимо отсортировать подмассив данных и вставить значение в нужное место.
//Сортировка вставками {---
Функция СортировкаВставками(Знач Массив)
Для i = 0 По Массив.ВГраница()-1 Цикл
Ключ = i + 1;
Замена = Массив[Ключ];
j = i + 1;
Пока j > 0 И Замена < Массив Цикл
Массив[j] = Массив;
Замена = j - 1;
Ключ = j - 1;
j = j - 1;
КонецЦикла;
Массив[Ключ] = Замена;
КонецЦикла;
Возврат Массив;
КонецФункции
//---}
Для первой итерации Шаг = Цел(Массив.Количество()/2), для последующих Шаг = Цел(Шаг/2). Т.е. постепенно шаг сокращается и когда Шаг будет равен 1 произойдет последние сравнение и массив будет отсортирован.
Дан массив (10,5,3,1,14,2,7,12).
1. Шаг = 4.
Сортируем простыми вставками каждые 4 группы по 2 элемента (10,14)(5,2)(3,7)(1,12)
Сортируем простыми вставками каждые 2 группы по 4 элемента (10,3,14,7)(2,1,5,12)
Сортируем простыми вставками каждую 1 группу по 8 элементов.
//Сортировка Шелла {---
Функция СортировкаШелла(Знач Массив)
Шаг = Цел(Массив.Количество()/2);
Пока Шаг > 0 Цикл
i = 0;
Пока i < (Массив.Количество() - Шаг) Цикл
j = i;
Пока j >= 0 И Массив[j] > Массив Цикл
Замена = Массив[j];
Массив[j] = Массив;
Массив = Замена;
j = j - 1;
Если ПрименитьОтображениеСортировки Тогда
ОтобразитьДиаграммуСортировки(Массив);
КонецЕсли;
КонецЦикла;
i = i + 1;
КонецЦикла;
Шаг = Цел(Шаг/2);
ОбработкаПрерыванияПользователя();
КонецЦикла;
Возврат Массив;
КонецФункции
//---}
Вся суть алгоритма сводится к тому, чтобы разбить сложную задачу на маленькие и решить их по отдельности. Выбирается некая опорная точка и все значения которые меньше перебрасываются влево, все остальные вправо. Далее для каждой полученной части выполняетя тоже самое, до тех пор пока дробить части уже нельзя. В конце мы получаем множество отсортированных частей, которые необходимо просто склеить в 1 целое.
-Для создания другого массива необходимо нажать на кнопку "Создание ГСЧ массива ", также можно выбирать необходимый диапазон.
-Для включения динамической анимации необходимо поставить галочку на "Отобразить сортировку в диаграмме". Советую на неэффективных алгоритмах устанавливать галочку при размерности массива до 100 элементов, иначе состаритесь ждать сортировки:)
Для проведения исследования были выбраны следующие алгоритмы сортировки:
Понятие быстрой сортировки
Алгоритм
Эффективность быстрой сортировки
Реализация алгоритма
