Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
 
Рейтинг 4.63/27: Рейтинг темы: голосов - 27, средняя оценка - 4.63
0 / 0 / 0
Регистрация: 04.09.2011
Сообщений: 106
1

Пузырьковая сортировка

06.09.2011, 21:39. Показов 5149. Ответов 31
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Хочу спросить, это пузырьковая сортировка или нет? Как её правильно реализовать? Как оценить эффективность алгоритма сортировки по числу сравнений (упорядочен по возрастанию)?

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <iostream.h>
#include <conio.h>
#define MAX 400
 
int main()
{
    long kol = 0;
    int A[MAX] = {0};
    clrscr();
    for(int i = 0; i < MAX; i++)
    {
    A[i] = MAX - i;
    }
    int c, t;
    int exchange;
 
    for(i=0; i < MAX-1; ++i)
    {
    exchange = 0;
    c = i;
    t = A[i];
    for(int j=i+1; j < MAX; ++j)
    {
        kol++;
        if(A[j] < t)
        {
        c = j;
        t = A[j];
        exchange = 1;
        }
    }
    if(exchange)
    {
        A[c] = A[i];
        A[i] = t;
    }
    }
    cout << kol;
    getch();
    return 0;
}
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
06.09.2011, 21:39
Ответы с готовыми решениями:

Пузырьковая сортировка
Здравствуйте .Объясните , пожалуйста , подробно , как работает пузырьковая сортировка . ...

Пузырьковая сортировка
Здравствуйте хочу разобраться в сортировках....нашла пример в книге.....но почему то она не...

Пузырьковая сортировка
Дан одномерный массив целых чисел A. Напишите программу, которая упорядочит все элементы до...

Пузырьковая сортировка
Написал программу сортировки методом пузырька: #include &lt;stdio.h&gt; #include &lt;conio.h&gt; #include...

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
Заблокирован
Автор FAQ
06.09.2011, 22:04 3
Вот пузырьком Отсортировать массив с помощью сортировки методом вставки
Вот вставкой Отсортировать массив с помощью сортировки методом вставки

Здесь под 10-ку код
Отсортировать массив с помощью сортировки методом вставки

Алгоритмі рабочие т.к ТС топика на который ссылаюсь успешно здал этот алгоритм
Отсортировать массив с помощью сортировки методом вставки

PS:Приведенный в топике код на глаз посмотрел, впринципе пузырьком есть
увидел циклы присущие данному алгоритму :
два for(i = 0 for(j = i + 1 - это и позволяет "числам всплывать наверх"
1
Эксперт С++
4267 / 2241 / 203
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
06.09.2011, 22:07 4
Цитата Сообщение от maxim43k Посмотреть сообщение
Хочу спросить, это пузырьковая сортировка или нет?
Нет, не она. Это сортировка методом прямого выбора.
1
0 / 0 / 0
Регистрация: 04.09.2011
Сообщений: 106
06.09.2011, 22:09  [ТС] 5
Ведь там, насколько я понял, сортировка методом вставки, а нужна пузырьковая. А выше код - это что за сортировка?
0
Эксперт С++
4267 / 2241 / 203
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
06.09.2011, 22:10 6
Вот пузырьковая:


C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
    void BubbleSort(double *a, const int n)
    {
       int i, r, flag;
       double buf;
       flag = 1;
       r = n;
       while(flag)
       {
          flag = 0;
          for(i = 1; i < r; i++)
             if (a[i] < a[i-1])
             {
                buf = a[i];
                a[i] = a[i-1];
                a[i-1] = buf;
                flag = 1;
             }
          r--;
       }
    }
1
0 / 0 / 0
Регистрация: 04.09.2011
Сообщений: 106
06.09.2011, 22:11  [ТС] 7
Всё же, как сделать пузырьком?
0
Эксперт С++
4267 / 2241 / 203
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
06.09.2011, 22:12 8
Цитата Сообщение от maxim43k Посмотреть сообщение
Ведь там, насколько я понял, сортировка методом вставки
Это метод прямого выбора

Добавлено через 35 секунд
Цитата Сообщение от maxim43k Посмотреть сообщение
Всё же, как сделать пузырьком?
В 6 посте она самая
1
Заблокирован
Автор FAQ
06.09.2011, 22:12 9
Цитата Сообщение от Thinker Посмотреть сообщение
Это сортировка методом прямого выбора.
- уверен??? http://ru.wikipedia.org/wiki/%... 0%BE%D0%BC
1
Эксперт С++
4267 / 2241 / 203
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
06.09.2011, 22:13 10
Цитата Сообщение от -=ЮрА=- Посмотреть сообщение
- уверен???
Что я, SelectionSort не знаю что-ли...ха-ха...
1
0 / 0 / 0
Регистрация: 04.09.2011
Сообщений: 106
06.09.2011, 22:13  [ТС] 11
А как оценить эффективность алгоритма?
0
Заблокирован
Автор FAQ
06.09.2011, 22:14 12
Цитата Сообщение от maxim43k Посмотреть сообщение
Всё же, как сделать пузырьком?
- зачем ссылки приводил?
Если есть желание самому написать вот ссылка http://algolist.manual.ru/sort/bubble_sort.php
1
Эксперт С++
4267 / 2241 / 203
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
06.09.2011, 22:15 13
Цитата Сообщение от maxim43k Посмотреть сообщение
А как оценить эффективность алгоритма?
Оцените число операций сравнения или число проходов по массиву, смотря что за основу брать. Отмечу, что пузырьковая сортировка это та еще "бяка", избегайте ее как только можно.
1
Заблокирован
Автор FAQ
06.09.2011, 22:21 14
Цитата Сообщение от Thinker Посмотреть сообщение
Что я, SelectionSort не знаю что-ли...ха-ха...
неуверен но думаю ошибаешся и перепутал пузырёк с прямым выбором
http://www.vedikhin.ru/2007/01/bubble-sort.html
1
Эксперт С++
4267 / 2241 / 203
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
06.09.2011, 22:23 15
Цитата Сообщение от -=ЮрА=- Посмотреть сообщение
неуверен но думаю ошибаешся и перепутал пузырёк с прямым выбором
Еще раз. В посте 1 - сортировка прямым выбором, в посте 6 - пузырьком (другое название - обменная сортировка).
1
0 / 0 / 0
Регистрация: 04.09.2011
Сообщений: 106
06.09.2011, 22:27  [ТС] 16
В том то и дело, что я не знаю, КАК оценить эффективность алгоритма сортировки по числу сравнений (массив упорядочен наоборот). Это что, счётчик какой то ставить? А куда?
0
Модератор
Эксперт PythonЭксперт JavaЭксперт CЭксперт С++
12460 / 7484 / 1754
Регистрация: 25.07.2009
Сообщений: 13,762
06.09.2011, 22:29 17
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <stdio.h>
 
#define count(a) ( sizeof(a) / sizeof(*(a)) )
 
void swap(int * a, int * b){
    int c = *a;
    *a = *b;
    *b = c;
}
 
void dump(const int * arr, size_t size){ while ( size-- ) printf("%d%c", *arr++, ( size ) ? ' ' : '\n'); }
 
void bublesort(int * arr, size_t size){
    size_t i, j;
    
    if ( ! arr || ! size )
        return;
        
    for ( i = 0; i < size - 1; ++i )
        for ( j = size - 1; j > i; --j )
            if ( arr[i] > arr[j] )
                swap(&arr[i], &arr[j]);
}
 
int main(void){
    int arr[] = { 3, 1, 5, 2, 4 };
    
    printf("Before: ");
    dump(arr, count(arr));
    bublesort(arr, count(arr));
    printf("After:  ");
    dump(arr, count(arr));
    
    return 0;
}
1
Эксперт С++
4267 / 2241 / 203
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
06.09.2011, 22:36 18
Цитата Сообщение от maxim43k Посмотреть сообщение
В том то и дело, что я не знаю, КАК оценить эффективность алгоритма сортировки по числу сравнений (массив упорядочен наоборот). Это что, счётчик какой то ставить? А куда?
В среднем случае для пузырьковой сортировки сложность 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

Не по теме:

Цитата Сообщение от Thinker Посмотреть сообщение
easybudda, ваш алгоритм лучше оптимизировать
Да ну нафиг! Пузырьковая сортировка нужна только, чтобы принцип понять, ну и преподу лабораторную сдать. Если речь заходит о производительности, есть несколько более удачные алгоритмы сортировки... ;)

0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
06.09.2011, 22:43

Пузырьковая сортировка
Есть курсовик. Есть пузырьковая сортировка Есть одно НО. Сортировка должна быть сделана через...

пузырьковая сортировка
Пожалуйста помогите написать программу, которая выполняет сортировку исходного целочисленного...

Пузырьковая сортировка
Здравствуйте. Есть код, который сортирует методом пузырька по строчкам, что мне поменять, чтобы...

Сортировка пузырьковая
Привет всем!помогите отсортировать задачку. #include &lt;iostream&gt; #include &lt;iomanip&gt; using...


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

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru