Selection Sort

Selection sort is a basic sorting algorithm that works by making iterations, or passes, through the data being sorted. Each pass results in the placement of one element into its correct location. As a result, each subsequent pass has to inspect one fewer item than the previous pass.

Figure 1 An unsorted array

Figure 1 contains an unsorted array. Since this array contains eight elements, a selection sort must make seven passes to sort the data. Each pass places one element into the position that will result in a sorted array. The next two figures represent the first two passes, respectively. In each figure, the filled arrow indicates the position that the pass is seeking to fill. During each pass, the algorithm looks for the smallest remaining element. The pass ends with the algorithm swapping the smallest element into the position under consideration.

Figure 2 The first pass

After the first pass, the lowest element is placed into the first position of the array. The next pass, illustrated by Figure 3, places the second lowest element into the second position of the array.

Figure 3 The second pass

The selection sort algorithm always makes one fewer passes than the number of elements in the array. This is true even if the original array is already sorted. The algorithm has no mechanism to detect when the array is sorted, so it must make all required passes. A C++ implementation of the selection sort appears in Listing 1.

1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19:	// Sorting using selection sort template <typename T> void selection_sort(vector<T>& v) {   for (unsigned int i = 0; i < v.size() - 1; i++) { unsigned int best = i; for (unsigned int j = i + 1; j < v.size(); j++) { if (v[j] < v[best]) { best = j; } }   if (best!= i) { T temp = v[i]; v[i] = v[best]; v[best] = temp; } } }
Listing 1 Selection Sort

4.1.1 Сравнение линейного поиска с двоичным Поиск: Общая задача Поиск данных является задачей имеющее место не только в информатике, но и в реальном мире. В основе задачи лежит поиск элемента сохраненного в векторе, осуществляется подобно поиску имени человека в телефонной книге. Т.е. требуется найти необходимые данные, которые существуют (где-нибудь) в большем наборе подобных данных. И в информатике, и в реальном мире, процессы включающие поиск отличаются по методу, в зависимости от условий нахождения искомого набора данных. Если набор располагается без определенного порядка, лучший процесс поиска это простой перебор всей коллекции данных. Он включает исследование каждого элемента находящегося в наборе (front-to-back), пока не найдется то, что мы ищем. Такое решение следует признать вполне приемлемым, но только для маленьких наборов данных. Предположим, требуется найти определенную карту в полностью перетасованной колоде. Только перебрав пятьдесят две карты поочередно и переворачивая их (front-to-back), позволит найти необходимую карту. Но большие наборы данных требуют более эффективного подхода поиска. Предположим, требуется найти номер телефона человека в телефонной книге, которая содержит список людей в произвольном порядке. Исследование каждого перечисления, вероятно, заняло бы несколько дней. Это определенно не эффективный подход, и является причиной, почему списки в телефонных книжках организовывают в алфавитном порядке. Знание, как в телефонной книге организованы списки, мы можем выполнить более эффективный поиск. Этот поиск включает открытие телефонной книги, и сравнение списков на странице с тем, что мы ищем. Если мы ищем "Doe, John", а страница, на которой мы открыли книгу, содержит только списки для " Smith", мы знаем, что должны обратиться к другой странице поближе к спискам для "Doe". Так мы продолжаем поиск, пока мы не достигнем страницы, содержащую необходимое слово. Такой поиск, вероятно, занял бы не более минуты времени. Он гораздо быстрее по сравнению с тем, когда приходилось бы вчитываться во все строки всех страниц (front-to-back). У обоих из этих подходов к поиску в реальном мире есть аналоги алгоритмов в информатики. Последовательность front-to-back известна как линейный поиск (linear search). Более формальная разновидность поиска, как по телефонной книге, известна как двоичный поиск (binary search). Линейный Поиск Линейный поиск является простым алгоритмом поиска, который находит элемент, перебирая данные в последовательном порядке. Поэтому линейный поиск иногда называют последовательным поиском. В C++ мы можем реализовать линейный поиск посредством цикла написав всего несколько строк кода.

1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11:	// Finding an element in a vector using linear search template <typename T> int linear_search(const vector<T>& v, const T& item) {   for (int i = 0; i < v.size(); i++) { if (v[i] == item) { return i; // item found } } return -1; // item not found }
Listing 1 Finding an element in a vector using a linear search

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

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

Функция STL find выполняет линейный поиск в контейнере. Эта функция принимает три параметра. Первыми двумя параметрами являются iterators, которые определяют диапазон поиска. Третий параметр является значение, которое функция пытается найти. Эта функция возвращает iterator первой позиции, которая содержит разыскиваемое значение. Если поиск неудачен, функция find возвращает iterator равное второму iterator. Использование в качестве примера функции find приведено в find.cpp, где программа заполняет вектор с первыми двадцатью пятью числами Фибоначчи. Она позволяет пользователю вводить число если число является одним из тех чисел Фибоначчи.