Форум программистов, компьютерный форум CyberForum.ru

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

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 22, средняя оценка - 4.68
maxim43k
0 / 0 / 0
Регистрация: 04.09.2011
Сообщений: 106
06.09.2011, 21:39     Пузырьковая сортировка #1
Хочу спросить, это пузырьковая сортировка или нет? Как её правильно реализовать? Как оценить эффективность алгоритма сортировки по числу сравнений (упорядочен по возрастанию)?

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;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
06.09.2011, 21:39     Пузырьковая сортировка
Посмотрите здесь:

пузырьковая сортировка C++
Пузырьковая сортировка C++
Сортировка пузырьковая C++
C++ Пузырьковая сортировка
C++ Пузырьковая сортировка
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
maxim43k
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. Результаты вычислений нужно поместить в таблицу:

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

Величина К должна оставаться примерно постоянной.
Кто-нибудь понял, что нужно сделать? Поясните мне русским языком, пожалуйста.
-=ЮрА=-
Заблокирован
Автор FAQ
06.09.2011, 22:04     Пузырьковая сортировка #3
Вот пузырьком Отсортировать массив с помощью сортировки методом вставки
Вот вставкой Отсортировать массив с помощью сортировки методом вставки

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

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

PS:Приведенный в топике код на глаз посмотрел, впринципе пузырьком есть
увидел циклы присущие данному алгоритму :
два for(i = 0 for(j = i + 1 - это и позволяет "числам всплывать наверх"
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
06.09.2011, 22:07     Пузырьковая сортировка #4
Цитата Сообщение от maxim43k Посмотреть сообщение
Хочу спросить, это пузырьковая сортировка или нет?
Нет, не она. Это сортировка методом прямого выбора.
maxim43k
0 / 0 / 0
Регистрация: 04.09.2011
Сообщений: 106
06.09.2011, 22:09  [ТС]     Пузырьковая сортировка #5
Ведь там, насколько я понял, сортировка методом вставки, а нужна пузырьковая. А выше код - это что за сортировка?
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 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--;
       }
    }
maxim43k
0 / 0 / 0
Регистрация: 04.09.2011
Сообщений: 106
06.09.2011, 22:11  [ТС]     Пузырьковая сортировка #7
Всё же, как сделать пузырьком?
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
06.09.2011, 22:12     Пузырьковая сортировка #8
Цитата Сообщение от maxim43k Посмотреть сообщение
Ведь там, насколько я понял, сортировка методом вставки
Это метод прямого выбора

Добавлено через 35 секунд
Цитата Сообщение от maxim43k Посмотреть сообщение
Всё же, как сделать пузырьком?
В 6 посте она самая
-=ЮрА=-
Заблокирован
Автор FAQ
06.09.2011, 22:12     Пузырьковая сортировка #9
Цитата Сообщение от Thinker Посмотреть сообщение
Это сортировка методом прямого выбора.
- уверен??? http://ru.wikipedia.org/wiki/%D0%A1%...BA%D0%BE%D0%BC
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
06.09.2011, 22:13     Пузырьковая сортировка #10
Цитата Сообщение от -=ЮрА=- Посмотреть сообщение
- уверен???
Что я, SelectionSort не знаю что-ли...ха-ха...
maxim43k
0 / 0 / 0
Регистрация: 04.09.2011
Сообщений: 106
06.09.2011, 22:13  [ТС]     Пузырьковая сортировка #11
А как оценить эффективность алгоритма?
-=ЮрА=-
Заблокирован
Автор FAQ
06.09.2011, 22:14     Пузырьковая сортировка #12
Цитата Сообщение от maxim43k Посмотреть сообщение
Всё же, как сделать пузырьком?
- зачем ссылки приводил?
Если есть желание самому написать вот ссылка http://algolist.manual.ru/sort/bubble_sort.php
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
06.09.2011, 22:15     Пузырьковая сортировка #13
Цитата Сообщение от maxim43k Посмотреть сообщение
А как оценить эффективность алгоритма?
Оцените число операций сравнения или число проходов по массиву, смотря что за основу брать. Отмечу, что пузырьковая сортировка это та еще "бяка", избегайте ее как только можно.
-=ЮрА=-
Заблокирован
Автор FAQ
06.09.2011, 22:21     Пузырьковая сортировка #14
Цитата Сообщение от Thinker Посмотреть сообщение
Что я, SelectionSort не знаю что-ли...ха-ха...
неуверен но думаю ошибаешся и перепутал пузырёк с прямым выбором
http://www.vedikhin.ru/2007/01/bubble-sort.html
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
06.09.2011, 22:23     Пузырьковая сортировка #15
Цитата Сообщение от -=ЮрА=- Посмотреть сообщение
неуверен но думаю ошибаешся и перепутал пузырёк с прямым выбором
Еще раз. В посте 1 - сортировка прямым выбором, в посте 6 - пузырьком (другое название - обменная сортировка).
maxim43k
0 / 0 / 0
Регистрация: 04.09.2011
Сообщений: 106
06.09.2011, 22:27  [ТС]     Пузырьковая сортировка #16
В том то и дело, что я не знаю, КАК оценить эффективность алгоритма сортировки по числу сравнений (массив упорядочен наоборот). Это что, счётчик какой то ставить? А куда?
easybudda
Модератор
Эксперт С++
 Аватар для easybudda
9371 / 5421 / 914
Регистрация: 25.07.2009
Сообщений: 10,423
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;
}
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 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, ваш алгоритм лучше оптимизировать, так как если массив в какой-то момент времени в сортировке уже не нуждается, то ее следует прекратить.
maxim43k
0 / 0 / 0
Регистрация: 04.09.2011
Сообщений: 106
06.09.2011, 22:42  [ТС]     Пузырьковая сортировка #19
А для оценки куда счётчик ставить? Вроде надо определить, сколько сравнений было.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
06.09.2011, 22:43     Пузырьковая сортировка
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
easybudda
06.09.2011, 22:43     Пузырьковая сортировка
  #20

Не по теме:

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

Yandex
Объявления
06.09.2011, 22:43     Пузырьковая сортировка
Ответ Создать тему
Опции темы

Текущее время: 03:02. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru