Сортировка выбором, общий подход

Имеется исходная неотсортированния последовательность 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*(n² + 2*n) - 1. Т.о. производительность ~ O(n²).

К достоинствам можно отнести отсутствие расхода памяти: все операции перестановки происходятся на исходной последовательности.

Алгоритм - очень похож на алгоритм сортировки вставками. Можно даже сказать, что они в некотором отношении "симметричны": этот выбирает нужный элемент из неотсортированной последовательности и вставляет его последним в отсортированную, вставками - выбирает первый элемент из неотсортированных, но вставляет его в нужное место сортированной последовательности.

Реализации:

заполните необходимые поля!

название:
uri-имя*:
заголовок окна:
ЯП:	[другой...] pseudojavajavascriptpythonC++C#CphpGoqbasicrailsrubysmartytsqlvbnetvisualfoxproxmlactionscriptplsqlpascaloracle8sqlvbfortransmalltalkasmcssdelphigroovylispperlmysqlmatlab
код (double click - редактирование) (Esc - предпросмотр)
описание:
автор:	email:
пароль:	[для последующего редактирования]
	подписаться на комментарии**

*	можно кириллицей (недопустимые символы:?&+=\/%#)
**	только для зарегистрированных пользователей

 Сортировка выбором, общий подход ссылка |режим:

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;
    }
}

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; } }

Использует стратегию схожую с алгоритмом сортировки вставками.

Производительность: ~ O(n²)
Расход памяти: - (память используется только под счетчики циклов и 1 вспомогательный элемент)

Тестировалось на: MS Visual Studio 2005, .NET Framework 2.0

 

 сортировка выбором ссылка |режим:

#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]);                //Заполнение массива
 
   printf ("\n");
   s = vibor (vvh, m);                                                //Сортировка методом выбора
   printf("sravneniy", f);
   printf ("%d", s);
 
	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]);
   printf ("\n");
 
return sravnen;	                                              //Возвращаем число сравнений
}

#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]); //Заполнение массива printf ("\n"); s = vibor (vvh, m); //Сортировка методом выбора printf("sravneniy", f); printf ("%d", s); 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]); printf ("\n"); return sravnen; //Возвращаем число сравнений }

Сортировка выбором. Выбирается минимальный элемент в массиве, переносится в выходной массив на очередную позицию. Во входном массиве все элементы от следующего за текущим до конца сдвигаются на один влево.