Сортировка структуры

@Senarist · Регистрация: 14.03.2014

Всем привет. Нужна помощь при сортировке. Во время сортировки углов нужно так же отсортировать их координаты чтобы каждая координата соответствовала своему углу до сортировки. У самого получился какой то бред с выходом за границы массива. double b[], double c[] массивы хранящие координаты x и y соответственно, а double *a массив хранящий углы.

C++

#include<iostream>
#include<stack>
#include<algorithm>
#include<windows.h>
#include<cmath>
#include<cstdlib>
 
using namespace std;
const double PI = 3.14159265;
 
//============================================//
 
struct hull
{
    int x;
    int y;
};
 
 
void Sort(double *a, double b[], double c[], const int n)
{
    
    int k = 0, u = 0;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            
            if (a[j] > a[i])
            {
                double l = a[i];
                a[i] = a[j];
                a[j] = l;
 
            }
            else
                k++;
            
        }
        u++;
    }
    cout <<"k ="<< k - u << endl;
    for (int i = 0; i < n; i++)
    {
        if ((i + k - u) >(n - 1))
            k = fabs(k - i + 1);
        else
            k = k - u;
        cout << a[i] << " координата х " << b[i + k] << endl;
    }
    /*for (int j = 0; j < n; j++)
    {
        cout << "number " << j << " ";
        cout << a[j] << " " << b[j] <<  endl;
 
    }  */
 
}
int main()
{
    setlocale(0, "");
    int N;
    std::cout << "Введите количество точек: ";
    std::cin >> N;
 
    hull *ps = new hull[N];
 
    for (int i = 0; i < N; i++)
    {
        std::cin >> (ps + i)->x;
        std::cin >> (ps + i)->y;
 
    }
    double y0 = ps->y;
    double x0 = ps->x;
 
    for (int i = 0; i < N; i++)
    {
        if ((ps + i)->y < y0)
        {
            y0 = (ps + i)->y;
            x0 = (ps + i)->x;
 
        }
 
    }
    double *x = new double[N];
    double *y = new double[N];
 
    double *ps2 = new double[N];
    for (int i = 0; i < N; i++)
    {
        ps2[i] = atan2(((ps + i)->y) - y0, ((ps + i)->x) - x0) * 180 / PI;
        x[i] = (ps + i)->x;
        y[i] = (ps + i)->y;
 
    }
    for (int i = 0; i < N; i++)
        cout << ps2[i] << endl;
 
    Sort(ps2, x, y, N);
 
    /*int j;
    for (j = 0; j < N; j++)
    {
    cout << "number " << j << " ";
    cout << ps2[j] << endl;
 
    } */
 
 
    delete[] y;
    delete[] x;
 
    delete[] ps2;
    delete[] ps;
    system("pause");
    return 0;
}

@Dimension · 20.10.2015, 17:12

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

@SuperKir · 20.10.2015, 17:17

А почему просто не сделать структуру, содержащую в себе все элементы?

C++

struct Name
{
    double angle;
    double x;
    double y;
};

И по полю Угол(angle) произвести сортировку структур.

@Senarist · 20.10.2015, 17:26 **[ТС]**

SuperKir
т.е тогда нужна в этом:

C++

1 2	double x = new double[N]; double y = new double[N];

отпадет?

@Dimension · 20.10.2015, 17:33

нет ,хранить данные то надо ,для структуры выделить придется

@SuperKir · 20.10.2015, 17:37

Dimension, что, простите?
Senarist, тебе нужно будет только N структур задать, не более. Дальше уже заполнять их поля

C++

1
2
3

Name *Param = new Name[N]; //name в данном случае имя структуры
for (int i=0; i<N; i++)
    cin >> Param[i].angel >> Param[i].x >> Param[i].y;

Ну а дальше обычная сортировка (тем же пузырьком), где буферной переменной будет переменная типа стуктуры.

@Senarist · 20.10.2015, 17:41 **[ТС]**

C++

1	hull *ps = new hull[N];

Так вот для структуры. То что выше это просто чтобы удобнее с координатами было работать.

Добавлено через 3 минуты
SuperKir Эмм.. так мне ток надо координаты вводить а угол считается на основе самой нижней точки по y, и каждой последующей. Обход грэхэма пытаюсь реализовать.

@SuperKir · 20.10.2015, 17:47

Senarist, Так, давай тогда по порядку. (Честно, не охото разбирать весь код).

1. Вводим кол-во точек
2. Выделяем память под N координат (x,y) этих точек
3. Заполняем координаты.

Что происходит далее?

@Senarist · 20.10.2015, 18:01 **[ТС]**

Далее берем самую первую структуру и начинаем искать минимальную из всех по y.

C++

double y0 = ps->y;
    double x0 = ps->x;
 
    for (int i = 0; i < N; i++)
    {
        if ((ps + i)->y < y0)
        {
            y0 = (ps + i)->y;
            x0 = (ps + i)->x;
 
        }
 
    }

Далее ищем углы из этой точки во все остальные: (ps2 хранит углы в градусах)

C++

double *ps2 = new double[N];
    for (int i = 0; i < N; i++)
    {
        ps2[i] = atan2(((ps + i)->y) - y0, ((ps + i)->x) - x0) * 180 / PI;

далее соответствующие координаты заносим в массив:

C++

1 2	x[i] = (ps + i)->x; y[i] = (ps + i)->y;

Хотя наверное можно и было оставаться со структурой

Далее
Начинаем сортировку

C++

1	Sort(ps2, x, y, N);

Сортируем по возрастанию угла:

C++

void Sort(double *a, double b[], double c[], const int n)
{
    
    //int k = 0, u = 0;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            
            if (a[j] > a[i])
            {
                double l = a[i];
                a[i] = a[j];
                a[j] = l;
 
            }

Но поскольку мы углы отсортировали, их координаты (соответствующие углу) стали не в том порядке. Вот в это проблема. Чтобы по углу мы могли знать координаты.

@Dimension · 20.10.2015, 18:16

в 12 строчке когда начинаете переставлять углы ,точно так же координаты переставляйте

C++

if (a[j] > a[i])
{
 swap(a[i],a[j]);
 swap(b[i],b[j]);
  swap(c[i],c[j]);
                
}

@SuperKir · 20.10.2015, 18:18

Сообщение от Senarist

Сортируем по возрастанию угла:

Ладно, судя по коду, очень много лишнего, ну да ладно.

C++

if (a[j] > a[i])
{
    double l = a[i];
    a[i] = a[j];
    a[j] = l;
    double buf = x[i];
    x[i] = x[j];
    x[j] = buf;
    buf = y[i];
    y[i] = y[j];
    y[j] = buf;
}

@Senarist · 20.10.2015, 18:28 **[ТС]**

SuperKir Спасибо. Можете конкретно что я лишнего сделал. Буду редактировать

@SuperKir · 20.10.2015, 18:47

Сообщение от Senarist

SuperKir Спасибо. Можете конкретно что я лишнего сделал. Буду редактировать

Зачем вводить лишние массивы x,y, если у нас есть готовые структуры, чем мы и можем воспользоваться.
Не особо понял, что и зачем ты сортировал, поэтому убрал лишнее (для себя, оставил только сортировку)

C++

#include "iostream"
 
using namespace std;
const double PI = 3.14159265;
 
//============================================//
 
struct hull
{
    int x;
    int y;
};
 
 
void Sort(double *a, hull *b, const int n)
{
 
    int k = 0, u = 0;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
 
            if (a[j] > a[i])
            {
                double l = a[i];
                a[i] = a[j];
                a[j] = l;
                hull buf = b[i];
                b[i] = b[j];
                b[j] = buf;
            }
        }
    }
    for (int i = 0; i < n; i++)
        cout << a[i] << " координаты х,y: [" << b[i].x << "," << b[i].y << "]" << endl;
}
 
int main()
{
    setlocale(0, "");
    int N;
    cout << "Введите количество точек: ";
    cin >> N;
 
    hull *ps = new hull[N];
 
    for (int i = 0; i < N; i++)
        cin >> ps[i].x >> ps[i].y;
 
    double x0 = ps->x;
    double y0 = ps->y;
 
    for (int i = 0; i < N; i++)
    {
        if (ps[i].y < y0)
        {
            y0 = ps[i].y;
            x0 = ps[i].x;
        }
 
    }
 
    double *ps2 = new double[N];
    for (int i = 0; i < N; i++)
        ps2[i] = atan2(ps[i].y - y0, ps[i].x - x0) * 180 / PI;
 
    for (int i = 0; i < N; i++)
        cout << ps2[i] << endl;
 
    Sort(ps2, ps, N);
 
    delete[] ps2;
    delete[] ps;
 
    system("pause");
    return 0;
}

Да и это можно сократить

@Senarist · 20.10.2015, 22:19 **[ТС]**

SuperKir а можешь подсказать если знаешь: как проверить образуют ли 3 точки левый поворот? Это обход Грэхема (если вдруг знаешь такое). Везде описан алгоритм который вроде понятен но как проверять какой поворот не ясно.

@Dimension Dimension 580 / 448 / 223 Регистрация: 08.04.2014 Сообщений: 1,710
	20.10.2015, 17:12	2
	пузырьковую сортировку напишите и когда обмениваете углы там же меняйте и координаты 0

@Dimension Dimension 580 / 448 / 223 Регистрация: 08.04.2014 Сообщений: 1,710
	20.10.2015, 17:33	5
	нет ,хранить данные то надо ,для структуры выделить придется 0

@SuperKir 469 / 422 / 290 Регистрация: 10.03.2015 Сообщений: 1,782
	20.10.2015, 17:47	8
	Senarist, Так, давай тогда по порядку. (Честно, не охото разбирать весь код). 1. Вводим кол-во точек 2. Выделяем память под N координат (x,y) этих точек 3. Заполняем координаты. Что происходит далее? 0

@Senarist 52 / 56 / 34 Регистрация: 14.03.2014 Сообщений: 776
	20.10.2015, 18:28 [ТС]	12
	SuperKir Спасибо. Можете конкретно что я лишнего сделал. Буду редактировать 0

@Senarist 52 / 56 / 34 Регистрация: 14.03.2014 Сообщений: 776
	20.10.2015, 22:19 [ТС]	14
	SuperKir а можешь подсказать если знаешь: как проверить образуют ли 3 точки левый поворот? Это обход Грэхема (если вдруг знаешь такое). Везде описан алгоритм который вроде понятен но как проверять какой поворот не ясно. 0