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

Ускорить программу сортировки списка в порядке возрастания

14.06.2017, 12:12. Показов 1267. Ответов 12

Здраствуйте!Написал код программы.Тесты не проходит из-за превышение времени работы.
Суть такова:
Вводится число n-количество троек чисел.Дальше n строк по три числа в каждой(x,y,z).Дальше нужно отсортировать список в порядке возрастания по формуле sqrt(x^2+y^2+z^2).Если корень чисел одинаковы то ставим числа в порядке возрастания(по большему x.Если х одинаковые то по у и тд.)

Число n<=10^5.
Числа x,y,z<=10^9.


Необходимое время 800мс.
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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include <iostream>
#include <cmath>
using namespace std;
 
int main ()
{
    long long n;
    cin >> n;
    long long arr[n][3];
    float arr1[n];
    for(int i=0; i<n; i++)
    {
        cin>>arr[i][0]>>arr[i][1]>>arr[i][2];
        arr1[i]=sqrt(arr[i][0]*arr[i][0]+arr[i][1]*arr[i][1]+arr[i][2]*arr[i][2]);
    }
    for(int i=0; i<n; i++)
    {
        for(int xi=0; xi<n; xi++)
        {
            if(arr1[i]<arr1[xi])
            {
                swap(arr1[i],arr1[xi]);
                swap(arr[i][3],arr[xi][3]);
                swap(arr[i][2],arr[xi][2]);
                swap(arr[i][1],arr[xi][1]);
                swap(arr[i][0],arr[xi][0]);
            }
            else if(arr1[i]==arr1[xi])
            {
                if(arr[i][3]<arr[xi][3])
                {
                    swap(arr1[i],arr1[xi]);
                    swap(arr[i][3],arr[xi][3]);
                    swap(arr[i][2],arr[xi][2]);
                    swap(arr[i][1],arr[xi][1]);
                    swap(arr[i][0],arr[xi][0]);
                }
                else  if(arr[i][3]==arr[xi][3])
                {
                    if(arr[i][2]<arr[xi][2])
                    {
                        swap(arr1[i],arr1[xi]);
                        swap(arr[i][3],arr[xi][3]);
                        swap(arr[i][2],arr[xi][2]);
                        swap(arr[i][1],arr[xi][1]);
                        swap(arr[i][0],arr[xi][0]);
                    }
                    else  if(arr[i][2]==arr[xi][2])
                    {
                        if(arr[i][1]<arr[xi][1])
                        {
                            swap(arr1[i],arr1[xi]);
                            swap(arr[i][3],arr[xi][3]);
                            swap(arr[i][2],arr[xi][2]);
                            swap(arr[i][1],arr[xi][1]);
                            swap(arr[i][0],arr[xi][0]);
                        }
                        else if(arr[i][1]==arr[xi][1])
                        {
                            if(arr[i][0]<arr[xi][0])
                            {
                                swap(arr1[i],arr1[xi]);
                                swap(arr[i][3],arr[xi][3]);
                                swap(arr[i][2],arr[xi][2]);
                                swap(arr[i][1],arr[xi][1]);
                                swap(arr[i][0],arr[xi][0]);
                            }
                        }
                    }
                }
            }
        }
    }
    for(int i=0; i<n; i++)
    {
        cout<<arr[i][0]<<" "<<arr[i][1]<<" "<<arr[i][2]<<endl;
 
    }
    return 0;
}
__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
14.06.2017, 12:12
Ответы с готовыми решениями:

Разработать программу быстрой сортировки в порядке возрастания ключей.
Разработать программу быстрой сортировки в порядке возрастания ключей.

Создать программу сортировки массива в порядке возрастания его элементов
Создать программу сортировки массива А в порядке возрастания его элементов методом вставки, если...

Написать программу, упорядочивающую массив строк в порядке возрастания длины их первого слова методом пузырьковой сортировки
Доброго времени суток, Прошу помочь с задачей: Написать программу, упорядочивающую массив строк в...

Составить программу для упорядочения в порядке возрастания элементов однонаправленного списка
составить программу для упорядочения в порядке возростания элементов однонаправленного списка

12
Диссидент
Эксперт C
26839 / 16746 / 3670
Регистрация: 24.12.2010
Сообщений: 37,492
14.06.2017, 12:21 2
ERW1N, Вы сортируете методом пузырька? (или даже чем-то еще похуже)
Из всех известных методов сортировки "Пузырек" - один из самых медленных. Примените что-нибудь вроде метода Шелла.
1
Форумчанин
Эксперт CЭксперт С++
8190 / 5040 / 1437
Регистрация: 29.11.2010
Сообщений: 13,453
14.06.2017, 12:34 3
Скиньте ссылку на задачу, чтобы можно было решения попробовать
0
0 / 0 / 1
Регистрация: 29.10.2016
Сообщений: 71
14.06.2017, 12:39  [ТС] 4
Не выйдет,сервер закрытый мне просто доступ открыли.
0
Форумчанин
Эксперт CЭксперт С++
8190 / 5040 / 1437
Регистрация: 29.11.2010
Сообщений: 13,453
14.06.2017, 12:51 5
Вот так по идее должно быстрее работать. Можно ещё попробовать пихать в вектор, а потом сортировать. Хотя и данный вариант должен для n<=10^5 укладываться
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <cmath>
#include <iostream>
#include <map>
#include <tuple>
 
double Foo(const int x, const int y, const int z)
{
    return sqrt(x*x + y*y + z*z);
}
 
int main()
{
    size_t N;
    std::cin >> N;
    int x, y, z;
    std::multimap<double, std::tuple<int, int, int>> m;
    for (size_t i = 0; i < N && std::cin >> x >> y >> z; i++)
        m.emplace(Foo(x, y, z), std::make_tuple(x, y, z));
    for (const auto &p : m)
        std::cout << std::get<0>(p.second) << " " << std::get<1>(p.second) << " " << std::get<2>(p.second) << std::endl;
}
Добавлено через 6 минут
Второй вариант решения:
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
#include <algorithm>
#include <cmath>
#include <iostream>
#include <vector>
 
struct A
{
    A(const int x_, const int y_, const int z_) : x(x_), y(y_), z(z_), p(sqrt(x*x + y*y + z*z)) {}
    int x, y, z;
    double p;
};
 
int main()
{
    size_t N;
    std::cin >> N;
    int x, y, z;
    std::vector<A> v;
    v.reserve(N);
    for (size_t i = 0; i < N && std::cin >> x >> y >> z; i++)
        v.emplace_back(x, y, z);
    std::sort(v.begin(), v.end(), [](const A &lhs, const A &rhs) { return lhs.p < rhs.p; });
    for (const auto &a : v)
        std::cout << a.x << " " << a.y << " " << a.z << std::endl;
}
1
0 / 0 / 1
Регистрация: 29.10.2016
Сообщений: 71
14.06.2017, 12:52  [ТС] 6
error This file requires compiler and library support for the \
ISO C++ 2011 standard. This support is currently experimental, and must be \
enabled with the -std=c++11 or -std=gnu++11 compiler options.
0
Форумчанин
Эксперт CЭксперт С++
8190 / 5040 / 1437
Регистрация: 29.11.2010
Сообщений: 13,453
14.06.2017, 12:53 7
ERW1N, там явно написано что нужно во флаги компилятора добавить -std=c++11 чтобы включить поддержку 11 стандарта
1
0 / 0 / 1
Регистрация: 29.10.2016
Сообщений: 71
14.06.2017, 12:59  [ТС] 8
Угу.Понял.Ток ща буду пробовать доделать)Если корень чисел одинаковый то ставим числа в порядке возрастания(по меньшему x.Если х одинаковые то по у и тд.)Прошло 0/100.Но думаю дело именно в одинаковых корнях

Добавлено через 1 минуту
Подскажите где именно эту поправку нужно вставить??
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
#include <algorithm>
#include <cmath>
#include <iostream>
#include <vector>
 
struct A
{
    A(const int x_, const int y_, const int z_) : x(x_), y(y_), z(z_), p(sqrt(x*x + y*y + z*z)) {}
    int x, y, z;
    double p;
};
 
int main()
{
    size_t N;
    std::cin >> N;
    int x, y, z;
    std::vector<A> v;
    v.reserve(N);
    for (size_t i = 0; i < N && std::cin >> x >> y >> z; i++)
        v.emplace_back(x, y, z);
    std::sort(v.begin(), v.end(), [](const A &lhs, const A &rhs) { return lhs.p < rhs.p; });
    for (const auto &a : v)
        std::cout << a.x << " " << a.y << " " << a.z << std::endl;
}
0
Форумчанин
Эксперт CЭксперт С++
8190 / 5040 / 1437
Регистрация: 29.11.2010
Сообщений: 13,453
14.06.2017, 13:11 9
Лучший ответ Сообщение было отмечено ERW1N как решение

Решение

Вынес компаратор в отдельную функцию т.к. теперь там большое условие. Можете экспериментировать с условием как угодно.
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
#include <algorithm>
#include <cmath>
#include <iostream>
#include <vector>
 
struct A
{
    A(const int x_, const int y_, const int z_) : x(x_), y(y_), z(z_), p(sqrt(x*x + y*y + z*z)) {}
    int x, y, z;
    double p;
};
 
bool operator<(const A &lhs, const A &rhs)
{
    if (fabs(lhs.p - rhs.p) > 1e-08)
        return lhs.p < rhs.p;
    if (lhs.x != rhs.x)
        return lhs.x < rhs.x;
    if (lhs.y != rhs.y)
        return lhs.y < rhs.y;
    return lhs.z < rhs.z;
}
 
int main()
{
    size_t N;
    std::cin >> N;
    int x, y, z;
    std::vector<A> v;
    v.reserve(N);
    for (size_t i = 0; i < N && std::cin >> x >> y >> z; i++)
        v.emplace_back(x, y, z);
    std::sort(v.begin(), v.end());
    for (const auto &a : v)
        std::cout << a.x << " " << a.y << " " << a.z << std::endl;
}
Добавлено через 6 минут
Кстати, если система не 64-битная, то int для
Цитата Сообщение от ERW1N Посмотреть сообщение
<=10^9
может не хватить. Правильнее наверное использовать int32_t
1
0 / 0 / 1
Регистрация: 29.10.2016
Сообщений: 71
14.06.2017, 13:13  [ТС] 10
0/100Попробуйю сделать как байт говорил,изменить сортировку надеюсь поможет
0
Форумчанин
Эксперт CЭксперт С++
8190 / 5040 / 1437
Регистрация: 29.11.2010
Сообщений: 13,453
14.06.2017, 13:23 11
Лучший ответ Сообщение было отмечено ERW1N как решение

Решение

ERW1N, вы тип данных пробовали сменить?
0
0 / 0 / 1
Регистрация: 29.10.2016
Сообщений: 71
14.06.2017, 13:29  [ТС] 12
По идее можно и long long верно???

Добавлено через 2 минуты
Спасибо вам!!!!Пойду свечу вам в церковь поставлюВек вам буду благодарен)))))))
0
Форумчанин
Эксперт CЭксперт С++
8190 / 5040 / 1437
Регистрация: 29.11.2010
Сообщений: 13,453
14.06.2017, 13:31 13
Лучший ответ Сообщение было отмечено ERW1N как решение

Решение

Спасибо
1
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
14.06.2017, 13:31
Помогаю со студенческими работами здесь

Расставить элементы массива в порядке возрастания методом сортировки выбором и сортировки простыми вставками
Здрасьте еще раз!С прошедшим вас праздником! я глупая и бестолковая опять пришла к вам на...

Функция сортировки массива в порядке возрастания методом вставки
Помогите написать: 1)Написать функцию сортировки массива в порядке возрастания методом вставки.

Вывести элементы массива построчно в порядке возрастания без сортировки
помогите пожалуйста написать программу на Visual! Напишите программу на C++/CLI, которая создает...

Составить функцию сортировки значений трех переменных а, b, с в порядке возрастания
Составить функцию сортировки значений трех переменных а, b, с в порядке возрастания. Использовать...


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

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

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