Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > C/C++ программирование > Общие вопросы C/C++
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 15.12.2015, 16:56   #1
Мефала
 
Аватар для Мефала
 
Регистрация: 14.12.2015
Сообщений: 6
По умолчанию Алгоритмы сортировки

Всем добрый день!
На досуге решила тут реализовать на плюсах некоторые алгоритмы сортировок. Интерсует критика, мнения и всё такое, ибо новичёк.
Может кому-то будет полезно - буду рада.

1. Сортировка вставками
Код:
#include <iostream>
#include <vector>
#include <ctime>

void sort_mas(std::vector <int>& m)
{
    for (int i = 2; i < m.size(); ++i)
    {
        int key = m[i];
        int j = i - 1;
        while ((j > 0)&&(m[j] > key))
        {
            m[j + 1] = m[j];
            j -= 1;
        }
         m[j + 1] = key;
    }
    if (m[0] > m[1]) 
    {
        int temp = m[1];
        m[1] = m[0];
        m[0] = temp;
    }
}

int main()
{
    srand(time(NULL));
    std::vector <int> mas;
    for(int i = 0; i < 5; ++i)
    {
        mas.push_back(rand()%10);
        std::cout << " " << mas[i];
    }
    std::cout << std::endl;
    sort_mas(mas);

    for (int i = 0; i < mas.size(); ++i)
        std::cout << " " << mas[i];
    system("pause>nul");
}
2. Сортировка пузырьком

Код:
#include <iostream>
#include <vector>
#include <ctime>

void bubble_sort(std::vector <int>& vec)
{
    int count = 0, temp = 0;
    for (int i = 0; i < vec.size() - 1 ; ++i)
    {
        if (vec[i + 1] < vec[i])
        {
            temp = vec[i];
            vec[i] = vec[i + 1];
            vec[i + 1] = temp;
            ++count;
        }
    }
    if (count != 0)
        bubble_sort(vec);
}

int main()
{
    srand(time(NULL));
    size_t size = 20;
    std::vector <int> v;
    for (int i = 0; i < size; ++i)
    {
        v.push_back(rand()%20);
        std::cout << v[i] << " ";
    }
    bubble_sort(v);
    std::cout << std::endl;
    for (int i = 0; i < size; ++i)
        std::cout << v[i] << " ";
    system("pause>nul");
}
И в процессе ещё сортировка выбором... И другие сортировки тоже.
Cat.

Последний раз редактировалось Мефала; 15.12.2015 в 17:00.
Мефала вне форума Ответить с цитированием
Старый 15.12.2015, 17:21   #2
Serge_Bliznykov
Старожил
 
Регистрация: 09.01.2008
Сообщений: 26,238
По умолчанию

Зачем в сортировке пузырьком использовать рекурсию? ЗАЧЕМ?!!!
Неужели простой обычный, БАНАЛЬНЫЙ цикл чем-то Вас не устроил?!!
Serge_Bliznykov вне форума Ответить с цитированием
Старый 15.12.2015, 17:25   #3
Stilet
Белик Виталий :)
Старожил
 
Аватар для Stilet
 
Регистрация: 23.07.2007
Сообщений: 57,792
По умолчанию

Цитата:
std::vector <int>& vec
Для STL есть уже процедуры сортировки, их не нужно реализовывать.
Цитата:
Интерсует критика
А почему пузырек рекурсией если не секрет?
I'm learning to live...
Stilet вне форума Ответить с цитированием
Старый 15.12.2015, 17:27   #4
Мефала
 
Аватар для Мефала
 
Регистрация: 14.12.2015
Сообщений: 6
По умолчанию

Цитата:
Сообщение от Serge_Bliznykov Посмотреть сообщение
Зачем в сортировке пузырьком использовать рекурсию? ЗАЧЕМ?!!!
Неужели простой обычный, БАНАЛЬНЫЙ цикл чем-то Вас не устроил?!!
Зачем столько нервов? Я ведь просто мнение спросила... Перепишу под цикл, если не съедите.

Цитата:
Сообщение от Stilet Посмотреть сообщение
А почему пузырек рекурсией если не секрет?
Показалось проще... Но уже почитала про "съедение стэка" и все дела, так что исправлю, спасибо.
Cat.

Последний раз редактировалось Stilet; 15.12.2015 в 17:39.
Мефала вне форума Ответить с цитированием
Старый 15.12.2015, 17:41   #5
Stilet
Белик Виталий :)
Старожил
 
Аватар для Stilet
 
Регистрация: 23.07.2007
Сообщений: 57,792
По умолчанию

Цитата:
Показалось проще...
Ну я бы не сказал. Сделай тогда все на рекурсии.
Цитата:
Но уже почитала про "съедение стэка"
Ну я бы не кивал на проблему со стеком. При количестве данных, что такая сортировка обрабатывает нагружать ей огромные массивы врядли кто-то станет. Сам смысл такого гибрида как-то бессмысленен.
I'm learning to live...
Stilet вне форума Ответить с цитированием
Старый 15.12.2015, 17:43   #6
Мефала
 
Аватар для Мефала
 
Регистрация: 14.12.2015
Сообщений: 6
По умолчанию

Цитата:
Сообщение от Stilet Посмотреть сообщение
Ну я бы не сказал. Сделай тогда все на рекурсии.
А можете рассказать подробнее, если не сложно? Чем рекурсия хуже или лучше?
Cat.
Мефала вне форума Ответить с цитированием
Старый 15.12.2015, 17:50   #7
Smitt&Wesson
Старожил
 
Аватар для Smitt&Wesson
 
Регистрация: 31.05.2010
Сообщений: 13,964
По умолчанию

Цитата:
Зачем в сортировке пузырьком использовать рекурсию? ЗАЧЕМ?!!!
Неужели простой обычный, БАНАЛЬНЫЙ цикл чем-то Вас не устроил?!!
Серж. Ну, учится человек. Сразу бить по морде, не камильфо.

Мефала, не обижайся на него.

Цитата:
А можете рассказать подробнее, если не сложно? Чем рекурсия хуже или лучше?
В программировании нет понятий хуже и лучше. Есть понятие - эффективно. Если для одной задачи эффективна рекурсияч, для другой, она может быть совершенно неприемлема.
Рекурсия, занимает стек. У стека, есть глубина. Самое "страшное", когда Вы, не понимая этого, вгоняете машину в бесконечность (рекурсивная функция с ошибкой из выхода из ней). В этом - проблема рекурсии. С другой стороны, сортировка пузырьком и рекурсия, это - нонсенс. Обмен через стек, не самое эффективное, что можно придумать.
Пиши пьяным, редактируй трезвым.
Справочник по алгоритмам С++ Builder

Последний раз редактировалось Smitt&Wesson; 15.12.2015 в 18:04.
Smitt&Wesson вне форума Ответить с цитированием
Старый 15.12.2015, 18:04   #8
Serge_Bliznykov
Старожил
 
Регистрация: 09.01.2008
Сообщений: 26,238
По умолчанию

Извините за излишнюю резкость.
Обидеть я не хотел.
Просто "пузырёк" - это самый простой и примитивный алгоритм.
примеров реализации на всех языках полным полно.
Даже видео с танцем про пузырёк было.

А рекурсия - это ЗЛО.
Ей нужно пользоваться ТОЛЬКО тогда,
когда без неё обойтись очень сложно, алгоритм получается сложный, запутанный и, главное, притянутый за уши.
Ну, например, обход дерева, файловой структуры - тут, конечно, рекурсия будет к месту. Но вставлять её туда, где она не нужна - не надо!
Serge_Bliznykov вне форума Ответить с цитированием
Старый 15.12.2015, 18:08   #9
Мефала
 
Аватар для Мефала
 
Регистрация: 14.12.2015
Сообщений: 6
По умолчанию

Цитата:
Сообщение от Smitt&Wesson Посмотреть сообщение
Серж. Ну, учится человек. Сразу бить по морде, не камильфо.

Мефала, не обижайся на него.

В программировании нет понятий хуже и лучше. Есть понятие - эффективно. Если для одной задачи эффективна рекурсияч, для другой, она может быть совершенно неприемлема.
Рекурсия, занимает стек. У стека, есть глубина. Самое "страшное", когда Вы, не понимая этого, вгоняете машину в бесконечность (рекурсивная функция с ошибкой из выхода из ней). В этом - проблема рекурсии. С другой стороны, сортировка пузырьком и рекурсия, это - нонсенс. Обмен через стек, не самое эффективное, что можно придумать.
Фух... Аж комфортнее стало... Спасибо за поддержку.
И за информацию!

Цитата:
Сообщение от Serge_Bliznykov Посмотреть сообщение
А рекурсия - это ЗЛО.
Ей нужно пользоваться ТОЛЬКО тогда,
когда без неё обойтись очень сложно, алгоритм получается сложный, запутанный и, главное, притянутый за уши.
Ну, например, обход дерева, файловой структуры - тут, конечно, рекурсия будет к месту. Но вставлять её туда, где она не нужна - не надо!
Буду знать, спасибо!
Cat.

Последний раз редактировалось Stilet; 15.12.2015 в 21:05.
Мефала вне форума Ответить с цитированием
Старый 15.12.2015, 21:09   #10
Stilet
Белик Виталий :)
Старожил
 
Аватар для Stilet
 
Регистрация: 23.07.2007
Сообщений: 57,792
По умолчанию

Цитата:
Чем рекурсия хуже или лучше?
Да не хуже она и не лучше. Вопрос в уместности. Ну например ты же не ездишь на тракторе на работу? или в Универ, или где ты там обретаешься...
Ты ездишь на автобусе. Вот так же и рекурсия. Где-то она уместна, где-то не очень.
Смешивать рекурсию и цикл для решения задач, где можно обойтись одним циклом, это бессмысленно, и наоборот.
Так что Смитт почти верно все сказал за исключением менеджеров рекурсий. Они в разных языках себя по разному ведут, и не все из них вообще работают загружая стек. Некоторые оптимизируются. Вообще это оч. хороша описано в старых учебниках по Лиспу.
I'm learning to live...
Stilet вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Алгоритмы сортировки Cи Панdopa Помощь студентам 6 17.06.2015 15:06
Ошибка.Алгоритмы сортировки.Язык си. East Undia Trading Помощь студентам 6 14.05.2014 22:42
Алгоритмы сортировки пирамидальный(кучей) и быстрой сортировки (с++) mmd12 Помощь студентам 4 17.05.2012 14:14
Алгоритмы сортировки массивов С++ Sunless Помощь студентам 1 29.03.2011 17:10
C++ алгоритмы сортировки 1ok Помощь студентам 5 18.09.2010 15:27