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

Сортировка массивов - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 20, средняя оценка - 4.85
Toshkarik
 Аватар для Toshkarik
1139 / 856 / 50
Регистрация: 03.08.2011
Сообщений: 2,381
Завершенные тесты: 1
08.10.2011, 11:46     Сортировка массивов #1
Приветствую всех. Делаю задание из учебника Дейтелов.
Задания:
7.11. (Пузырьковая сортировка) В алгоритме пузырьковой сортировки меньшие
значения постепенно «всплывают» к началу массива подобно пузырькам в воде, в то
время как большие значения опускаются «на дно». Пузырьковая сортировка
выполняет несколько проходов по массиву. На каждом проходе сравниваются пары
смежных элементов. Если порядок элементов в паре восходящий (или элементы
идентичны), мы оставляем их так, как есть. Если порядок элементов
нисходящий, их значения в массиве обмениваются. Напишите программу,
сортирующую массив из 10 целых чисел посредством пузырьковой сортировки.
7.12. Пузырьковая сортировка, представленная в упражнении 7.11, неэффективна
для больших массивов. Выполните следующие простые модификации для
улучшения эффективности пузырьковой сортировки.
a) После первого прохода наибольшее число гарантированно окажется в
элементе массива с наивысшим номером; после второго прохода «на месте» окажутся
два наибольших числа и так далее. Модифицируйте пузырьковую сортировку
так, чтобы вместо выполнения девяти сравнений на каждом проходе на
втором проходе было восемь сравнений, на третьем проходе — семь и так далее.
b) Данные в массиве могут уже находиться в необходимом порядке, либо
близком к нему, так зачем же делать девять проходов, если достаточно сделать
меньше? Модифицируйте сортировку так, чтобы в конце каждого прохода
проверялось, были ли сделаны какие-либо перестановки. Если не было ни
одной, значит, данные уже находятся в соответствующем порядке, так что
программа должна завершиться. Если перестановки были сделаны, нужно
сделать, по меньшей мере, еще один проход.


Первое сделал
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
template< typename T >
void swap( T &x, T &y )
{
    T temp = x;
    x = y;
    y = temp;
}
 
template< typename T >
void arrSort( T arr[], const long long &size )
{
    for ( int i = 0; i < size; i++ )
        for ( int j = 1; j < size; j++ )
            if ( arr[ j ] < arr[ j - 1 ] )
                swap ( arr[ j ], arr[ j - 1 ] );
}
Из второго задания часть а.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
template< typename T >
void arrSort( T arr[], const long long &size )
{
    int max;
    int temp = size - 1;
 
    for ( int i = 0; i < size; i++, temp-- )
    {
        max = 0;
 
        for ( int j = 0; j <= temp; j++ )
            if ( arr[ j ] > arr[ max ] )
                max = j;
 
        swap ( arr[ max ], arr[ temp ] );
    }
}
Не могу понять, как сделать часть b. Подскажите, пожалуйста. И поправьте если я что не так сделал в предыдущих. Спасибо.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
hijacker7
19 / 19 / 1
Регистрация: 06.10.2011
Сообщений: 53
08.10.2011, 12:24     Сортировка массивов #2
Вот как-то так:
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
08.10.2011, 12:26     Сортировка массивов #3
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
void arrSort( T arr[], const long long &size )
{
           int flag = 1;
           while (flag)
           {
                   flag = 0;
                   for ( int j = 1; j < size; j++ )
                        if ( arr[ j ] < arr[ j - 1 ] )
                        {
                                swap ( arr[ j ], arr[ j - 1 ] );
                                flag = 1;
                        }
           }
}
-=ЮрА=-
Заблокирован
Автор FAQ
08.10.2011, 12:30     Сортировка массивов #4
Toshkarik, почитайте здесь Алгоритмы сортировок
Toshkarik
 Аватар для Toshkarik
1139 / 856 / 50
Регистрация: 03.08.2011
Сообщений: 2,381
Завершенные тесты: 1
08.10.2011, 12:35  [ТС]     Сортировка массивов #5
Thinker, Спасибо, я опять задание не правильно понял, думал, что нужно к а) прибавить б). Оказывается это две разные модификации.

-=ЮрА=-, Спасибо, но я видел это. Когда делаешь сам, лучше усваивается.
rangerx
1908 / 1517 / 139
Регистрация: 31.05.2009
Сообщений: 2,876
08.10.2011, 13:52     Сортировка массивов #6
Цитата Сообщение от Toshkarik Посмотреть сообщение
И поправьте если я что не так сделал в предыдущих
Цитата Сообщение от Toshkarik Посмотреть сообщение
void arrSort( T arr[], const long long &size )
Для работы с массивами есть специальный тип size_t, использовать long long для указания размера массива неверно. Плюс ко всему ты ещё и сравниваешь переменную типа long long с переменной типа int внутри функции... И нет особого смысла делать парметр встроенного типа константной ссылкой.
Toshkarik
 Аватар для Toshkarik
1139 / 856 / 50
Регистрация: 03.08.2011
Сообщений: 2,381
Завершенные тесты: 1
08.10.2011, 14:10  [ТС]     Сортировка массивов #7
rangerx, по поводу size_t, разве это относится к С-массивам? Вроде как я понял это к векторам, в любом случае в книги данный вопрос слегка был затронут на небольшом ознакомлении с классом vector. А по поводу long long, спасибо, и в правду что то сглупил. Где то увидел в примере long long или просто long и решил написать так же.
rangerx
1908 / 1517 / 139
Регистрация: 31.05.2009
Сообщений: 2,876
08.10.2011, 14:40     Сортировка массивов #8
Дело не в том массив это или вектор. Подробнее смотри здесь.
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
08.10.2011, 16:28     Сортировка массивов #9
Toshkarik, ваша реализация под буквой a - сортировка прямым выбором в чистом виде. Имелось вот что в виду:

C++
1
2
3
4
5
6
7
8
9
10
11
void arrSort( T arr[], const long long &size )
{
       int r = size; 
       for ( int i = 0; i < size; i++ )
       {
                for ( int j = 1; j < r; j++ )
                        if ( arr[ j ] < arr[ j - 1 ] )
                                swap ( arr[ j ], arr[ j - 1 ] );
                r--;
       }
}
Toshkarik
 Аватар для Toshkarik
1139 / 856 / 50
Регистрация: 03.08.2011
Сообщений: 2,381
Завершенные тесты: 1
08.10.2011, 17:43  [ТС]     Сортировка массивов #10
rangerx, спасибо большое, более-менее понятно.

Thinker, получается просто нужно декрементировать переменную в условии цикла? В этом вся "модификация"?
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
08.10.2011, 18:07     Сортировка массивов
Еще ссылки по теме:

C++ Обработка одномерных массивов. Сортировка массивов
Сортировка 2-х массивов C++
Сортировка массивов C++

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

Или воспользуйтесь поиском по форуму:
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
08.10.2011, 18:07     Сортировка массивов #11
Цитата Сообщение от Toshkarik Посмотреть сообщение
Thinker, получается просто нужно декрементировать переменную в условии цикла? В этом вся "модификация"?
Именно так.
Yandex
Объявления
08.10.2011, 18:07     Сортировка массивов
Ответ Создать тему
Опции темы

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