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

@maxim43k · Регистрация: 04.09.2011

Студворк — интернет-сервис помощи студентам

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

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;
}

@maxim43k · 06.09.2011, 21:46 **[ТС]**

«Исследование эффективности методов сортировки (поиска)»
Требуется оценить эффективность алгоритма (А) путем экспериментального определения зависимости О(f(N)) по числу сравнений или перемещений (присваиваний) – по заданию работы, где N – размер массива. Для прямых методов сортировки эта зависимость О(N2). Зависимость О(f(N)) нужно получить для случая по заданию: массив упорядочен наоборот (наихудший случай <<<). Чтобы точнее установить зависимость О(f(N)), нужно получить результаты для трех различных размеров массива данных, например, N = 100, 200 и 400. Результаты вычислений нужно поместить в таблицу:

Величина К должна оставаться примерно постоянной.
Кто-нибудь понял, что нужно сделать? Поясните мне русским языком, пожалуйста.

@-=ЮрА=- · 06.09.2011, 22:04

Вот пузырьком Отсортировать массив с помощью сортировки методом вставки
Вот вставкой Отсортировать массив с помощью сортировки методом вставки

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

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

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

PS:Приведенный в топике код на глаз посмотрел, впринципе пузырьком есть
увидел циклы присущие данному алгоритму :
два for(i = 0 for(j = i + 1 - это и позволяет "числам всплывать наверх"

@Thinker · 06.09.2011, 22:07

Сообщение от maxim43k

Хочу спросить, это пузырьковая сортировка или нет?

Нет, не она. Это сортировка методом прямого выбора.

@maxim43k · 06.09.2011, 22:09 **[ТС]**

Ведь там, насколько я понял, сортировка методом вставки, а нужна пузырьковая. А выше код - это что за сортировка?

@Thinker · 06.09.2011, 22:10

Вот пузырьковая:

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 · 06.09.2011, 22:11 **[ТС]**

Всё же, как сделать пузырьком?

@Thinker · 06.09.2011, 22:12

Сообщение от maxim43k

Ведь там, насколько я понял, сортировка методом вставки

Это метод прямого выбора

Добавлено через 35 секунд

Сообщение от maxim43k

Всё же, как сделать пузырьком?

В 6 посте она самая

@-=ЮрА=- · 06.09.2011, 22:12

Сообщение от Thinker

Это сортировка методом прямого выбора.

- уверен??? http://ru.wikipedia.org/wiki/%... 0%BE%D0%BC

@Thinker · 06.09.2011, 22:13

Сообщение от -=ЮрА=-

- уверен???

Что я, SelectionSort не знаю что-ли...ха-ха...

@maxim43k · 06.09.2011, 22:13 **[ТС]**

А как оценить эффективность алгоритма?

@-=ЮрА=- · 06.09.2011, 22:14

Сообщение от maxim43k

Всё же, как сделать пузырьком?

- зачем ссылки приводил?
Если есть желание самому написать вот ссылка http://algolist.manual.ru/sort/bubble_sort.php

@Thinker · 06.09.2011, 22:15

Сообщение от maxim43k

А как оценить эффективность алгоритма?

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

@-=ЮрА=- · 06.09.2011, 22:21

Сообщение от Thinker

Что я, SelectionSort не знаю что-ли...ха-ха...

неуверен но думаю ошибаешся и перепутал пузырёк с прямым выбором

http://www.vedikhin.ru/2007/01/bubble-sort.html

@Thinker · 06.09.2011, 22:23

Сообщение от -=ЮрА=-

неуверен но думаю ошибаешся и перепутал пузырёк с прямым выбором

Еще раз. В посте 1 - сортировка прямым выбором, в посте 6 - пузырьком (другое название - обменная сортировка).

@maxim43k · 06.09.2011, 22:27 **[ТС]**

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

@easybudda · 06.09.2011, 22:29

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 · 06.09.2011, 22:36

Сообщение от maxim43k

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

В среднем случае для пузырьковой сортировки сложность O(n^2). Если массив упорядочен наоборот (худший случай), то сложность алгоритма n(n-1)/2, так как вычисления сводятся к сумме ряда:
1+2+...+(n-1)

Добавлено через 6 минут
easybudda, ваш алгоритм лучше оптимизировать, так как если массив в какой-то момент времени в сортировке уже не нуждается, то ее следует прекратить.

@maxim43k · 06.09.2011, 22:42 **[ТС]**

А для оценки куда счётчик ставить? Вроде надо определить, сколько сравнений было.

@easybudda · 06.09.2011, 22:43

Не по теме:

Сообщение от Thinker

easybudda, ваш алгоритм лучше оптимизировать

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

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): сборка C/C++ проекта из консоли 8Observer8 30.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .	Установка Emscripten SDK (emsdk) и CMake на Windows для сборки C и C++ приложений в WebAssembly (Wasm) 8Observer8 30.01.2026 Чтобы скачать Emscripten SDK (emsdk) необходимо сначало скачать и уставить Git: Install for Windows. Следуйте стандартной процедуре установки Git через установщик. Система контроля версиями Git. . .	Подключение Box2D v3 к SDL3 для Android: физика и отрисовка коллайдеров 8Observer8 29.01.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .	Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT bedvit 28.01.2026 Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования. Часть библиотеки BedvitCOM Использованы. . .
Загрузка PNG с альфа-каналом на SDL3 для Android: с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 28.01.2026 Содержание блога SDL3 имеет собственные средства для загрузки и отображения PNG-файлов с альфа-каналом и базовой работы с ними. В этой инструкции используется функция SDL_LoadPNG(), которая. . .	Загрузка PNG с альфа-каналом на SDL3 для Android: с помощью SDL3_image 8Observer8 27.01.2026 Содержание блога SDL3_image - это библиотека для загрузки и работы с изображениями. Эта пошаговая инструкция покажет, как загрузить и вывести на экран смартфона картинку с альфа-каналом, то есть с. . .	Влияние грибов на сукцессию anaschu 26.01.2026 Бифуркационные изменения массы гриба происходят тогда, когда мы уменьшаем массу компоста в 10 раз, а скорость прироста биомассы уменьшаем в три раза. Скорость прироста биомассы может уменьшаться за. . .	Воспроизведение звукового файла с помощью SDL3_mixer при касании экрана Android 8Observer8 26.01.2026 Содержание блога SDL3_mixer - это библиотека я для воспроизведения аудио. В отличие от инструкции по добавлению текста код по проигрыванию звука уже содержится в шаблоне примера. Нужно только. . .

@maxim43k 0 / 0 / 0 Регистрация: 04.09.2011 Сообщений: 106
	06.09.2011, 21:46 [ТС]
	«Исследование эффективности методов сортировки (поиска)» Требуется оценить эффективность алгоритма (А) путем экспериментального определения зависимости О(f(N)) по числу сравнений или перемещений (присваиваний) – по заданию работы, где N – размер массива. Для прямых методов сортировки эта зависимость О(N2). Зависимость О(f(N)) нужно получить для случая по заданию: массив упорядочен наоборот (наихудший случай <<<). Чтобы точнее установить зависимость О(f(N)), нужно получить результаты для трех различных размеров массива данных, например, N = 100, 200 и 400. Результаты вычислений нужно поместить в таблицу: Величина К должна оставаться примерно постоянной. Кто-нибудь понял, что нужно сделать? Поясните мне русским языком, пожалуйста. 0

@-=ЮрА=- 6614 / 4256 / 401 Регистрация: 08.08.2009 Сообщений: 10,325 Записей в блоге: 24
	06.09.2011, 22:04
	Вот пузырьком Отсортировать массив с помощью сортировки методом вставки Вот вставкой Отсортировать массив с помощью сортировки методом вставки Здесь под 10-ку код Отсортировать массив с помощью сортировки методом вставки Алгоритмі рабочие т.к ТС топика на который ссылаюсь успешно здал этот алгоритм Отсортировать массив с помощью сортировки методом вставки PS:Приведенный в топике код на глаз посмотрел, впринципе пузырьком есть увидел циклы присущие данному алгоритму : два for(i = 0 for(j = i + 1 - это и позволяет "числам всплывать наверх" 1

@maxim43k 0 / 0 / 0 Регистрация: 04.09.2011 Сообщений: 106
	06.09.2011, 22:09 [ТС]
	Ведь там, насколько я понял, сортировка методом вставки, а нужна пузырьковая. А выше код - это что за сортировка? 0

@maxim43k 0 / 0 / 0 Регистрация: 04.09.2011 Сообщений: 106
	06.09.2011, 22:11 [ТС]
	Всё же, как сделать пузырьком? 0

@maxim43k 0 / 0 / 0 Регистрация: 04.09.2011 Сообщений: 106
	06.09.2011, 22:13 [ТС]
	А как оценить эффективность алгоритма? 0

@maxim43k 0 / 0 / 0 Регистрация: 04.09.2011 Сообщений: 106
	06.09.2011, 22:27 [ТС]
	В том то и дело, что я не знаю, КАК оценить эффективность алгоритма сортировки по числу сравнений (массив упорядочен наоборот). Это что, счётчик какой то ставить? А куда? 0

@maxim43k 0 / 0 / 0 Регистрация: 04.09.2011 Сообщений: 106
	06.09.2011, 22:42 [ТС]
	А для оценки куда счётчик ставить? Вроде надо определить, сколько сравнений было. 0