1

Тема: Алгоритми сортування: "камінець" і "бульбашка"

1. Поясніть, будь ласка, різницю між алгоритмами сортування "камінець" і "бульбашка". Як на мене, вони однакові, тільки один для сортування по-зростанню, а другий по-спаданню. Але викладач задав задачі, в одній потрібно використати "бульбашка" і сортувати за спаданням та зростанням, а в іншій - "камінець".
2. Я спробувала запрограмувати один алгоритм, теоретично це мав бути "бульбашка"

void bubbleSort(T mas[], int size)
{
    T swap;
    for (int i = 0; i < size - 1; i++)
    {
        for (int j = i; j < size - 1 - i; j++)
        {
            if (mas[j] > mas[j + 1])
            {
                swap = mas[j];
                mas[j] = mas[j + 1];
                mas[j + 1] = swap;
            }
        }
    }
}

Чи справді це так?

2

Re: Алгоритми сортування: "камінець" і "бульбашка"

1. Вашому викладачу краще б розказати про щось корисніше за різні назви одного і того ж алгоритму.
2. Я б сказав, що це сортування «камінцем», тому що «важкі» елементи швидко «тонуть». Але тут 50/50.

3

Re: Алгоритми сортування: "камінець" і "бульбашка"

Ніколи раніше не чув про сортування «камінцем». Викладач узагалі посилається на якусь літературу, де цей алгоритм описується, чи це його власний винахід, усі матеріали про який — лише в конспектах його лекцій?

Подякували: 0xDADA11C71

4 Востаннє редагувалося koala (26.08.2015 05:47:29)

Re: Алгоритми сортування: "камінець" і "бульбашка"

Алгоритми повністю симетричні і призначені для одного й того самого, основне питання - чи йде рух у внутрішньому циклі вниз чи вгору.
Ваша програма - це зламана бульбашка. Сортування не працює, ви лишаєте на початку масиву великі елементи.
Якщо кортить зробити щось більш-менш оригінальне - зробіть сортування змішуванням: спершу підіймаємо найбільший, потім - спускаємо найменший, потім знову підіймаємо...

5

Re: Алгоритми сортування: "камінець" і "бульбашка"

koala, сортування працює: масив впорядковується по-зростанню.

Прихований текст

http://i.imgur.com/EHO1LRP.png

Тільки я не знаю чи правильно зрозуміла суть алгоритму.

6

Re: Алгоритми сортування: "камінець" і "бульбашка"

Спробуйте на масиві  {100,10,1,2,3}

7

Re: Алгоритми сортування: "камінець" і "бульбашка"

koala, дякую, я вже виправила. Це правильно?

template <typename T>
void bubbleSort(T mas[], int size)
{
    T swap;
    for (int i = 0; i < size - 1; i++)
    {
        for (int j = 0; j < size - 1 - i; j++)
        {
            if (mas[j] > mas[j + 1])
            {
                swap = mas[j];
                mas[j] = mas[j + 1];
                mas[j + 1] = swap;
            }
        }
    }
}

8 Востаннє редагувалося koala (26.08.2015 14:31:20)

Re: Алгоритми сортування: "камінець" і "бульбашка"

Ніби так. Бульбашка.
Дам пораду: проголошуйте змінну там, де вона використовується:

            if (mas[j] > mas[j + 1])
            {
                T swap = mas[j];
                mas[j] = mas[j + 1];
                mas[j + 1] = swap;
            }

чи використовуйте стандартні функції

#include<algorithm>
...
            if (mas[j] > mas[j + 1])
            {
                std::swap( mas[j], mas[j + 1] ) ;
            }
Подякували: pika19891

9

Re: Алгоритми сортування: "камінець" і "бульбашка"

Дякую. І ще питання тоді "камінець" це як? Так як "бульбашка", тільки йти від кінця масиву?

10 Востаннє редагувалося koala (26.08.2015 14:32:11)

Re: Алгоритми сортування: "камінець" і "бульбашка"

Так. І обережно з границями циклів - внутрішній має йти до 0, потім до 1 і т.д.

11

Re: Алгоритми сортування: "камінець" і "бульбашка"

Я вас правильно зрозуміла?

Прихований текст
void stoneSort(T mas[], int size)
{
    bool swap = true;
    while (swap)
    {
        for (int i = 0; i < size - 1; i++)
        {
            swap = false;
            for (int j = size - 1; j >= i; j--)
            {
                if (mas[j - 1] > mas[j])
                {
                    T temp = mas[j];
                    mas[j] = mas[j - 1];
                    mas[j - 1] = temp;
                    swap = true;
                }
            }
        }
    }
}

12 Востаннє редагувалося koala (26.08.2015 14:50:20)

Re: Алгоритми сортування: "камінець" і "бульбашка"

Перевірте ще раз границі циклів. Зокрема, кінець внутрішнього.

А нащо вам swap?

13

Re: Алгоритми сортування: "камінець" і "бульбашка"

Бульбашкове сортування

14 Востаннє редагувалося pika1989 (26.08.2015 17:19:08)

Re: Алгоритми сортування: "камінець" і "бульбашка"

koala написав:

А нащо вам swap?

Це я перевіряла одну теорію, яку знайшла в неті, і просто забула видалити. *PARDON*

koala написав:

Перевірте ще раз границі циклів. Зокрема, кінець внутрішнього.

Здається все працює. Це впорядкування елементів за зростанням, а якщо треба за спаданням, то достатньо змінити умову?

15

Re: Алгоритми сортування: "камінець" і "бульбашка"

Не все працює. Перевірте випадок i = 0, j = 0. Що з чим буде порівнюватися?
І так, достатньо змінити умову.

16

Re: Алгоритми сортування: "камінець" і "бульбашка"

koala, я вам дуже дякую за терпіння і допомогу.
Я, здається,  зрозуміла, у внутрішньому циклі потрібно зробити так

for (int j = size - 1; j >= i + 1; j--)

17

Re: Алгоритми сортування: "камінець" і "бульбашка"

j > i трохи простіше виглядає :)

Подякували: pika19891

18

Re: Алгоритми сортування: "камінець" і "бульбашка"

Зрозуміла, дуже і дуже дякую