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

@maxim43k · Регистрация: 04.09.2011

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

Хочу спросить, это пузырьковая сортировка или нет? Как её правильно реализовать? Как оценить эффективность алгоритма сортировки по числу сравнений (упорядочен по возрастанию)?

C++

#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 · 06.09.2011, 22:55

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

А для оценки куда счётчик ставить? Вроде надо определить, сколько сравнений было.

Во внутренний цикл. Хотя это теоретически вычисляется.

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

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

Не по теме:

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

Не по теме:

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

@maxim43k · 06.09.2011, 22:59 **[ТС]**

Как оценить по количеству сравнений?

@Thinker · 06.09.2011, 23:01

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

Как оценить по количеству сравнений?

перед if счетчик увеличивайте

@easybudda · 06.09.2011, 23:11

C

#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 · 07.09.2011, 14:04 **[ТС]**

Вроде это сортировка по возрастанию, а надо сортировку наоборот, наихудший случай

@easybudda · 07.09.2011, 14:50

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

а надо сортировку наоборот

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

if ( arr[i] > arr[j] )

C

1	if ( arr[i] < arr[j] )

@maxim43k · 07.09.2011, 16:44 **[ТС]**

А как сортировка будет выглядеть на С++? Там же с потоками как-то?

@Thinker · 07.09.2011, 17:51

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

А как сортировка будет выглядеть на С++? Там же с потоками как-то?

Смотря что вам сортировать надо. Если массивы, то они и в Африке массивы.

@maxim43k · 07.09.2011, 18:41 **[ТС]**

Как переделать пузырёк со счётчиком к такому виду? Одна функция, язык С++? Типа такого, только с моим случаем:

C++

#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 · 07.09.2011, 18:51

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

Как переделать пузырёк со счётчиком к такому виду? Одна функция, язык С++? Типа такого, только с моим случаем:

Слушайте, но я же вам говорил, что у вас метод прямого выбора.

Добавлено через 8 минут
Или вы про это:

C++

#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 · 07.09.2011, 19:01 **[ТС]**

Я про то, что запутался в разных "size_t" и т.п. Поэтому прошу показать, как это всё делается по простому, в одной функции, на языке С++, со счётчиком сравнений... Было бы прекрасно, если бы был готовый код, в котором ничего исправлять не нужно.

@Thinker · 07.09.2011, 19:17

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

Я про то, что запутался в разных "size_t" и т.п. Поэтому прошу показать, как это всё делается по простому, в одной функции, на языке С++, со счётчиком сравнений... Было бы прекрасно, если бы был готовый код, в котором ничего исправлять не нужно.

Ну, все это в посте 30.

@Thinker 4267 / 2241 / 203 Регистрация: 26.08.2011 Сообщений: 3,802 Записей в блоге: 5
	06.09.2011, 22:55	21
	Сообщение от maxim43k А для оценки куда счётчик ставить? Вроде надо определить, сколько сравнений было. Во внутренний цикл. Хотя это теоретически вычисляется. Добавлено через 11 минут Сообщение от easybudda Не по теме: Да ну нафиг! Пузырьковая сортировка нужна только, чтобы принцип понять, ну и преподу лабораторную сдать. Если речь заходит о производительности, есть несколько более удачные алгоритмы сортировки... ;) Не по теме: Да, но мозги то зачем. Чтобы подумать и хоть немного что-то улучшить. Тем более, человек учиться пришел, а не любой ценой диплом получить. Это я в идеальном случае:) А сама эта пузырьковая сортировка и близко никуда не годится, это понятно 2

@maxim43k 0 / 0 / 0 Регистрация: 04.09.2011 Сообщений: 106
	07.09.2011, 14:04 [ТС]	25
	Вроде это сортировка по возрастанию, а надо сортировку наоборот, наихудший случай 0

@maxim43k 0 / 0 / 0 Регистрация: 04.09.2011 Сообщений: 106
	07.09.2011, 16:44 [ТС]	27
	А как сортировка будет выглядеть на С++? Там же с потоками как-то? 0

@Thinker 4267 / 2241 / 203 Регистрация: 26.08.2011 Сообщений: 3,802 Записей в блоге: 5
	07.09.2011, 17:51	28
	Сообщение от maxim43k А как сортировка будет выглядеть на С++? Там же с потоками как-то? Смотря что вам сортировать надо. Если массивы, то они и в Африке массивы. 1

@maxim43k 0 / 0 / 0 Регистрация: 04.09.2011 Сообщений: 106
	07.09.2011, 19:01 [ТС]	31
	Я про то, что запутался в разных "size_t" и т.п. Поэтому прошу показать, как это всё делается по простому, в одной функции, на языке С++, со счётчиком сравнений... Было бы прекрасно, если бы был готовый код, в котором ничего исправлять не нужно. 0

@maxim43k 0 / 0 / 0 Регистрация: 04.09.2011 Сообщений: 106
	06.09.2011, 22:59 [ТС]	22
	Как оценить по количеству сравнений? 0

@Thinker 4267 / 2241 / 203 Регистрация: 26.08.2011 Сообщений: 3,802 Записей в блоге: 5
	06.09.2011, 23:01	23
	Сообщение от maxim43k Как оценить по количеству сравнений? перед if счетчик увеличивайте 1

@Thinker 4267 / 2241 / 203 Регистрация: 26.08.2011 Сообщений: 3,802 Записей в блоге: 5
	07.09.2011, 19:17	32
	Сообщение от maxim43k Я про то, что запутался в разных "size_t" и т.п. Поэтому прошу показать, как это всё делается по простому, в одной функции, на языке С++, со счётчиком сравнений... Было бы прекрасно, если бы был готовый код, в котором ничего исправлять не нужно. Ну, все это в посте 30. 1