Теория: Общая информация изложена здесь
Практика: informatics.mccme.ru
Визуализатор: rain.ifmo.ru [Java]
Реализация:
- void selection_sort(vector<int> &mas)
- {
- for (int i=0;i<mas.size();i++)
- for (int j=i+1;j<mas.size();j++)
- if (mas[i]>mas[j])
- swap(mas[i],mas[j]);
- }
* This source code was highlighted with Source Code Highlighter.UPD[29.09.2011]
- void selection_sort(vector<int> &mas) {
- for(int i=0;i<mas.size();i++) {
- int minPos = i;
- for(int j=i+1;j<mas.size();j++)
- if(mas[minPos] > mas[j])
- minPos = j;
- swap(mas[minPos],mas[i]);
- }
- }
* This source code was highlighted with Source Code Highlighter.P.S: Из всех квадратичных сортировок сортировка выбором имеет самую локаничную запись и сложность O(n*(n-1)/2). Вот почему, мне она нравится больше других квадратичных сортировок)
Это не сортировка выбором.
ОтветитьУдалитьПервая реализация использует принцип сортировки выбором. При этом она имеет локаничную запись, но выполняет лишние обмены. Думаю вторая реализация Вам больше понравится.
ОтветитьУдалитьОбъясню почему мне нравится первая реализация.
Во-первых, она пишется в 4 строчки.
Во-вторых, лишние обмены не приведут к значительному замедлению программы, т.к. количество объектов в массиве будет ограничено разумным числом. (1000 например).
В-третьих, если размеры элементов велики и операция swap являтся тяжеловесной, то всегда можно сортировать не сами объекты, а указатели на них.