0 / -1 / 1
Регистрация: 10.09.2016
Сообщений: 115
1

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

01.08.2017, 17:39. Показов 1507. Ответов 5
Метки array, c, sort (Все метки)

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

Сделайте проход по массиву, проверяя каждую пару соседних элементов (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++;
    }
Можете подсказать,пожалуйста,что делать. Может я задание не так понимаю...
__________________
Помощь в написании контрольных, курсовых и дипломных работ здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
01.08.2017, 17:39
Ответы с готовыми решениями:

Сортировка пузырьком
Задача: При диспансеризации школьников определялись их рост и вес. В результате были получены...

сортировка пузырьком
#include &lt;cstdlib&gt; #include &lt;iostream&gt; #include &lt;ctime&gt; using namespace std; int main(int...

сортировка пузырьком
Вечер добрый! Задача проста: отсортировать сначала по зп, если &lt; 400, то в 1ый список, а если...

Сортировка пузырьком
#include &lt;stdio.h&gt; #include &lt;iostream&gt; #include &lt;conio.h&gt; #define M 10 void main() { int...

5
1265 / 1023 / 469
Регистрация: 25.12.2016
Сообщений: 3,331
01.08.2017, 17:48 2
Лучший ответ Сообщение было отмечено Sh_a_man как решение

Решение

Цитата Сообщение от 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])
Нестрогое неравенство <= нужно заменить на строгое <. Зачем менять местами два одинаковых элемента?
1
0 / -1 / 1
Регистрация: 10.09.2016
Сообщений: 115
01.08.2017, 18:03  [ТС] 3
Цитата Сообщение от likehood Посмотреть сообщение
Зачем менять местами два одинаковых элемента?
Я и сам не понимаю, просто выходные данные у меня не сходятся...вот и пытаюсь их "подогнать".

Добавлено через 1 минуту
Цитата Сообщение от likehood Посмотреть сообщение
Здесь происходит выход за границу массива, причём дважды.
Упс Да,тут надо
C++
1
for (int j = 0; j < number_of_lines-1; j++)
Добавлено через 7 минут
likehood,
Спасибо,теперь не зацикливается,но выходные данные (количество обменов и количество проходов) не сходятся

Добавлено через 2 минуты
Во время этих сортировок количество обменов и количество проходов намного больше,чем должно быть в ответе
0
1265 / 1023 / 469
Регистрация: 25.12.2016
Сообщений: 3,331
01.08.2017, 18:21 4
Цитата Сообщение от Sh_a_man Посмотреть сообщение
количество обменов и количество проходов намного больше,чем должно быть в ответе
Возможно проблема в другом месте программы.
0
0 / -1 / 1
Регистрация: 10.09.2016
Сообщений: 115
01.08.2017, 18:32  [ТС] 5
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;
}
0
1265 / 1023 / 469
Регистрация: 25.12.2016
Сообщений: 3,331
01.08.2017, 18:45 6
Лучший ответ Сообщение было отмечено Sh_a_man как решение

Решение

Цитата Сообщение от Sh_a_man Посмотреть сообщение
C++
27
flag += 2;
В первом варианте было по-другому, и было больше похоже на правду.
1
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
01.08.2017, 18:45

Сортировка пузырьком
Можете помочь? Программа в консоли: Спросить у пользователя 5 чисел и сохранить их в массив....

Сортировка пузырьком
#include &quot;stdafx.h&quot; #include &lt;iostream&gt; using namespace std; int main() { const int n =...

Сортировка пузырьком
#include &lt;iostream&gt; #include &lt;iomanip&gt; #include &lt;ctime&gt; using namespace std; void Sort(int *,...

Сортировка пузырьком
Нужно осортировать методом пузырька по 4 столбцу (который я как смог добавил криво косо так как в...

Сортировка пузырьком
Подскажите как мне показать(вывести) пары чисел расположенные наиболее рядом? #include...

Сортировка пузырьком
Здравствуйте! Решаю задачу:пользователь вводит слова через пробел,я должен вывести их в алфавитном...


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

Или воспользуйтесь поиском по форуму:
6
Ответ Создать тему
Опции темы

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