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

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

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 22, средняя оценка - 4.68
maxim43k
0 / 0 / 0
Регистрация: 04.09.2011
Сообщений: 106
06.09.2011, 21:39     Пузырьковая сортировка #1
Хочу спросить, это пузырьковая сортировка или нет? Как её правильно реализовать? Как оценить эффективность алгоритма сортировки по числу сравнений (упорядочен по возрастанию)?

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++
Пузырьковая сортировка C++
Сортировка пузырьковая C++
C++ Пузырьковая сортировка
C++ Пузырьковая сортировка
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 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++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
06.09.2011, 23:01     Пузырьковая сортировка #23
Цитата Сообщение от maxim43k Посмотреть сообщение
Как оценить по количеству сравнений?
перед if счетчик увеличивайте
easybudda
Модератор
Эксперт С++
 Аватар для easybudda
9373 / 5423 / 914
Регистрация: 25.07.2009
Сообщений: 10,423
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
Модератор
Эксперт С++
 Аватар для easybudda
9373 / 5423 / 914
Регистрация: 25.07.2009
Сообщений: 10,423
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++
 Аватар для Thinker
4215 / 2189 / 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++
 Аватар для Thinker
4215 / 2189 / 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++ Пузырьковая сортировка
C++ Пузырьковая сортировка

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

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

Текущее время: 02:17. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru