Сортировка вектора прямоугольников - PullRequest
Новая
       73

Сортировка вектора прямоугольников

1 голос
/ 13 июля 2020

Итак, я пытаюсь реализовать алгоритм пузырьковой сортировки с использованием SFML. Я создал вектор, в который добавляю несколько прямоугольников и сортирую их по высоте, но вроде ничего не сортирую. Я делаю что-то неправильно? Пожалуйста, проверьте этот код ... это не слишком много. 

#include <SFML/Graphics.hpp>
#include <ctime>
#include <iostream>
#include <vector>

int main()
{
    srand(time(0));
    float randomHeight;
    std::vector<sf::RectangleShape> v;
    float currY = 100;
    sf::RenderWindow window(sf::VideoMode(1280, 800), "SFML works!");
    
    for (unsigned int i = 0; i < 100; i++)
    {
       
        randomHeight = rand() % 500 + 200;
        sf::RectangleShape rect({ 4, randomHeight });
        rect.setFillColor(sf::Color::White);
        rect.setRotation(180);
        currY += 10;
        rect.setPosition({ currY, 720 });

        v.push_back(rect);
    }
  

    while (window.isOpen())
    {
        sf::Event event;
        while (window.pollEvent(event))
        {
            if (event.type == sf::Event::Closed)
                window.close();
        }
        
        
        
        for (unsigned int i = 0; i < v.size(); i++)
        {
            for (auto itj = v.begin(); itj != v.end() - 1; itj = std::next(itj))
            {
                if ((*itj).getSize().y > (*std::next(itj)).getSize().y)
                {
                    std::swap(*itj, *std::next(itj)); 
                }
            }
        }

        for (auto i = v.begin(); i != v.end(); i = std::next(i))
            window.draw(*i);
        window.display();
       
        
    }
    
    return 0;
}

Ответы [ 2 ]

0 голосов
/ 13 июля 2020

Похоже, вы забыли логическое значение. Мой c ++ довольно ржавый, так что будьте осторожны. Вместо этого: 

for (unsigned int i = 0; i < v.size(); i++)
{
    for (auto itj = v.begin(); itj != v.end() - 1; itj = std::next(itj))
    {
        if ((*itj).getSize().y > (*std::next(itj)).getSize().y)
        {
            std::swap(*itj, *std::next(itj)); 
        }
    }
}

У вас должно получиться что-то вроде этих строк: 

bool swapped = false;
do {
    swapped = false;
    for (unsigned int i = 0; i < v.size(); i++)
    {
        for (auto itj = v.begin(); itj != v.end() - 1; itj = std::next(itj))
        {
            if ((*itj).getSize().y > (*std::next(itj)).getSize().y)
            {
                std::swap(*itj, *std::next(itj)); 
                swapped = true;
            }
        }
    }
} while (swapped);

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

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

Удачи!

0 голосов
/ 13 июля 2020

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

std::swap(*itj, *std::next(itj)); 

//Swapping x,y coordinates
int x = (*itj).getPosition().x;
int y = (*itj).getPosition().y;

int x_next = (*std::next(itj)).getPosition().x;
int y_next = (*std::next(itj)).getPosition().y;

(*itj).setPosition( sf::Vector2f(x_next, y_next) );
(*std::next(itj)).setPosition( sf::Vector2f(x, y) );

Это позволит отсортировать прямоугольники в порядке возрастания в зависимости от их высоты.

...