WRITELN("Результат:");
FOR I:=1 TO N DO WRITE(A[I]," ")
Такой типичный случай повторяющегося процесса с двумя условиями
окончания позволяет нам воспользоваться хорошо известным приемом
“барьера” (sentinel).
Анализ метода прямого включения. Число сравнений ключей (Ci) при i- м просеивании самое большее равно i-1, самое меньшее – 1; если предположить, что все перестановки из n ключей равновероятны, то среднее число сравнений – I/2. Число же пересылок Mi равно Ci + 2 (включая барьер). Поэтому общее число сравнений и число пересылок таковы:
Cmin = n-1 (2.1.) Mmin = 3*(n-1) (2.4.)
Cave = (n2+n-2)/4 (2.2.) Mave = (n2+9*n-10)/4 (2.5.)
Cmax = (n2+n-4)/4 (2.3.) Mmax = (n2+3*n-4)/2 (2.6.)
Алгоритм с прямыми включениями можно легко улучшить, если обратить внимание на то, что готовая последовательность, в которую надо вставить новый элемент, сама уже упорядочена. Естественно остановиться на двоичном поиске, при котором делается попытка сравнения с серединой готовой последовательности, а затем процесс деления пополам идет до тех пор, пока не будет найдена точка включения. Такой модифицированный алгоритм сортировки называется методом с двоичным включением (binaryinsertion).
ПРОГРАММА 2.2. СОРТИРОВКА МЕТОДОМ ДЕЛЕНИЯ ПОПОЛАМ.
I,J,M,L,R,X,N:INTEGER;
A:ARRAY OF INTEGER;
WRITELN("Введи длину массива");
WRITELN("Введи массив");
FOR I:=1 TO N DO READ(A[I]);
FOR I:=2 TO N DO
X:=A[I];L:=1;R:=I;
IF A[M]<=X THEN L:=M+1 ELSE R:=M
На днях в комментариях вконтакте у меня возник спор с одним из других студентов проекта. Суть спора заключалась в том, «кто кого» - метод sort() из класса java.util.Arrays или самописные реализации простых алгоритмов: bubble
(пузырьковая), insertion
(вставками), selection
(выбором), shell
(алгоритм Шелла).
Для некоторых ответ на данный вопрос может быть очевиден, но раз спор возник, при том что у каждой из сторон были «уважаемые источники» в пользу своей точки зрения, было принято решение провести исследование, поразмяв в процессе серое вещество, реализуя различные алгоритмы.
TL;DR:
java.util.Arrays.sort() безоговорочно лидирует на массивах от 100 000 элементов, при меньшем размере с ним иногда может потягаться метод Шелла. Остальные рассмотренные алгоритмы сливают вчистую и могут быть полезны лишь при каких-то экзотических условиях.
Теперь давайте рассмотрим, как же осуществляется сортировка массивов в наших убер-девайсах из кремния.
Selection sort. Сортировка выбором
Начнем с самого простого и очевидного способа. Суть его нам отлично демонстрирует Роберт Седжвик в своей видеолекции на coursera (привожу погано пережатую в gif мной анимацию оттуда):
Пробегая по массиву с первого элемента, мы на каждом шаге ищем в правой части минимальный элемент, с которым и меняем местами текущий. В результате мы оставляем за собой окончательный вариант нашего массива в отсортированном виде.
Вот код, реализующий этот алгоритм на Java:
public
void
sort
(int
array)
{
int
n =
array.
length;
for
(int
i =
0
;
i <
n;
i ++
)
{
int
minIndex =
min
(array,
i,
n -
1
)
;
swap
(array,
i,
minIndex)
;
}
}
public
static
void
swap
(int
array,
int
i,
int
j)
{
int
temp =
array[
i]
;
array[
i]
=
array[
j]
;
array[
j]
=
temp;
}
public
static
int
min
(int
array,
int
begin,
int
end)
{
int
minVal =
array[
begin]
;
int
minIndex =
begin;
for
(int
i =
begin +
1
;
i <=
end;
i++
)
{
if
(array[
i]
<
minVal)
{
minVal =
array[
i]
;
minIndex =
i;
}
}
return
minIndex;
}
Анализ алгоритма показывает, что необходимо на каждом проходе прошерстить весть остаток массива, то есть нам понадобится ровно N + (N-1) + (N-2) + … + 1 = N^2/2 сравнений. Таким образом, сложность алгоритма составляет O(N^2). Что же это означает? А означает это, что, увеличив количество элементов в массиве (N) в 2 раза, мы увеличим время работы алгоритма не в 2, а в 2^2 = 4 раза. Увеличив N в 10 раз, время работы увеличим в 100 раз и так далее. На моем ноутбуке 2012 года с процессором Core i3 под Ubuntu 14.4 я получил следующее время работы:
Insertion sort. Сортировка вставками
Здесь идея несколько иная. Опять же, обратимся к анимации от Доктора Седжвика:
То, что впереди, нами еще даже не просмотрено, а все что оставляем позади себя, всегда остается выстроенным по порядку. Суть в том, что каждый новый элемент исходного массива мы «возвращаем» к началу до тех пор, пока он не «упрется» в меньший элемент.
Таким образом, у нас опять N проходов (для каждого элемента исходного массива), но в каждом проходе в большинстве случаев мы просматриваем не весь остаток, а только часть. То есть вариант 1 + (N-1) + (N-2) + … + N = N^2/2 мы получим, только если каждый следующий элемент нам придется возвращать к самому началу, то есть в случае отсортированного «наоборот» входного массива (не везет, так невезет). В случае же уже отсортированного массива (вот везуха ваще) будет полная халява – на каждом проходе всего одно сравнение и оставление элемента на месте, то есть отработает алгоритм за время, пропорциональное N. Сложность алгоритма же будет определяться худшим теоретическим случаем, то есть O(N^2). Среднестатистически же, время работы будет пропорционально N^2/4, то есть, вдвое быстрее предыдущего алгоритма. В моей реализации из-за неоптимального использования перестановки время работы получилось больше, чем у Selection. Планирую в ближайшее время исправить и обновить пост.
Вот код и результат его работы на той же машине:
public
void
sort
(int
array)
{
int
length =
array.
length;
for
(int
i =
1
;
i <
length;
i++
)
{
for
(int
j =
i;
j >=
1
;
j--
)
{
if
(array[
j]
<
array[
j -
1
]
)
swap
(array,
j,
j -
1
)
;
else
break
;
}
}
}
Shell sort. Сортировка Шелла
Умный мужик Дональд Шелл аж в 1959-м году заметил, что в алгоритме вставками дороже всего обходятся случаи, когда элемент возвращается очень далеко к началу массива: на каком-то проходе мы вернем элемент к началу на пару позиций, а на другом проходе почти через весь массив к началу – далеко и долго. Нельзя ли это сделать сразу, прыгая через несколько элементов? И такой способ он нашел. Заключается он в последовательном выполнении особых частичных сортировок, называемых в общем виде d-sort или, у Седжвика, h-sort (подозреваю, h означает hop - прыжок).
3-sort, например, будет сравнивать рассматриваемый элемент не с предыдущим, а пропустит два и сравнит с отстоящим на 3 позиции назад. Если поменяли, он его сравнит снова с элементом на 3 позиции назад и так далее.
Суть в том, что полученный в результате массив будет «3-отсортирован», то есть неправильность положения элементов составит менее 3х позиций. Работать с таким алгоритму вставки будет легко и приятно. Кстати, «1-sort» является ничем иным, как просто алгоритмом вставки=)
Последовательно применяя к массиву h-sort с уменьшающимся значением h, мы сможем отсортировать большой массив быстрее. Вот как это выглядит:
Сложность здесь заключается в том, как выбрать правильную последовательность частичных сортировок. От этого, в итоге, зависит производительность алгоритма. Наиболее распространенной является последовательность, предложенная Дональдом Кнутом:
h = h*3 + 1, то есть 1, 4, 13, 40, … и так до 1/3 размера массива. Такая последовательность обеспечивает достойную производительность, а также проста в реализации.
Анализ алгоритма требует тонн матана и мной не осилен. Обширность анализа так же определяется множеством вариантов последовательностей h. Эмпирически же можно сказать, что скорость алгоритма весьма хороша – смотрите сами:
Миллион элементов менее, чем за секунду!
А вот код на Java с кнутовской последовательностью.
public
void
sort
(int
array)
{
int
h =
1
;
while
(h*
3
<
array.
length)
h =
h *
3
+
1
;
while
(h >=
1
)
{
hSort
(array,
h)
;
h =
h/
3
;
}
}
private
void
hSort
(int
array,
int
h)
{
int
length =
array.
length;
for
(int
i =
h;
i <
length;
i++
)
{
for
(int
j =
i;
j >=
h;
j =
j -
h)
{
if
(array[
j]
<
array[
j -
h]
)
swap
(array,
j,
j -
h)
;
else
break
;
}
}
}
Bubble sort. Метод пузырька
Это классика! Этот алгоритм реализует почти каждый начинающий программист. Это настолько классика, что у Доктора Седжвика даже не нашлось анимации для него, потому мне пришлось потрудиться самому.
Здесь на каждом проходе мы обходим массив с начала до конца, меняя местами соседние элементы, стоящие не по порядку. В результате самые крупные элементы «всплывают» (отсюда и название) в конец массива. Каждый новый проход мы начинаем, оптимистично надеясь, что массив уже отсортирован (sorted = true). В конце прохода, если мы видим, что ошиблись, начинаем новый проход.
Сложность здесь заключается в том, что мы, опять же, обходим весь (почти) массив на каждом проходе. Сравнение происходит на каждом шаге, обмен - почти на каждом, что делает данный алгоритм одним из самых медленных (если рассматривать рационально реализованные, а не "сортировку встряхиванием" и прочие подобные).
Интересно, что формально сложность и здесь будет равна O(N^2), только вот коэффициент гораздо выше, чем у вставок и выборов. Код алгоритма:
public
void
sort
(int
array)
{
boolean
isSorted;
int
nMinusOne =
array.
length -
1
;
for
(int
i =
0
;
i <
nMinusOne;
i++
)
{
isSorted =
true
;
for
(int
j =
0
;
j <
nMinusOne -
i;
j++
)
{
if
(array[
j]
>
array[
j +
1
]
)
{
swap
(array,
j,
j +
1
)
;
isSorted =
false
;
}
}
if
(isSorted)
return
;
}
}
Время работы:
Почувствуйте разницу: более получаса на миллионе элементов!
Вывод: Никогда не исползуйте этот алгоритм!!!
Резюме первой части
Как итог предлагаю посмотреть общую таблицу для этих алгоритмов.
Можете так же сравнить с результатами для встроенного метода java.util.Arrays.sort() . Похоже на какую-то магию - что же может быть быстрее Шелла? Об этом напишу в следующей части. Там мы рассмотрим широко применяемые алгоритмы быстрой сортировки, а также сортировки слиянием, узнаем о разнице в методах сортировки массивов из примитивов и ссылочных типов, а также познакомимся с очень важным в этом деле интерфейсом Comparable ;)
Ниже можете изучить график, построенный в логарифмическом масштабе по данным таблицы. Чем более полого идет линия, тем лучше алгоритм =)
Кто хочет скачать весь проект и прогнать тесты у себя, держите ссылку:
Java
До встречи в следующей части! =)
В данной статье рассматриваются алгоритмы сортировки массивов. Для начала представляются выбранные для тестирования алгоритмы с кратким описанием их работы, после чего производится непосредственно тестирование, результаты которого заносятся в таблицу и производятся окончательные выводы.
Алгоритмы сортировок очень широко применяются в программировании, но иногда программисты даже не задумываются какой алгоритм работает лучше всех (под понятием «лучше всех» имеется ввиду сочетание быстродействия и сложности как написания, так и выполнения).
В данной статье постараемся это выяснить. Для обеспечения наилучших результатов все представленные алгоритмы будут сортировать целочисленный массив из 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 миллисекунды меньше. Однако при сортировке частично отсортированного массива быстрая сортировка срабатывает намного быстрее и потребляет меньшее количество памяти.
Существует три общих метода сортировки массивов:
- Обмен
- Выбор (выборка)
- Вставка
Чтобы понять, как работают эти методы, представьте себе колоду игральных карт. Чтобы отсортировать карты методом обмена
, разложите их на столе лицом вверх и меняйте местами карты, расположенные не по порядку, пока вся колода не будет упорядочена.
В методе выбора
разложите карты на столе, выберите карту наименьшей значимости и положите ее в руку. Затем из оставшихся карт снова выберите карту наименьшей значимости и положите ее на ту, которая уже находится у вас в руке. Процесс повторяется до тех пор, пока в руке не окажутся все карты; по окончании процесса колода будет отсортирована.
Чтобы отсортировать колоду методом вставки
, возьмите все карты в руку. Выкладывайте их по одной на стол, вставляя каждую следующую карту в соответствующую позицию. Когда все карты окажутся на столе, колода будет отсортирована.
Сортировка вставками
Сортировка вставками
- простой алгоритм сортировки. Хотя этот алгоритм уступает в эффективности более сложным (таким как быстрая сортировка), у него есть ряд преимуществ:
· эффективен на небольших наборах данных, на наборах данных до десятков элементов может оказаться лучшим;
· эффективен на наборах данных, которые уже частично отсортированы;
· это устойчивый алгоритм сортировки (не меняет порядок элементов, которые уже отсортированы);
· может сортировать список по мере его получения;
Минусом -высокая сложность алгоритма: O(n
²)
Вообще говоря, в худших случаях сортировка вставками настолько же плоха, как и пузырьковая сортировка и сортировка посредством выбора, а в среднем она лишь немного лучше.
Описание
На каждом шаге алгоритма мы выбираем один из элементов входных данных и вставляем его на нужную позицию в уже отсортированном списке, до тех пор, пока набор входных данных не будет исчерпан. Метод выбора очередного элемента из исходного массива произволен; может использоваться практически любой алгоритм выбора. Обычно (и с целью получения устойчивого алгоритма сортировки), элементы вставляются по порядку их появления во входном массиве.
Анализ Алгоритма
Время выполнения алгоритма зависит от входных данных: чем большее множество нужно отсортировать, тем большее время выполняется сортировка. Также на время выполнения влияет исходная упорядоченность массива. Так, лучшим случаем является отсортированный массив, а худшим - массив, отсортированный в порядке, обратном нужному. Временная сложность алгоритма при худшем варианте входных данных - θ(n²).
Реализация на java
public void
addingSort() {
for
(Node cur = first.next; cur != null
; cur = cur.next) {
Node n = cur.prev;
Object val = cur.value;
for
(; n != null
; n = n.prev) {
if
(((Comparable) n.value).compareTo(val)
> 0) {
n.next.value = n.value;
} else
{
if
(n != null
) {
n.next.value = val;
} else
{
first.value = val;
Сначала он сортирует два первых элемента. Затем алгоритм вставляет третий элемент в соответствующую порядку позицию по отношению к первым двум элементам. После этого он вставляет четвертый элемент в список из трех элементов. Этот процесс повторяется до тех пор, пока не будут вставлены все элементы. Например
, при сортировке массива dcab
каждый проход алгоритма будет выглядеть следующим образом:
Начало d c a b
Проход 1 c d a b
Проход 2 a c d b
Проход 3 a b c d
Сортировка выбором
Описание
При сортировке из массива выбирается элемент с наименьшим значением и обменивается с первым элементом. Затем из оставшихся n
- 1 элементов снова выбирается элемент с наименьшим ключом и обменивается со вторым элементом, и т.д. Эти обмены продолжаются до двух последних элементов. Например
, если применить метод выбора к массиву dcab
, каждый проход будет выглядеть так:
Начало d c a bПроход 1 a c d bПроход 2 a b d cПроход 3 a b c d
Анализ
К сожалению, как и в пузырьковой сортировке, внешний цикл выполняется n
- 1 раз, а внутренний - в среднем n
/2 раз. Следовательно, сортировка посредством выбора требует 1/2(n
2 -n
)
сравнений. Таким образом, это алгоритм порядка n
2 , из-за чего он считается слишком медленным для сортировки большого количества элементов. Несмотря на то, что количество сравнений в пузырьковой сортировке и сортировке посредством выбора одинаковое, в последней количество обменов в среднем случае намного меньше, чем в пузырьковой сортировке.
Реализация на java
public void
SelectSort() {
for
(Node a = first; a != last; a = a.next) {
Node min = last;
for
(Node b = a; b != last; b = b.next) {
if
(((Comparable) b.val).compareTo(min.val)
< 0) {
a.val = min.val;
Сортировка Обменом
Самый известный алгоритм - пузырьковая сортировка
. Его популярность объясняется интересным названием и простотой самого алгоритма. Тем не менее, в общем случае это один из самых худших алгоритмов сортировки.
Пузырьковая сортировка относится к классу обменных сортировок, т.е. к классу сортировок методом обмена. Ее алгоритм содержит повторяющиеся сравнения (т.е. многократные сравнения одних и тех же элементов) и, при необходимости, обмен соседних элементов. Элементы ведут себя подобно пузырькам воздуха в воде - каждый из них поднимается на свой уровень.
Чтобы наглядно показать, как работает пузырьковая сортировка, допустим, что исходный массив содержит элементы dcab
. Ниже показано состояние массива после каждого прохода:
Начало d c a b
Проход 1 a d c b
Проход 2 a b d c
Проход 3 a b c d
При анализе любого алгоритма сортировки полезно знать, сколько операций сравнения и обмена будет выполнено в лучшем, среднем и худшем случаях. Поскольку характеристики выполняемого кода зависят от таких факторов, как оптимизация, производимая компилятором, различия между процессорами и особенности реализации, мы не будем пытаться получить точные значения этих параметров. Вместо этого сконцентрируем свое внимание на общей эффективности каждого алгоритма.
В пузырьковой сортировке количество сравнений всегда одно и то же, поскольку два цикла for повторяются указанное количество раз независимо от того, был список изначально упорядочен или нет. Это значит, что алгоритм пузырьковой сортировки всегда выполняет
(n
2 -n
)/2
сравнений, где n
- количество сортируемых элементов. Данная формула выведена на том основании, что внешний цикл выполняется n
- 1 раз, а внутренний выполняется в среднем n
/2 раз. Произведение этих величин и дает предыдущее выражение.
Обратите внимание на член n
2 в формуле. Говорят, что пузырьковая сортировка является алгоритмом порядка n
2 , поскольку время ее выполнения пропорционально квадрату количества сортируемых элементов. Необходимо признать, что алгоритм порядка n
2 не эффективен при большом количестве элементов, поскольку время выполнения растет экспоненциально в зависимости от количества сортируемых элементов.
В алгоритме пузырьковой сортировки количество обменов в лучшем случае равно нулю, если массив уже отсортирован. Однако в среднем и худшем случаях количество обменов также является величиной порядка n
2 .
Похожая информация.
МЕТОДЫ СОРТИРОВКИ
При разработке программного обеспечения очень распространенной операцией является сортировка значений, т.е. расположение списка элементов в некотором порядке (например, слова по алфавиту или числа в возрастающем или убывающем порядке).
Существует множество алгоритмов сортировки элементов. Наиболее простой из них - метод «пузырька». Алгоритм реализуется в виде двух вложенных циклов. Во внутреннем цикле просматриваются по порядку все элементы массива, попарно сравниваются рядом стоящие элементы, и если второй больше первого (при сортировке по убыванию) элементы меняются местами. Параметром внутреннего цикла является индекс(номер) элемента массива. Для полной сортировки такая перестановка должна быть выполнена n-1 раз, где n - количество элементов в массиве. Для этого организуется внешний цикл, параметром которого является шаг сортировки.
Пример. Отсортировать элементы одномерного массива целых чисел по возрастанию.
На рисунке 1 приведена последовательность перестановки элементов.
Рисунок 1. Сортировка методом «пузырька»
Хотя в предложенном примере сортировка выполнилась за четыре шага, проверка элементов будет продолжаться еще две итерации, т.к. полное число итераций на единицу меньше размерности массива.
На рисунке 2 приведена блок-схема рассмотренного алгоритма.
Рисунок 2. Блок-схема алгоритма сортировки методом «пузырька»
Переменная m введена для возможности обмена значениями между двумя переменными, k отвечает за шаги сортировки.
Программа на языке С++ по данному алгоритму будет выглядеть следующим образом.
Рисунок 3. Программа сортировки элементов массива методом «пузырька»
Сортировка пузырьковым методом является неэффективным методом, вследствие большого числа сравнений.
Более эффективным является метод прямого выбора
На первом шаге последовательно происходит просмотр всего списка значений и выбор из него минимального или максимального (в зависимости от порядка сортировки), далее расположение его в первой позиции обменом с элементом, стоявшим там ранее.
Затем эта процедура повторяется, но поиск минимального (максимального) значения происходит уже со второй позиции и т.д. Схема этого алгоритм представлена на рисунке 4.
сортировка значение программный обеспечение
Рисунок 4. Сортировка методом прямого выбора
Фрагмент программы, с помощью которого реализуется сортировка методом прямого выбора, приведен ниже.
// сортируем элементы массива по возрастанию
int temp;//переменная для временного хранения при обмене значениями
int i;//переменная управления циклом (номер элемента массива)
int k;//переменная управления циклом (номер шага сортировки)
int nmin;//номер минимального значения
for (к=0; i < к 1; i++)
// ищем номер минимального элемента среди значений list [ i … n -1]
for (i = k+1; i< n; i++)
if (list[i] < list[ nmin ]) nmin = i;
//меняем местами list[ nmin ] и list[ k ]
temp = list[ nmin ];
list[ nmin ]= list[ k ];
list[ k ] = temp;
Следует отметить, что поиск минимального значения во внутреннем цикле происходит в оставшейся части списка.
Чтобы произвести сортировку по убыванию, нужно на каждом шаге вместо минимального значения находить максимальное значение.
