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

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

Восстановить пароль Регистрация
 
stuxjkee
0 / 0 / 0
Регистрация: 18.04.2014
Сообщений: 15
01.05.2014, 20:35     Сортировка разворотом #1
Необходим отсортировать входной массив, используя только операции разворота первых k елементов.
Необходимо вывести количество таких разворотов и каждое такое k
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
01.05.2014, 20:35     Сортировка разворотом
Посмотрите здесь:

C++ сортировка
C++ Сортировка.
C++ Сортировка подсчетом и LSD сортировка
C++ сортировка
шейкерная сортировка + сортировка слиянием C++
Пирамидальная сортировка и сортировка Шелла C++
Сортировка методом "быстрая сортировка" C++
C++ Сортировка Хоара / Быстрая сортировка

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
malyuta
1 / 1 / 1
Регистрация: 04.05.2014
Сообщений: 6
04.05.2014, 10:09     Сортировка разворотом #2
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Для решения этой задачи необходимо в цикле искать максимальный элемент и делать развороты, тем самым перемещая максимальный элемент сначала на первую позицию, а затем в конец (перед элементами, которые больше текущего максимального элемента).

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <iostream>
#include <string>
 
using namespace std;
 
int main() {
    int length;
    cin >> length;
    int *data = new int[length];
 
    string list = "";
 
    for (int i = 0; i < length; ++i)
        cin >> data[i];
 
    int imax = 0, max = data[0];
    int tleng = length, swap;
 
    while(tleng > 1) {
        for(int i = 1; i < tleng; ++i) {
            if (data[i] > max) {
                max = data[i];
                imax = i;
            }
        }
 
        if(imax == tleng-1) {
            --tleng;
            imax = 0;
            max = data[0];
            continue;
        }
        else {
            if(imax != 0) {
                for(int i = 0; i <= imax/2; ++i) {
                    swap = data[i];
                    data[i] = data[imax-i];
                    data[imax-i] = swap;
                }
                list += imax+1;
            }
            for(int i = 0; i < tleng/2; ++i) {
                swap = data[i];
                data[i] = data[tleng-i-1];
                data[tleng-i-1] = swap;
            }
            list += tleng;
            --tleng;
            imax = 0;
            max = data[0];
        }
    }
    cout << list.size() << endl;
    for(int i = 0; i < list.size(); ++i)
        cout << (int)list[i] << " ";
    return 0;
}
Yandex
Объявления
04.05.2014, 10:09     Сортировка разворотом
Ответ Создать тему
Опции темы

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