четверг, 3 января 2013 г.

Сортировка выбором (Selection Sort) + Реализация С++

Идея сортировки выбором состоит в том, что на i-ом шаге итерации ищется минимальный элемент в одномерном массиве размером n и этот элемент меняется местами с i-эм элементом массива. т.е. swap(min(к-ый нашли),a[i]). В результате
Время работы алгоритма O(n^2), так как для нахождения минимального элемента происходит n сравнений + по в процессе увеличения количества итераций, число сравнений уменьшается(n-1,n-2...1)
Алгоритм:

  1. находим номер минимального значения в текущем списке
  2. производим обмен этого значения со значением первой неотсортированной позиции (обмен не нужен, если минимальный элемент уже находится на данной позиции)
  3. теперь сортируем хвост списка, исключив из рассмотрения уже отсортированные элементы


Пример можно посмотреть здесь (стырено с algolist)


Реализация:


template < typename Type>
void Selection_Sort(Type mas[], unsigned long size){
 unsigned long minIndex;
 for (unsigned long i=0; i< size; i++){
  minIndex=i;
  for (unsigned long j=i+1; j< size; j++){
   if (mas[j]< mas[minIndex])
    minIndex=j;
  }
  if (minIndex!=i){
   swap(mas[minIndex],mas[i]);
  }
 }
}

0 коммент.:

Отправить комментарий