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

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

@Thinker · 06.09.2011, 22:55

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

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

Во внутренний цикл. Хотя это теоретически вычисляется.

Добавлено через 11 минут

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

Не по теме:

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

Не по теме:

Да, но мозги то зачем. Чтобы подумать и хоть немного что-то улучшить. Тем более, человек учиться пришел, а не любой ценой диплом получить. Это я в идеальном случае:) А сама эта пузырьковая сортировка и близко никуда не годится, это понятно

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

Как оценить по количеству сравнений?

@Thinker · 06.09.2011, 23:01

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

Как оценить по количеству сравнений?

перед if счетчик увеличивайте

@easybudda · 06.09.2011, 23:11

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
#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'); }
 
size_t bublesort(int * arr, size_t size){
    size_t i, j, cnt;
    
    if ( ! arr || ! size )
        return;
        
    for ( cnt = 0, i = 0; i < size - 1; ++i )
        for ( j = size - 1; j > i && ++cnt; --j )
            if ( arr[i] > arr[j] )
                swap(&arr[i], &arr[j]);
    return cnt;
}
 
int main(void){
    int arr[] = { 3, 8, 6, 1, 5, 9, 2, 4, 0, 7 };
    size_t count;
    
    printf("Before: ");
    dump(arr, count(arr));
    count = bublesort(arr, count(arr));
    printf("After:  ");
    dump(arr, count(arr));
    printf("Sorted by %u steps\n", count);
    
    return 0;
}

@maxim43k · 07.09.2011, 14:04 **[ТС]**

Вроде это сортировка по возрастанию, а надо сортировку наоборот, наихудший случай

@easybudda · 07.09.2011, 14:50

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

а надо сортировку наоборот

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

if ( arr[i] > arr[j] )

C
1
if ( arr[i] < arr[j] )

@maxim43k · 07.09.2011, 16:44 **[ТС]**

А как сортировка будет выглядеть на С++? Там же с потоками как-то?

@Thinker · 07.09.2011, 17:51

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

А как сортировка будет выглядеть на С++? Там же с потоками как-то?

Смотря что вам сортировать надо. Если массивы, то они и в Африке массивы.

@maxim43k · 07.09.2011, 18:41 **[ТС]**

Как переделать пузырёк со счётчиком к такому виду? Одна функция, язык С++? Типа такого, только с моим случаем:

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

@Thinker · 07.09.2011, 18:51

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

Как переделать пузырёк со счётчиком к такому виду? Одна функция, язык С++? Типа такого, только с моим случаем:

Слушайте, но я же вам говорил, что у вас метод прямого выбора.

Добавлено через 8 минут
Или вы про это:

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
#include<iostream>
const int N = 400;
 
int main()
{
   int i, r, flag, a[N], count;
   double buf;
   for (i = 0; i < N; i++)
      a[i] = N - i;
   flag = 1;
   r = N;
   count = 0;
   while(flag)
   {
      flag = 0;
      for(i = 1; i < r; i++)
      {
         count++;
         if (a[i] < a[i-1])
         {
            buf = a[i];
            a[i] = a[i-1];
            a[i-1] = buf;
            flag = 1;
         }
      }
      r--;
   }
   std::cout << count;
   return 0;
}

@maxim43k · 07.09.2011, 19:01 **[ТС]**

Я про то, что запутался в разных "size_t" и т.п. Поэтому прошу показать, как это всё делается по простому, в одной функции, на языке С++, со счётчиком сравнений... Было бы прекрасно, если бы был готовый код, в котором ничего исправлять не нужно.

@Thinker · 07.09.2011, 19:17

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

Я про то, что запутался в разных "size_t" и т.п. Поэтому прошу показать, как это всё делается по простому, в одной функции, на языке С++, со счётчиком сравнений... Было бы прекрасно, если бы был готовый код, в котором ничего исправлять не нужно.

Ну, все это в посте 30.

Новые блоги и статьи Все статьи Все блоги /
Транслитерация текста с кириллицы на латиницу Maks 11.11.2026 Решил облегчить жизнь себе и коллегам админам при создании электронных почтовых ящиков для пользователей, в результате написал обработку "Транслитерация текста" с кириллицы на латиницу, а в ней. . .	Книги по геймдизайну, левел-дизайну, игровым механикам и проектированию игрового опыта 8Observer8 08.11.2026 Содержание блога \| English Version 1. 2003 - 06 - Designing Virtual Worlds (1st Edition) Автор: Richard A. Bartle \| Объем: 768 стр. Ссылки: Amazon . . .	Родители токсичные абьюзеры по отношению к своим детям ругают их оскорбляют не любят zorxor 08.11.2026 Жить в атмосфере постоянных оскорблений, критики и холодности со стороны родителей — это тяжелое и болезненное испытание, которое оставляет глубокие эмоциональные раны. Токсичное и абьюзивное. . .	Как только я захожу к себе в свою комнату я сразу же с себя снимаю свои трусы. Ответ от Джемени ИИ. zorxor 08.11.2026 Джемени, как только я захожу к себе в свою комнату я сразу же с себя снимаю свои трусы. Многие люди, возвращаясь домой, сразу переодеваются в максимально свободную одежду или вовсе предпочитают. . .
Паттерн очереди действий/команд (Action / Command Queue). Система очереди действий и кат-сцен с SDL3 Callbacks, cglm и OpenGL 8Observer8 07.11.2026 Содержание блога \| English Version Руководство для начинающих по реализации паттерна очереди действий/ команд (Action / Command Queue) на C++ (C++20) с использованием официального SDL3 Callbacks. . .	Проверка полного ФИО в типовом справочнике Maks 07.11.2026 Решение реализовано в конфигурации КА2, на примере справочника "КонтактныеЛицаПартнеров". Задача: Запрет инициалов. Не допускаеть использование сокращений вида "И. И. ", "И. И. ", "И И" и. . .	Про "Windows must die!" kumehtar 04.11.2026 Знаете, чет накатило. . . . Когда-то это было почти боевым кличем: мол, нормальный человек сидит на DOS, OS/ 2 или Linux, а вот это вот - Must Die. А теперь человек произносит «мастдай» с усмешкой - и. . .	Красочные поля с номером страницы svg+background-image russiannick 04.11.2026 Красочные поля с номером страницы не менее важны чем в эпоху бумажных книг. Посему спешу представить почтеннейшей публике этот важный инструмент который эти поля и формирует. В процессе разработки. . .

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

@maxim43k 0 / 0 / 0 Регистрация: 04.09.2011 Сообщений: 106
	07.09.2011, 14:04 [ТС]
	Вроде это сортировка по возрастанию, а надо сортировку наоборот, наихудший случай 0

@maxim43k 0 / 0 / 0 Регистрация: 04.09.2011 Сообщений: 106
	07.09.2011, 16:44 [ТС]
	А как сортировка будет выглядеть на С++? Там же с потоками как-то? 0

@maxim43k 0 / 0 / 0 Регистрация: 04.09.2011 Сообщений: 106
	07.09.2011, 19:01 [ТС]
	Я про то, что запутался в разных "size_t" и т.п. Поэтому прошу показать, как это всё делается по простому, в одной функции, на языке С++, со счётчиком сравнений... Было бы прекрасно, если бы был готовый код, в котором ничего исправлять не нужно. 0