0 / 0 / 0
Регистрация: 13.05.2017
Сообщений: 2
1

Сортировка через один

13.05.2017, 15:46. Показов 5101. Ответов 6
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Напишите программу, которая сортирует по возрастанию все элементы массива с нечётными номерами. При этом все элементы с чётными номерами должны остаться на своих местах. Нумерация элементов массива начинается с единицы.

Входные данные
Первая строка содержит размер массива N . Во второй строке через пробел задаются N чисел – элементы массива. Гарантируется, что 0 < N ≤ 100000 .

Выходные данные
Программа должна вывести все элементы отсортированного массива в одну строку, разделив их пробелами.

Примеры
входные данные
6
6 5 4 3 2 1
выходные данные
2 5 4 3 6 1


В тестирующей системе программа выполняет только первые 11 из 22 тестов. В остальных пишется "Ошибка во время выполнения программы".
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
#include <fstream>
#include <cstdlib>
using namespace std;
int main()
{
    ifstream input("input.txt");
    ofstream output("output.txt");
    int c, n;
    int a[10000] = {};
    input >> n;
    for (int i = 1; i <=n; i++)
    {
        input >> a[i];
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j<n-1; j++)
        {
            if (j & 1)
            {
                if (a[j] > a[j + 2])
                {
                    
                    c = a[j];
                    a[j] = a[j + 2];
                    a[j + 2] = c;
                }
            }
        }
    }
    for (int i = 1; i <= n; i++)
    {
        output << a[i] << " ";
    }
    input.close();
    output.close();
    return 0;
}
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
13.05.2017, 15:46
Ответы с готовыми решениями:

Через какое минимальное количество точек можно провести один и только один эллипс?
Здравствуйте. Если я не ошибаюсь, то по трём точкам, не лежащим на одной прямой, можно построить...

Получение инета через один Wi-Fi адаптер, а раздача через другой
Приветствую всех форумчан. Облизал весь инет и перепробовал кучу софта и разных методов но так и...

Выбрать через JOIN только один столбец и запихнуть его в ячейку через GROUP_CONCAT
Select *, GROUP_CONCAT(OtherTable.Id) FROM MainTable LEFT OUTER JOIN OtherTable...

Сортировка n количества столбцов в один
Добрый день! Имеется файл с n количеством столбцов и заполненных в них n количеством строк. ...

6
3 / 3 / 6
Регистрация: 12.03.2013
Сообщений: 25
13.05.2017, 15:56 2
Может просто в массиве идти через два шага?
заместо i++, i+=2
0
0 / 0 / 0
Регистрация: 13.05.2017
Сообщений: 2
13.05.2017, 16:49  [ТС] 3
Цитата Сообщение от jekkery Посмотреть сообщение
Может просто в массиве идти через два шага?
заместо i++, i+=2
Не выходит, результат тот же.
В программе во время прохождения теста происходит какая-то ошибка. Т.к. при неверном ответе система пишет "Неправильный ответ", а у меня выходит "Ошибка во время выполнения программы".
Миниатюры
Сортировка через один   Сортировка через один  
0
3 / 3 / 6
Регистрация: 12.03.2013
Сообщений: 25
13.05.2017, 18:03 4
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
#include <iostream>
 
using namespace std;
 
int main()
{
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    int c, n;
    int a[10000];
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
 
    for (int i = 0; i < n - 1; i+=2) {
        for (int j = 0; j < n - i - 2; j+=2) {
            if (a[j] > a[j + 2]) {
                swap(a[j], a[j+2]);
            }
        }
    }
 
 
    for (int i = 0; i < n; i++)
    {
        cout  << a[i] << " ";
    }
 
    return 0;
}
Добавлено через 10 минут
Не правильно прочитал условие 0 < N ≤ 100000
int a[100000];

сейчас надо сократить время работы

Добавлено через 43 минуты
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
#include <iostream>
 
using namespace std;
 
int main()
{
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    int c = 0;
    int n;
    int a[100000], b[100000];
    cin >> n;
 
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
 
    if (n % 2 != 1) {
        for (int i = 0; i <= n / 2 - 1; i++) {
            b[i] = a[i * 2];
            c++;
        }
    }
    else {
        for (int i = 0; i <= n / 2; i++) {
            b[i] = a[i * 2];
            c++;
        }
    }
 
 
    for (int i = 0; i <= n * 2 + 1; i++) {
        a[i*2] = b[i];
    }
 
    for (int i = 0; i < c - 1; i++) {
        for (int j = 0; j < c - i - 1; j++) {
            if (b[j] > b[j + 1]) {
                swap(b[j], b[j + 1]);
            }
        }
    }
    for (int i = 0; i <= n / 2; i++) {
        a[i * 2] = b[i];
    }
    
 
 
    for (int i = 0; i < n; i++)
    {
        cout << a[i] << " ";
    }
    return 0;
}
Не хватает каких то 052 секунды, какие еще методы сокращения операций я не в курсе, тут уже вопросы к профессионалам
1
2780 / 1933 / 570
Регистрация: 05.06.2014
Сообщений: 5,598
13.05.2017, 18:37 5
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
struct Pair
{
    bool operator<(const Pair&value)const{return x<value.x;}
    Pair&operator=(const Pair&value)
    {
        x=value.x;
        return*this;
    }
 
    int x,y;
};
 
int main()
{
    Pair buf[]={{6,5},{4,3},{2,1}};
    std::sort(buf,buf+sizeof(buf)/sizeof(buf[0]));
    for(int i=0;i<sizeof(buf)/sizeof(buf[0]);++i)
        std::cout<<buf[i].x<<" "<<buf[i].y<<" ";
    return 0;
}
Добавлено через 3 минуты
Цитата Сообщение от jekkery Посмотреть сообщение
сейчас надо сократить время работы
Цитата Сообщение от jekkery Посмотреть сообщение
swap(b[j], b[j + 1]);
Пузырек. Квадратичная сложность. Этим все сказано.
2
3 / 3 / 6
Регистрация: 12.03.2013
Сообщений: 25
13.05.2017, 18:43 6
Цитата Сообщение от Renji Посмотреть сообщение
Пузырек. Квадратичная сложность. Этим все сказано.
Кстати бы, я совсем не подумал)
0
142 / 143 / 64
Регистрация: 11.11.2010
Сообщений: 876
Записей в блоге: 10
13.05.2017, 20:59 7
Лучший ответ Сообщение было отмечено fafwb как решение

Решение

С разбиением массива при вводе.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <algorithm>
 
int main()
{
    int N;
    std::cin >> N;
    vector<int> even( ( N + 1 ) / 2 ), odd( N / 2 );
    for( int i = 0; i < N / 2; i++ )
        std::cin >> even[i] >> odd[i];
    if( N%2 == 1 )
        std::cin >> even[N/2];
 
   std::sort( even.begin(), even.end() );
 
    for( int i = 0; i < N / 2; i++ )
        std::cout << even[i] << odd[i];
    if( N%2 == 1 )
        std::cout << even[N/2];
}
1
13.05.2017, 20:59
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
13.05.2017, 20:59
Помогаю со студенческими работами здесь

Сортировка массива за один проход
помогите пожалуйста с задачей , хоть какие-нибудь варианты -- Переместить в целочисленном массиве...

Сортировка массива за один проход
Помогите. Нужно отсортировать массив так, чтобы справа были отрицательные, слева положительные и...

Сортировка в один проход по нескольким полям
Добрый вечер, #include &lt;iostream&gt; #include &lt;ctime&gt; #include &lt;vector&gt; #include &lt;algorithm&gt;...

Сделать один цикл while. Сортировка пузырьком c#
using System; using System.Diagnostics; using System.Collections.Generic; using System.Linq;...


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

Или воспользуйтесь поиском по форуму:
7
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru