Selection Sort - раздел Образование, Unit 4. Sorting, Searching, and Complexity · 4.1 Sorting and Searching · 4.2 Complexity Assessments · Multiple-Choice Quiz Selection Sort Is A Basic Sorting Algorithm That Works By Making Iterations, ...
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 1An 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 2The 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 3The 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.
// 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 1Selection 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 1Finding an element in a vector using a linear search
Помимо простоты реализации, основное преимущество линейного поиска состоит в том, что он не требует сортированных данных. Даже если данные, содержащиеся в наборе данных, хранятся в произвольном порядке, линейный поиск все равно сработает обязательно. Потому что линейный поиск не делает предположений по поводу схемы расположения данных. Метод просто перебирает каждый элемент в наборе данных, пока не найдет требуемое.
Основной недостаток линейного поиска, он пригоден только для небольших наборов данных. Наилучший результат достигается, когда сразу же первый элемент является тем что ищем. В худшем случае поиск завершается, когда востребованный элемент оказывается последним. Для векторов или массивов, содержащие несколько миллионов элементов, поиск может занять значительное время, особенно если поиск повторяется многократно. Среднестатистическим, линейный поиск проходит половину элементов, прежде чем найдет искомое.
Функция STL find выполняет линейный поиск в контейнере. Эта функция принимает три параметра. Первыми двумя параметрами являются iterators, которые определяют диапазон поиска. Третий параметр является значение, которое функция пытается найти. Эта функция возвращает iterator первой позиции, которая содержит разыскиваемое значение. Если поиск неудачен, функция find возвращает iterator равное второму iterator. Использование в качестве примера функции find приведено в find.cpp, где программа заполняет вектор с первыми двадцатью пятью числами Фибоначчи. Она позволяет пользователю вводить число если число является одним из тех чисел Фибоначчи.
На сайте allrefs.net читайте: "Unit 4. Sorting, Searching, and Complexity · 4.1 Sorting and Searching · 4.2 Complexity Assessments · Multiple-Choice Quiz"
Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ:
Selection Sort
Что будем делать с полученным материалом:
Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:
Binary Search
A binary search is a fast search algorithm suitable for data sets of any reasonable size encountered. Unlike a linear search, it is suitable even for very large data sets because it eliminates larg
Sorting Overview
Many different basic sorting algorithms exist. Each of these algorithms has unique characteristics, behaviors, and requirements. For example, for the same set of data, one algorithm may perform far
Binary поиск
Binary поиск считается быстрым алгоритмом поиска, подходит для наборов данных любого разумного размера. В отличие от линейного поиска, может использоваться даже для очень больших наборов данных, по
Краткий обзор
Существуют много различных алгоритмов сортировки. У каждого из этих алгоритмов есть уникальные характеристики, поведения, и требования. Например, для одной и той же задачи, один алгоритм может выпо
Selection Sort (Вид выбора)
Алгоритм selection sort является основным алгоритмом сортировки, который работает посредством итерации, или передачи сортируемых данных. Каждая передача приводит к перемещению одного элемента в его
Алгоритм
Quicksort является быстрым алгоритмом сортировки, который решает задачу используя проблему divide-and-conquer (разделяй и властвуй). Quicksort это рекурсия приводит массив элементов к элементарному
Реализация
Код quicksort реализации приведен в листинге 1. Эта quicksort реализация использует основную стратегию выбора центра как выбор среднего элемента. Это простой подход к реализации, и иногда он может
Использование функции сортировки STL
Стандартная библиотека шаблонов включает функции, которые программисты могут использовать, чтобы сортировать массивы контейнеров. Одна из этих функций sort функция. Функция sort выполняет быстрый s
Краткий обзор Хэш-таблиц
Хэш-таблица это структура данных ассоциативного массива, которая поддерживает очень быструю вставку элементов, удаление, и извлечение. Т.е. она позволяет хранить пары (ключ, значение) и выпо
Хеш-функции
Операции использующие хэш-таблицы эффективны, потому что позиция хранимой суммы может быть вычислена, используя ключ. Хэш-таблицы обычно реализуются как массив значений, а хеш-функция исполь
Реализация Хэш-таблицы
Следующий файл заголовочного файла и реализации объявляет и определяет шаблонный класс сопоставления хеша. Класс берет четыре шаблонных параметра. Первым является ключевой тип, и вторым является ти
The Algorithm
Quicksort is a fast sorting algorithm that uses a divide-and-conquer problem solving approach. Unlike the basic sorting algorithms we have already examined, quicksort uses recursion. Given an array
An Implementation
A quicksort implementation appears in Listing 1. This quicksort implementation uses a basic pivot selection strategy of selecting the middle element. This is a simple approach to implement, but one
Using the STL Sorting Functions
The Standard Template Library includes functions that programmers can use to sort a variety of containers. One of these functions is the sort function. The sort function performs a fast sort (typic
Overview of Hash Tables
A hash table is a data structure that supports very fast element insertion, removal, and retrieval. A hash table that is properly configured for the elements it contains can support these op
Hash Functions
Operations using hash tables are efficient because the position of a stored value can be calculated using the key. Hash tables are implemented typically as an array of values. A hash function
A Hash Table Implementation
The following header file and implementation file declares and defines a template hash map class. The class takes four template parameters. The first is the key type and the second is the value typ
Хотите получать на электронную почту самые свежие новости?
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Новости и инфо для студентов