0 / 0 / 0
Регистрация: 04.09.2011
Сообщений: 106
|
||||||
1 | ||||||
Пузырьковая сортировка06.09.2011, 21:39. Показов 5149. Ответов 31
Метки нет (Все метки)
Хочу спросить, это пузырьковая сортировка или нет? Как её правильно реализовать? Как оценить эффективность алгоритма сортировки по числу сравнений (упорядочен по возрастанию)?
0
|
06.09.2011, 21:39 | |
Ответы с готовыми решениями:
31
Пузырьковая сортировка Пузырьковая сортировка Пузырьковая сортировка Пузырьковая сортировка |
0 / 0 / 0
Регистрация: 04.09.2011
Сообщений: 106
|
|
06.09.2011, 21:46 [ТС] | 2 |
«Исследование эффективности методов сортировки (поиска)»
Требуется оценить эффективность алгоритма (А) путем экспериментального определения зависимости О(f(N)) по числу сравнений или перемещений (присваиваний) – по заданию работы, где N – размер массива. Для прямых методов сортировки эта зависимость О(N2). Зависимость О(f(N)) нужно получить для случая по заданию: массив упорядочен наоборот (наихудший случай <<<). Чтобы точнее установить зависимость О(f(N)), нужно получить результаты для трех различных размеров массива данных, например, N = 100, 200 и 400. Результаты вычислений нужно поместить в таблицу: Величина К должна оставаться примерно постоянной. Кто-нибудь понял, что нужно сделать? Поясните мне русским языком, пожалуйста.
0
|
Заблокирован
|
|
06.09.2011, 22:04 | 3 |
Вот пузырьком Отсортировать массив с помощью сортировки методом вставки
Вот вставкой Отсортировать массив с помощью сортировки методом вставки Здесь под 10-ку код Отсортировать массив с помощью сортировки методом вставки Алгоритмі рабочие т.к ТС топика на который ссылаюсь успешно здал этот алгоритм Отсортировать массив с помощью сортировки методом вставки PS:Приведенный в топике код на глаз посмотрел, впринципе пузырьком есть увидел циклы присущие данному алгоритму : два for(i = 0 for(j = i + 1 - это и позволяет "числам всплывать наверх"
1
|
0 / 0 / 0
Регистрация: 04.09.2011
Сообщений: 106
|
|
06.09.2011, 22:09 [ТС] | 5 |
Ведь там, насколько я понял, сортировка методом вставки, а нужна пузырьковая. А выше код - это что за сортировка?
0
|
06.09.2011, 22:10 | 6 | |||||
Вот пузырьковая:
1
|
0 / 0 / 0
Регистрация: 04.09.2011
Сообщений: 106
|
|
06.09.2011, 22:11 [ТС] | 7 |
Всё же, как сделать пузырьком?
0
|
Заблокирован
|
|
06.09.2011, 22:12 | 9 |
- уверен??? http://ru.wikipedia.org/wiki/%... 0%BE%D0%BC
1
|
0 / 0 / 0
Регистрация: 04.09.2011
Сообщений: 106
|
|
06.09.2011, 22:13 [ТС] | 11 |
А как оценить эффективность алгоритма?
0
|
Заблокирован
|
|
06.09.2011, 22:14 | 12 |
- зачем ссылки приводил?
Если есть желание самому написать вот ссылка http://algolist.manual.ru/sort/bubble_sort.php
1
|
06.09.2011, 22:15 | 13 |
Оцените число операций сравнения или число проходов по массиву, смотря что за основу брать. Отмечу, что пузырьковая сортировка это та еще "бяка", избегайте ее как только можно.
1
|
Заблокирован
|
|
06.09.2011, 22:21 | 14 |
неуверен но думаю ошибаешся и перепутал пузырёк с прямым выбором
http://www.vedikhin.ru/2007/01/bubble-sort.html
1
|
0 / 0 / 0
Регистрация: 04.09.2011
Сообщений: 106
|
|
06.09.2011, 22:27 [ТС] | 16 |
В том то и дело, что я не знаю, КАК оценить эффективность алгоритма сортировки по числу сравнений (массив упорядочен наоборот). Это что, счётчик какой то ставить? А куда?
0
|
Модератор
12460 / 7484 / 1754
Регистрация: 25.07.2009
Сообщений: 13,762
|
||||||
06.09.2011, 22:29 | 17 | |||||
1
|
06.09.2011, 22:36 | 18 |
В среднем случае для пузырьковой сортировки сложность O(n^2). Если массив упорядочен наоборот (худший случай), то сложность алгоритма n(n-1)/2, так как вычисления сводятся к сумме ряда:
1+2+...+(n-1) Добавлено через 6 минут easybudda, ваш алгоритм лучше оптимизировать, так как если массив в какой-то момент времени в сортировке уже не нуждается, то ее следует прекратить.
1
|
0 / 0 / 0
Регистрация: 04.09.2011
Сообщений: 106
|
|
06.09.2011, 22:42 [ТС] | 19 |
А для оценки куда счётчик ставить? Вроде надо определить, сколько сравнений было.
0
|
easybudda
|
06.09.2011, 22:43
Пузырьковая сортировка
#20
|
0
|
06.09.2011, 22:43 | |
Пузырьковая сортировка пузырьковая сортировка Пузырьковая сортировка Сортировка пузырьковая Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |