Welcome, Guest. Please login or register. Did you miss your activation email?

Author Topic: Implementing Insertion Sort Algorithm  (Read 88 times)

0 Members and 1 Guest are viewing this topic.

Daniel

  • Newbie
  • *
  • Posts: 7
    • View Profile
    • Email
Implementing Insertion Sort Algorithm
« on: August 07, 2020, 12:53:08 am »
Hello! I'm trying to implement insertion sort algorithm using iterators. So... In the source code, I have a vector of rectangles which will be sorted by their heights. I've printed the heights values which were in the correct order but when I'm trying to change the x, y coordinates it doesn't seem to work.

If you can play around with the code and maybe figure out something, please let me know... Thanks! :D

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

int main()
{
    sf::RenderWindow window(sf::VideoMode(1280, 800), "SFML works!");
   
        std::vector<sf::RectangleShape> sequence;
        int els = 5;
        int max = 100;
        int min = 10;
       
        float randomHeight;
        float xCurrPos = 100;

        for (unsigned int i = 0; i < els; i++)
        {
                randomHeight = rand() % max + min;
                sf::RectangleShape unit;
                unit.setSize(sf::Vector2f(4, randomHeight));
                unit.setFillColor(sf::Color::Black);
                unit.setRotation(180);
                unit.setPosition(xCurrPos, 720);
                xCurrPos += 10;
                sequence.push_back(unit);
        }


        while (window.isOpen())
        {
                std::vector<sf::RectangleShape>::iterator iti;
                int j;
                sf::RectangleShape leftmost;
                float xs, ys, xl, yl;

                for (iti = sequence.begin() + 1; iti != sequence.end(); ++iti)
                {
                        j = std::distance(sequence.begin(), std::prev(iti));
                        leftmost = *iti;

                        while (j >= 0 && sequence.at(j).getSize().y > leftmost.getSize().y)
                        {
                                sequence.at(j + 1) = sequence.at(j);
                                xs = sequence.at(j + 1).getPosition().x;
                                ys = sequence.at(j + 1).getPosition().y;
                                sequence.at(j).setPosition(sf::Vector2f(xs, ys));
                                --j;
                        }
                        sequence.at(j + 1) = leftmost;
                        xl = sequence.at(j + 1).getPosition().x;
                        yl = sequence.at(j + 1).getPosition().y;
                        leftmost.setPosition(sf::Vector2f(xl, yl));
                }
                       
               
                // prints the sorted sequence
                window.clear(sf::Color::White);
                for (std::vector<sf::RectangleShape>::iterator itp = sequence.begin(); itp != sequence.end(); itp = std::next(itp))
                {
                        window.draw(*itp);
                        //std::cout << (*itp).getSize().y << "\n";
                }
                window.display();
        }
    return 0;
}

Hapax

  • Hero Member
  • *****
  • Posts: 3017
  • My number of posts is shown in hexadecimal.
    • View Profile
Re: Implementing Insertion Sort Algorithm
« Reply #1 on: August 13, 2020, 04:47:03 pm »
When swapping the details of the rectangles, you seem to be only swapping the positions; the sizes are staying with their original rectangles. You could just swap the rectangles entirely.


Another option is to leave them in their original order and keep a vector of pointers that point to each one. Then, sort these pointers based on the rectangles they point to.
When you need to access them in order, use the pointer.
Another good thing about this is that you can access the rectangles directly and they never change so you can always be sure it's the one you want ;D
Selba Ward - SFML drawables
Kairos - Timing Library
Rectangular Boundary Collision - Rectangular SAT Collision

@Hapaxiation - Hapaxia on Twitter

 

anything