Сортировка Пузырьком

@Sh_a_man · Регистрация: 10.09.2016

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

Здравствуйте!
Пытался выполнить задание:
Сортировка Пузырьком - один из простейших способов осуществления такого упорядочивания. Мы опишем её даже немного проще чем обычно:

Сделайте проход по массиву, проверяя каждую пару соседних элементов (N-1 пара в массиве из N элементов).
Если в какой-то паре с индексами indexes i и i+1 обнаруживается что a[i] <= a[i+1] - т.е. больший элемент идёт раньше - меняем эти два элемента местами.
Повторяем такие "проходы" до тех пор пока не окажется что за весь проход ничего не поменяли.
Очевидно, что если на протяжении прохода по массиву ни одну пару не пришлось обменять, то массив уже отсортирован и последующие проходы ничего не изменят.

Для обмена элементов с индексами i и j существует несколько вариантов. Классический способ основан на использовании вспомогательной переменной t - вот так:

t = a[i]
a[i] = a[j]
a[j] = t
Входные данные указывают размер массива в первой строке - и элементы массива во второй (целые числа через пробел).
Ответ должен содержать два значения - количество проходов которые потребовались для того чтобы отсортировать массив по вышеописанному алгоритму - и суммарное количество обменов элементов (во всех этих проходах).

Пример:

входные данные:
8
3 1 4 1 5 9 2 6

ответ:
5 8
Заметьте что количество проверок пар (и количество обменов) приблизительно пропорционально N^2 где N это размер массива так что время затрачиваемое алгоритмом растёт гораздо быстрее чем размер массива - поэтому такой способ на практике используется только для небольших массивов (или в качестве составной части более сложных алгоритмов).

Я не понимаю как мне делать сортировку...я привык делать так:

C++
1
2
3
4
5
6
7
    for (int i = 0; i < numbers_of_line; i++)  
        for (int j = numbers_of_line - 1; j > i; j--)
            if (array_for_sort[j - 1] > array_for_sort[j])
            {
                int temp = array_for_sort[j - 1];
                array_for_sort[j - 1] = array_for_sort[j]; 
                array_for_sort[j] = temp;}

Когда делал как они хотят,у меня массив сортировался наполовину...или вообще зацикливался.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
while (changed){
        changed = false;
        for (int j = 0; j <= number_of_lines; j++)
        {
            if (array_of_numbers[j] <=  array_of_numbers[j + 1])
            {
                int tmp = array_of_numbers[j];
                array_of_numbers[j] = array_of_numbers[j + 1];
                array_of_numbers[j + 1] = tmp; changed = true;
                flag1++; 
            }
        }
        flag++;
    }

Можете подсказать,пожалуйста,что делать. Может я задание не так понимаю...

@likehood · 01.08.2017, 17:48

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

for (int j = 0; j <= number_of_lines; j++)

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

array_of_numbers[j + 1]

Здесь происходит выход за границу массива, причём дважды.

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

C++
1
if (array_of_numbers[j] <= array_of_numbers[j + 1])

Нестрогое неравенство <= нужно заменить на строгое <. Зачем менять местами два одинаковых элемента?

@Sh_a_man · 01.08.2017, 18:03 **[ТС]**

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

Зачем менять местами два одинаковых элемента?

Я и сам не понимаю, просто выходные данные у меня не сходятся...вот и пытаюсь их "подогнать".

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

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

Здесь происходит выход за границу массива, причём дважды.

Упс

Да,тут надо

C++
1
for (int j = 0; j < number_of_lines-1; j++)

Добавлено через 7 минут
likehood,
Спасибо,теперь не зацикливается,но выходные данные (количество обменов и количество проходов) не сходятся

Добавлено через 2 минуты
Во время этих сортировок количество обменов и количество проходов намного больше,чем должно быть в ответе

@likehood · 01.08.2017, 18:21

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

количество обменов и количество проходов намного больше,чем должно быть в ответе

Возможно проблема в другом месте программы.

@Sh_a_man · 01.08.2017, 18:32 **[ТС]**

likehood, не в том месте прибавляю?)

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
#include "stdafx.h"
#include <iostream>
 
int _tmain()
{
    int number_of_lines(0);
    std::cin >> number_of_lines;
    
    int* array_of_numbers = (int*)calloc(number_of_lines, sizeof(int));
 
    for (int i = 0; i < number_of_lines; i++)
        std::cin >> array_of_numbers[i];
 
    int flag(0);
    int flag1(0);
    bool changed = true;
    while (changed){
        changed = false;
        for (int j = 0; j < number_of_lines-1; j++)
        {
            if (array_of_numbers[j] <  array_of_numbers[j + 1])
            {
                int tmp = array_of_numbers[j];
                array_of_numbers[j] = array_of_numbers[j + 1];
                array_of_numbers[j + 1] = tmp; changed = true;
                flag1++; 
                flag += 2;
            }
        }
    }
    for (int i = 0; i < number_of_lines; i++)
        std::cout << array_of_numbers[i];
    std::cout << " " << flag1 << " " << flag;
    system("pause");
    return 0;
}

@likehood · 01.08.2017, 18:45

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

C++
27
flag += 2;

В первом варианте было по-другому, и было больше похоже на правду.

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .	Конвертировать закладки radiotray-ng в m3u-плейлист damix 19.02.2026 Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .	Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI Eddy_Em 18.02.2026 Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .
И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»	SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .

Сортировка Пузырьком

Решение

Решение