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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 22, средняя оценка - 4.68
maxim43k
0 / 0 / 0
Регистрация: 04.09.2011
Сообщений: 106
#1

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

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

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

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++
В чес дело не могу понять? Переменной массива с индексом X присваивается какое то левое значение. #include &lt;iostream&gt; #include...

Пузырьковая Сортировка - C++
Описать структуру с именем Train, содержащую следующие поля: Point (название пункта назначения), Number (номер поезда), Time (время...

Сортировка пузырьковая - C++
Привет всем!помогите отсортировать задачку. #include &lt;iostream&gt; #include &lt;iomanip&gt; using namespace std; int main() { const...

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

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

Пузырьковая сортировка - C++
Помогите плз. Работаю в Visual Studio 2010. Написал алгоритм пузырьковой сортировки, но когда запускаю вместо одной из цифр выводится самое...

пузырьковая сортировка - 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++
4221 / 2195 / 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++
4221 / 2195 / 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++
4221 / 2195 / 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++
4221 / 2195 / 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++
4221 / 2195 / 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++
4221 / 2195 / 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
Эксперт С++
9456 / 5469 / 927
Регистрация: 25.07.2009
Сообщений: 10,495
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++
4221 / 2195 / 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++
#include &lt;iostream&gt; #include &lt;fstream&gt; using namespace std; int main() { const int n = 5; int a; ifstream...

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

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

Пузырьковая сортировка - C++
Помогите исправить не сортирует массив.Еще должен считать кол-во шагов прохода цикла. #include &lt;stdio.h&gt; #include &lt;conio.h&gt; #include...


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

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

Не по теме:

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

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

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