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

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

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

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

06.09.2011, 21:39. Просмотров 2903. Ответов 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++):

пузырьковая сортировка - C++
Пожалуйста помогите написать программу, которая выполняет сортировку исходного целочисленного массива по возрастанию и убыванию. Исходные...

Сортировка пузырьковая - C++
Привет всем!помогите отсортировать задачку. #include &lt;iostream&gt; #include &lt;iomanip&gt; using namespace std; int main() { const...

Пузырьковая сортировка - C++
Здравствуйте. Есть код, который сортирует методом пузырька по строчкам, что мне поменять, чтобы была сортировка по столбцам начиная с...

Пузырьковая сортировка - C++
Посмотрите что не так дана таблица стран с кол-вом золотых, серебряных медалей нудно отсортировать страны в порядке убывания количества...

Пузырьковая Сортировка - C++
Описать структуру с именем Train, содержащую следующие поля: Point (название пункта назначения), Number (номер поезда), Time (время...

пузырьковая сортировка - C++
Задача не сложная, но у меня нет времени ее решать: дан одномерный массив, нужно сделать пузырьковую сортировку по нему

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
maxim43k
0 / 0 / 0
Регистрация: 04.09.2011
Сообщений: 106
06.09.2011, 22:27  [ТС] #16
В том то и дело, что я не знаю, КАК оценить эффективность алгоритма сортировки по числу сравнений (массив упорядочен наоборот). Это что, счётчик какой то ставить? А куда?
easybudda
Модератор
Эксперт CЭксперт С++
9530 / 5523 / 932
Регистрация: 25.07.2009
Сообщений: 10,608
06.09.2011, 22:29 #17
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
#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'); }
 
void bublesort(int * arr, size_t size){
    size_t i, j;
    
    if ( ! arr || ! size )
        return;
        
    for ( i = 0; i < size - 1; ++i )
        for ( j = size - 1; j > i; --j )
            if ( arr[i] > arr[j] )
                swap(&arr[i], &arr[j]);
}
 
int main(void){
    int arr[] = { 3, 1, 5, 2, 4 };
    
    printf("Before: ");
    dump(arr, count(arr));
    bublesort(arr, count(arr));
    printf("After:  ");
    dump(arr, count(arr));
    
    return 0;
}
Thinker
Эксперт C++
4225 / 2199 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
06.09.2011, 22:36 #18
Цитата Сообщение от maxim43k Посмотреть сообщение
В том то и дело, что я не знаю, КАК оценить эффективность алгоритма сортировки по числу сравнений (массив упорядочен наоборот). Это что, счётчик какой то ставить? А куда?
В среднем случае для пузырьковой сортировки сложность O(n^2). Если массив упорядочен наоборот (худший случай), то сложность алгоритма n(n-1)/2, так как вычисления сводятся к сумме ряда:
1+2+...+(n-1)

Добавлено через 6 минут
easybudda, ваш алгоритм лучше оптимизировать, так как если массив в какой-то момент времени в сортировке уже не нуждается, то ее следует прекратить.
maxim43k
0 / 0 / 0
Регистрация: 04.09.2011
Сообщений: 106
06.09.2011, 22:42  [ТС] #19
А для оценки куда счётчик ставить? Вроде надо определить, сколько сравнений было.
easybudda
06.09.2011, 22:43
  #20

Не по теме:

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

Thinker
Эксперт C++
4225 / 2199 / 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++
4225 / 2199 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
06.09.2011, 23:01 #23
Цитата Сообщение от maxim43k Посмотреть сообщение
Как оценить по количеству сравнений?
перед if счетчик увеличивайте
easybudda
Модератор
Эксперт CЭксперт С++
9530 / 5523 / 932
Регистрация: 25.07.2009
Сообщений: 10,608
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
Модератор
Эксперт CЭксперт С++
9530 / 5523 / 932
Регистрация: 25.07.2009
Сообщений: 10,608
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++
4225 / 2199 / 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++
4225 / 2199 / 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;
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.09.2011, 18:51
Привет! Вот еще темы с ответами:

Пузырьковая сортировка - C++
#include &lt;iostream&gt; #include &lt;fstream&gt; using namespace std; int main() { const int n = 5; int a; ifstream...

Пузырьковая сортировка - C++
В чес дело не могу понять? Переменной массива с индексом X присваивается какое то левое значение. #include &lt;iostream&gt; #include...

Пузырьковая сортировка - C++
Есть курсовик. Есть пузырьковая сортировка Есть одно НО. Сортировка должна быть сделана через массив указателей, а не через массив...

Пузырьковая сортировка - C++
Написал программу сортировки методом пузырька: #include &lt;stdio.h&gt; #include &lt;conio.h&gt; #include &lt;cstdlib&gt; int...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
07.09.2011, 18:51
Ответ Создать тему
Опции темы

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