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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 20, средняя оценка - 4.85
Toshkarik
1141 / 858 / 51
Регистрация: 03.08.2011
Сообщений: 2,384
Завершенные тесты: 1
#1

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

08.10.2011, 11:46. Просмотров 2568. Ответов 10
Метки нет (Все метки)

Приветствую всех. Делаю задание из учебника Дейтелов.
Задания:
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. Подскажите, пожалуйста. И поправьте если я что не так сделал в предыдущих. Спасибо.
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
08.10.2011, 11:46
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Сортировка массивов (C++):

Обработка одномерных массивов. Сортировка массивов - C++
Здравствуйсте! Помогите пожалуйста написать программу! В одномерном массиве, состоящем из n вещественных элементов, вычислить: 1)...

Обработка одномерных массивов. Сортировка массивов - C++
Здравствуйте, помогите пожалуйста решить задачу легким способом. В одномерном массиве, состоящем из n вещественных элементов, вычислить: ...

Сортировка массивов (?) - C++
Суть задания, в принципе, простая - есть три книги, написанные тремя авторами и содержащие разное кол-во страниц. Предлагается...

Сортировка 2-х массивов - C++
Вопрос очень простой, я забыл как из 2-х массивов получить 3-ий, что бы в нём присутствовали только элементы первого массива. Т.е. что бы...

Сортировка массивов - C++
Добрый день. Помогите, пожалуйста разобраться с задачей: Дан массив случайных чисел в диапазоне от -20 до +20 (из 20 элементов)....

Сортировка массивов. - C++
Помогите пожалуйста написать на 2006 с++ сортировки одномерного массива методом Шелла, Шейкера, слиянием, быстрой сортировки по примеру...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
hijacker7
20 / 20 / 1
Регистрация: 06.10.2011
Сообщений: 53
08.10.2011, 12:24 #2
Вот как-то так:
0
Thinker
Эксперт C++
4226 / 2200 / 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;
                        }
           }
}
1
-=ЮрА=-
Заблокирован
Автор FAQ
08.10.2011, 12:30 #4
Toshkarik, почитайте здесь Алгоритмы сортировок
0
Toshkarik
1141 / 858 / 51
Регистрация: 03.08.2011
Сообщений: 2,384
Завершенные тесты: 1
08.10.2011, 12:35  [ТС] #5
Thinker, Спасибо, я опять задание не правильно понял, думал, что нужно к а) прибавить б). Оказывается это две разные модификации.

-=ЮрА=-, Спасибо, но я видел это. Когда делаешь сам, лучше усваивается.
0
rangerx
1933 / 1542 / 141
Регистрация: 31.05.2009
Сообщений: 2,912
08.10.2011, 13:52 #6
Цитата Сообщение от Toshkarik Посмотреть сообщение
И поправьте если я что не так сделал в предыдущих
Цитата Сообщение от Toshkarik Посмотреть сообщение
void arrSort( T arr[], const long long &size )
Для работы с массивами есть специальный тип size_t, использовать long long для указания размера массива неверно. Плюс ко всему ты ещё и сравниваешь переменную типа long long с переменной типа int внутри функции... И нет особого смысла делать парметр встроенного типа константной ссылкой.
1
Toshkarik
1141 / 858 / 51
Регистрация: 03.08.2011
Сообщений: 2,384
Завершенные тесты: 1
08.10.2011, 14:10  [ТС] #7
rangerx, по поводу size_t, разве это относится к С-массивам? Вроде как я понял это к векторам, в любом случае в книги данный вопрос слегка был затронут на небольшом ознакомлении с классом vector. А по поводу long long, спасибо, и в правду что то сглупил. Где то увидел в примере long long или просто long и решил написать так же.
0
rangerx
1933 / 1542 / 141
Регистрация: 31.05.2009
Сообщений: 2,912
08.10.2011, 14:40 #8
Дело не в том массив это или вектор. Подробнее смотри здесь.
0
Thinker
Эксперт C++
4226 / 2200 / 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--;
       }
}
0
Toshkarik
1141 / 858 / 51
Регистрация: 03.08.2011
Сообщений: 2,384
Завершенные тесты: 1
08.10.2011, 17:43  [ТС] #10
rangerx, спасибо большое, более-менее понятно.

Thinker, получается просто нужно декрементировать переменную в условии цикла? В этом вся "модификация"?
0
Thinker
Эксперт C++
4226 / 2200 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
08.10.2011, 18:07 #11
Цитата Сообщение от Toshkarik Посмотреть сообщение
Thinker, получается просто нужно декрементировать переменную в условии цикла? В этом вся "модификация"?
Именно так.
1
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
08.10.2011, 18:07
Привет! Вот еще темы с ответами:

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

Сортировка массивов в С - C++
Люди помогите) как отсортировать одномерный статический рандомный массив по возрастанию без использования указателей? ...

сортировка массивов - C++
есть массив состоящие, допустим, из 10 элементов. нужно написать программу которая сортирует массив по порядку, чтобы сначала были...

Сортировка массивов - C++
Создать массив случайных чисел(данные массива+-int).Сделать сортировку обменом. Потом за усложненным правилом сделать сортировку - сначала...


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

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

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