С наступающим Новым годом! Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.67/3: Рейтинг темы: голосов - 3, средняя оценка - 4.67
Pavel93
4 / 1 / 0
Регистрация: 27.05.2013
Сообщений: 21
1

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

27.12.2013, 15:54. Просмотров 569. Ответов 3
Метки нет (Все метки)

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

Я пытался найти такую последовательность, но получается только одинаковое число присваиваний.
Пузырёк эффективен на практически отсортированных массивах, когда "маленькое число не загнанно в конец", но тут и выбор хорош.
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
27.12.2013, 15:54
Ответы с готовыми решениями:

Алгоритм сортировки выбором данных: простой выбор, пирамидальная сортировка
Помогите кто нить !)) мот у кого есть какие нить исходники?) я там и сам доделаю. начало просто...

Метод сортировки обменами
Дан массив В, состоящий из n элементов. Элементы массива ввести случайным образом. Переставить...

Задача на алгоритм сортировки обменами (метод пузырька)
Напишите улучшенную программу сортировки обменами. Напомним алгоритм сортировки обменами (метод...

Упорядочить символьный массив по алфавиту, используя метод сортировки обменами
Упорядочить символьный массив А(n), n<50 по алфавиту, используя метод сортировки обменами.

Сортировка обменами
Сортировка обменами. 1)Дана последовательность чисел a1, a2 , ..., an. Требуется представить числа...

3
riv94
64 / 64 / 29
Регистрация: 13.02.2011
Сообщений: 392
27.12.2013, 18:37 2
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
Qwertiy
821 / 629 / 100
Регистрация: 20.08.2013
Сообщений: 2,524
30.12.2013, 13:47 3
Цитата Сообщение от 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]);
    }
}
0
riv94
64 / 64 / 29
Регистрация: 13.02.2011
Сообщений: 392
31.12.2013, 00:41 4
Qwertiy, честно говоря, я тоже здесь очень озадачен... Вирт говорит одно, я же согласен с вами.. потому и не знаю, как быть
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
31.12.2013, 00:41

Сортировка обменами
Сортировка обменами. Дана последовательность чисел a1, a2, …, an Требуется представить числа...

Сортировка обменами
Доброго времени суток. У меня есть часть кода программы, которую я хочу реализовать: #include...

Сортировка обменами
Дана последовательность чисел a1, a2,...an. Требуется переставить числа в порядке возрастания. Для...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
4
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru