Главная
>>
Каталог задач
>>
Сортировка
>>
Сортировка Выбором (selection sort)
>>
Сортировка выбором, общий подход
Aвтор:
this
Дата:
04.09.2002
Просмотров: 74632
реализации(C++: 2шт...)
+добавить
Имеется исходная неотсортированния последовательность x[0..n-1]. Отсортируем ее по возрастанию. Выбираем из нее наименьший элемент и ставим на первое место. Т.е. меняем местами найденный наименьший элемент и первый. Затем в последовательности начиная со 2-го элемента и до конца - аналогично ищем наименьший элемент и меняем его местами со 2-ым. И так далее до предпоследнего элемента. Сортировка заканчивается, когда в оставшейся неотсортированной последовательности остается 1 элемент.
Таким образом, алгоритм имеет n-1 итераций. И на каждой i(=[0..n-1])-ой итерации из элементов x[i..n-1] выбирается наименьший и меняется местами с x[i]. Когда i=n-1 сортировка прекращается и мы получаем отсортированную последовательность.
Пример. Имеется последовательность: 7, 2, 6, 5, 10, 4. n = 6. Получим:
0 шаг - i = 0, min = 2(i=1), меняем местами x[0]=7 и x[1]=2, в итоге: 2, 7, 6, 5, 10, 4
1 шаг - i = 1, min = 4(i=5), меняем местами x[1]=7 и x[5]=4, в итоге: 2, 4, 6, 5, 10, 7
2 шаг - i = 2, min = 5(i=3), меняем местами x[2]=6 и x[3]=5, в итоге: 2, 4, 5, 6, 10, 7
3 шаг - i = 3, min = 6(i=3), меняем местами x[3]=6 и x[3]=6, в итоге: 2, 4, 5, 6, 10, 7*
4 шаг - i = 4, min = 6(i=5), меняем местами x[4]=10 и x[5]=7, в итоге: 2, 4, 5, 6, 7, 10
* - пустая итерация. Физически "перестановка" осуществляется, но фактически она ничего меняет.
/* до n-2, а не n-1, т.к.
последний элемент уже стоит
на своем месте */
for i = 0 to n-2
k = i
t = x[i]
for j = i+1 to n-1
if (x[j] < t)
k = j
t = x[j]
x[k] = x[i]
x[i] = t
Алгоритм делает n-1 итераций, на каждой из которых осуществляется еще n-i проходов(сравнений) и одна перестановка. Следовательно общее количество операций получаем:
n + (n-1 + 1) + (n-2 + 1) + ... + 2 = 1/2*(n2 + 2*n) - 1. Т.о. производительность ~ O(n2).
К достоинствам можно отнести отсутствие расхода памяти: все операции перестановки происходятся на исходной последовательности.
Алгоритм - очень похож на алгоритм сортировки вставками. Можно даже сказать, что они в некотором отношении "симметричны": этот выбирает нужный элемент из неотсортированной последовательности и вставляет его последним в отсортированную, вставками - выбирает первый элемент из неотсортированных, но вставляет его в нужное место сортированной последовательности.
Реализации:
C++(2)
+добавить
1)
Сортировка выбором, общий подход на C++, code #18[автор:this]
template<class T>
void SelectSort(T* x) {
T t;
/* Главный цикл до n-1, а не n, т.к.
последний остающийся элемент -
максимальный */
for (int i = 0; i < n-1; i++) {
int k = i;
t = x[i];
for (int j = i; j < n; j++) {
if (x[j] < t) {
k = j;
t = x[j];
}
}
x[k] = x[i];
x[i] = t;
}
}
2)
сортировка выбором на C++, code #594[автор:-]
#include <stdio.h>
#include <conio.h>
int vibor (int in[], int n);
void main ()
{
int m=0;
int s;
int vvh [100];
//Ввод массива
char f [80];
printf("\nvvedite chislo elementov v massive: ", f
);
scanf ("%d", &m); //Узнаем размер массива
printf("\n vvedite cherez probel celie chisla:", f
);
for (int j=0; j<m; j++) scanf ("%d", &vvh[j]); //Заполнение массива
s = vibor (vvh, m); //Сортировка методом выбора
getch();
}
int vibor (int in[], int n)
{
int sravnen=0; //Характеристика трудоемкости (число стравнений)
//Вывод сообщений
char f [80];
printf("\nsortirovka metodom vibora:\n", f
);
//Начало сортировки
int i;
for (i=0; i<n-1; i++) //n-1 раз ищем наименьший элемент
{
int imin=i; //принимаем за наименьший первый из рассматриваемых элементов
//Поиск минимального элемента
for (int j= i + 1; j<n; j++)
{
if (in[j]<in[imin]) imin = j;
sravnen++;
}
int a = in[i]; in[i]=in[imin]; in[imin]=a; //Обмен элементов
}
//Вывод результатов работы программы
for (i=
0; i<n; i++
) printf ("%d ", in
[i
]);
return sravnen; //Возвращаем число сравнений
}