Случай когда сортировка обменами эффективней сортировки выбором на малом массиве

@Pavel93 · Регистрация: 27.05.2013

Студворк — интернет-сервис помощи студентам

Здравствуйте, возможно ли привести последовательность на массиве из 5 чисел, когда сортировка обменами сделает меньше присваиваний, чем алгоритм сортировки выбором?

Я пытался найти такую последовательность, но получается только одинаковое число присваиваний.
Пузырёк эффективен на практически отсортированных массивах, когда "маленькое число не загнанно в конец", но тут и выбор хорош.

@riv94 · 27.12.2013, 18:37

Pavel93, решаю похожую задачу. Теоретическая подоплека из книжки Н.Вирта "Алгоритмы и структуры данных". Ну, поехали:

1) Пусть у нас n элементов!

2)Алгоритм сортировки выбором:
Кол-во сравнений не зависит от начального положения ключей C=(n^2-n)/2
Кол-во пересылок(присваиваний элементов) минимально для изначально упорядоченной последовательности (например: 12345) и равно Mmin=3(n-1)

3) Проведем аналогичный анализ алгоритма сортировки обменами("пузырьковой сортировки").
Что мы имеем...
Кол-во сравнений не зависит от начального положения ключей C=(n^2-n)/2
Кол-во пересылок(присваиваний элементов) минимально для изначально упорядоченной последовательности (например: 12345) и равно Mmin=0.

4)ВЫВОД: сортировка обменами делает значительно! меньше присваиваний, чем сортировка выбором на изначально упорядоченной последовательности!

Надеюсь, мои рассуждения верны,я ориентировался на книжку Вирта!)

@Qwertiy · 30.12.2013, 13:47

Сообщение от riv94

Кол-во пересылок(присваиваний элементов) минимально для изначально упорядоченной последовательности (например: 12345) и равно Mmin=3(n-1)

Почему? Что-то не пойму, где там будут присваивания для отсортированной последовательности.

Сообщение от http://ru.wikipedia.org/wiki/Сортировка_выбором

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
template <class Item>
void selection(Item a[], int len) {
 
    /* внешний цикл. i – позиция первого неотсортированного элемента на данной итерации */
    for (int i = 0; i < len - 1; i++) {
        int min = i; /* min – позиция минимального элемента */
 
        /* внутренний цикл. если найден элемент строго меньший текущего минимального, записываем его индекс как минимальный */
        for(int j = i + 1; j < len; j++) {
            if(a[j] < a[min])
                min = j;
        }
        if(min != i) /* минимальный элемент не является первым неотсортированным, обмен нужен */
            exch(a[i], a[min]);
    }
}

@riv94 · 31.12.2013, 00:41

Qwertiy, честно говоря, я тоже здесь очень озадачен... Вирт говорит одно, я же согласен с вами.. потому и не знаю, как быть

Новые блоги и статьи Все статьи Все блоги /
Символические и жёсткие ссылки в Linux. algri14 15.03.2026 Существует два типа ссылок — символические и жёсткие. Ссылка в Linux — это дополнительная запись в каталоге, которая может указывать либо на inode «файла-ИСТОЧНИКА», тогда это будет «жёсткая. . .	[Owen Logic] Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ФедосеевПавел 14.03.2026 Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ВВЕДЕНИЕ Выполняя задание на управление насосной группой заполнения резервуара,. . .	делаю науч статью по влиянию грибов на сукцессию anaschu 13.03.2026 прикрепляю статью	SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++ 8Observer8 10.03.2026 Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:
Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE 8Observer8 10.03.2026 Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .	Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки Neotwalker 08.03.2026 Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .	Модульная разработка через nuget packages DevAlt 07.03.2026 Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .	Модульный подход на примере F# DevAlt 06.03.2026 В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .

@Pavel93 4 / 1 / 0 Регистрация: 27.05.2013 Сообщений: 21

	Случай когда сортировка обменами эффективней сортировки выбором на малом массиве 27.12.2013, 15:54. Показов 1011. Ответов 3 Метки нет (Все метки) Здравствуйте, возможно ли привести последовательность на массиве из 5 чисел, когда сортировка обменами сделает меньше присваиваний, чем алгоритм сортировки выбором? Я пытался найти такую последовательность, но получается только одинаковое число присваиваний. Пузырёк эффективен на практически отсортированных массивах, когда "маленькое число не загнанно в конец", но тут и выбор хорош. 0

@riv94 66 / 66 / 29 Регистрация: 13.02.2011 Сообщений: 392
	27.12.2013, 18:37
	Pavel93, решаю похожую задачу. Теоретическая подоплека из книжки Н.Вирта "Алгоритмы и структуры данных". Ну, поехали: 1) Пусть у нас n элементов! 2)Алгоритм сортировки выбором: Кол-во сравнений не зависит от начального положения ключей C=(n^2-n)/2 Кол-во пересылок(присваиваний элементов) минимально для изначально упорядоченной последовательности (например: 12345) и равно Mmin=3(n-1) 3) Проведем аналогичный анализ алгоритма сортировки обменами("пузырьковой сортировки"). Что мы имеем... Кол-во сравнений не зависит от начального положения ключей C=(n^2-n)/2 Кол-во пересылок(присваиваний элементов) минимально для изначально упорядоченной последовательности (например: 12345) и равно Mmin=0. 4)ВЫВОД: сортировка обменами делает значительно! меньше присваиваний, чем сортировка выбором на изначально упорядоченной последовательности! Надеюсь, мои рассуждения верны,я ориентировался на книжку Вирта!) 1

@riv94 66 / 66 / 29 Регистрация: 13.02.2011 Сообщений: 392
	31.12.2013, 00:41
	Qwertiy, честно говоря, я тоже здесь очень озадачен... Вирт говорит одно, я же согласен с вами.. потому и не знаю, как быть 0