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

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

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

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

06.09.2011, 21:39. Просмотров 2864. Ответов 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++
Задача не сложная, но у меня нет времени ее решать: дан одномерный массив, нужно сделать пузырьковую сортировку по нему

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Thinker
Эксперт C++
4221 / 2195 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
06.09.2011, 22:55     Пузырьковая сортировка #21
Цитата Сообщение от maxim43k Посмотреть сообщение
А для оценки куда счётчик ставить? Вроде надо определить, сколько сравнений было.
Во внутренний цикл. Хотя это теоретически вычисляется.

Добавлено через 11 минут
Цитата Сообщение от easybudda Посмотреть сообщение

Не по теме:


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

Не по теме:

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

maxim43k
0 / 0 / 0
Регистрация: 04.09.2011
Сообщений: 106
06.09.2011, 22:59  [ТС]     Пузырьковая сортировка #22
Как оценить по количеству сравнений?
Thinker
Эксперт C++
4221 / 2195 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
06.09.2011, 23:01     Пузырьковая сортировка #23
Цитата Сообщение от maxim43k Посмотреть сообщение
Как оценить по количеству сравнений?
перед if счетчик увеличивайте
easybudda
Эксперт С++
9456 / 5469 / 927
Регистрация: 25.07.2009
Сообщений: 10,495
06.09.2011, 23:11     Пузырьковая сортировка #24
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
0 / 0 / 0
Регистрация: 04.09.2011
Сообщений: 106
07.09.2011, 14:04  [ТС]     Пузырьковая сортировка #25
Вроде это сортировка по возрастанию, а надо сортировку наоборот, наихудший случай
easybudda
Эксперт С++
9456 / 5469 / 927
Регистрация: 25.07.2009
Сообщений: 10,495
07.09.2011, 14:50     Пузырьковая сортировка #26
Цитата Сообщение от maxim43k Посмотреть сообщение
а надо сортировку наоборот
Цитата Сообщение от easybudda Посмотреть сообщение
if ( arr[i] > arr[j] )
C
1
if ( arr[i] < arr[j] )
maxim43k
0 / 0 / 0
Регистрация: 04.09.2011
Сообщений: 106
07.09.2011, 16:44  [ТС]     Пузырьковая сортировка #27
А как сортировка будет выглядеть на С++? Там же с потоками как-то?
Thinker
Эксперт C++
4221 / 2195 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
07.09.2011, 17:51     Пузырьковая сортировка #28
Цитата Сообщение от maxim43k Посмотреть сообщение
А как сортировка будет выглядеть на С++? Там же с потоками как-то?
Смотря что вам сортировать надо. Если массивы, то они и в Африке массивы.
maxim43k
0 / 0 / 0
Регистрация: 04.09.2011
Сообщений: 106
07.09.2011, 18:41  [ТС]     Пузырьковая сортировка #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
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
Эксперт C++
4221 / 2195 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
07.09.2011, 18:51     Пузырьковая сортировка #30
Цитата Сообщение от 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
0 / 0 / 0
Регистрация: 04.09.2011
Сообщений: 106
07.09.2011, 19:01  [ТС]     Пузырьковая сортировка #31
Я про то, что запутался в разных "size_t" и т.п. Поэтому прошу показать, как это всё делается по простому, в одной функции, на языке С++, со счётчиком сравнений... Было бы прекрасно, если бы был готовый код, в котором ничего исправлять не нужно.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.09.2011, 19:17     Пузырьковая сортировка
Еще ссылки по теме:

пузырьковая сортировка - 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...


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

Или воспользуйтесь поиском по форуму:
Thinker
Эксперт C++
4221 / 2195 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
07.09.2011, 19:17     Пузырьковая сортировка #32
Цитата Сообщение от maxim43k Посмотреть сообщение
Я про то, что запутался в разных "size_t" и т.п. Поэтому прошу показать, как это всё делается по простому, в одной функции, на языке С++, со счётчиком сравнений... Было бы прекрасно, если бы был готовый код, в котором ничего исправлять не нужно.
Ну, все это в посте 30.
Yandex
Объявления
07.09.2011, 19:17     Пузырьковая сортировка
Ответ Создать тему
Опции темы

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