Упорядочение координат - PullRequest
Новая
       4

Упорядочение координат

2 голосов
/ 25 марта 2012

Предположим, у меня есть n баллов 

(x,y1),(x2,y2),.....(xn,yn)

Моя цель - соединить эти точки таким образом, чтобы я получил сплайн без самопересечения. Мой метод состоит в том, чтобы упорядочить эти элементы путем увеличения порядка значений x и, если они равны, сравнить значения y. Вот мой метод: 

#include<iostream>
#include<ctime>

using namespace std;
#define N  1000
struct  Point
{
    int x;
    int y;

}point[N];
int main()
{
    int start=clock();
    int n;
    cout<<" enter  number of coordinantes " <<endl;
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>point[i].x>>point[i].y;

    for(int i=1;i<=n-1;i++){
        for(int j=i+1;j<=n;j++)
        {
            if(point[i].x>point[j].x)
            {
                int t=point[i].x;
                point[i].x=point[j].x;
                point[j].x=t;

            }
            if( point[i].x==point[j].x)
            {

                if(point[i].y>point[j].y)
                {
                    int s=point[i].y;
                    point[i].y=point[j].y;
                    point[j].y=s;
                }
                }


            }

    }
    int end=clock();
    cout<<"coordinantes are :"<<endl;
    for(int i=1;i<=n;i++)
        cout<<point[i].x<<" "<<point[i].y<<endl;
    cout<<(end-start)/(float)CLOCKS_PER_SEC<<endl;
    return 0;
}

Когда я ввел число элементов, равное 20, это заняло 102,59 миллисекунды (ноутбук с 2,5 ОЗУ, 1,87 ГГц). Является ли мой метод оптимальным или существует лучший метод?

Ответы [ 3 ]

3 голосов
/ 25 марта 2012

Узким местом в вашем алгоритме является сортировка - O(n^2). Это можно сделать в O(nlogn), что асимптотически намного лучше.

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

Также обратите внимание, что с условной точки зрения - обычно это хорошая практика для разделения между частями вашей программы - в вашем случае - разделения между сортировкой и последующим обходом.

Для сортировки вы, возможно, захотите взглянуть на std::sort() и, возможно, захотите ознакомиться с быстрой сортировкой

1 голос
/ 25 марта 2012

Если вас беспокоит производительность, я укажу на эти вещи:

1) Вы используете 1000 элементов - потеря памяти.Используйте * point & do malloc для требуемого количества элементов.

2) Вы не используете точку [0] в своей текущей реализации - потеря памяти!; -)

3) Как уже говорили другие, ваш алгоритм сортировки - не лучший выбор.

когда я ввел номер элемента 20, это заняло 102,59 миллисекунд (ноутбук с 2,5 ОЗУ, 1.87 GH), поэтому оптимальный способ

обработки 20 элементов не скажет об эффективности алгоритма.Выборка должна быть достаточно большой, чтобы разумно тестировать программу.

0 голосов
/ 28 марта 2012

Продолжая сортировку, вы можете сортировать по собственным критериям сравнения. 

boolean compare(Point A, Point B) {
   return ((A.x > B.x)||((A.x==B.x)&&(A.y>B.y)));
}

(извините за синтаксис ... Мой C ++ ржавый)

Затем вы выполните сортировку, используяхорошо реализованный алгоритм, такой как std :: sort и эта функция в качестве порядка сравнения.

...