Home Quick sort of dynamic massive of objects doesn't work correctly
Reply: 1

Quick sort of dynamic massive of objects doesn't work correctly

Нели Димитрова
1#
Нели Димитрова Published in 2018-01-12 14:48:56Z

In my task I have to make class city, which have data members

width(GeografskaShirina)
lenght(GeografskaDaljina)
ime(name)
NadmorskaVisochina(height)

I have constructor by defalut,which input data, copy constructor and predefinition of operator = .

I should sort my dynamic array bulgaria by GeografskaDaljina(length), using quick sort, which I realized in method of class quicksort. I have also a Output() method(to print sorted names of cities), method getDaljina(),which returns GeografskaDaljina(length).

The problem is that when I call quicksort in main(), sorting doesn't work correctly and doesn't print wishing results.

#include "stdafx.h"
#include<string>
#include<iostream>
using namespace std;
class city {
private:

    string ime;
    double GeografskaShirina;
    double GeografskaDaljina;
    double NadmorskaVisochina;
public:
    city();
    double getDaljina();
    string getN();
    void Output();
    city(const city& p);
    city& operator = (const city& p);
    void quicksort(city bulgaria[], int left, int right);


};

city::city(const city& p)
{
    ime = p.ime;
    GeografskaDaljina = p.GeografskaDaljina;
    GeografskaShirina = p.GeografskaShirina;
    NadmorskaVisochina = p.NadmorskaVisochina;

}
city& city::operator = (const city& p)
{
    if (this != &p)
    {
ime = p.ime;
    GeografskaDaljina = p.GeografskaDaljina;
    GeografskaShirina = p.GeografskaShirina;
    NadmorskaVisochina = p.NadmorskaVisochina;
    }
    return *this;


}
city::city()
{
    cout << "Vavedete ime grad: ";
    cin >> ime;
    cout << "Vavedete geografskata shirina na grada: ";
    cin >> GeografskaShirina;
    cout << "geografskata daljina na grada: ";
    cin >> GeografskaDaljina;
    cout << "Vavedete nadmorska visochina na grada: ";
    cin >> NadmorskaVisochina;
    cout << "---------------------------------" << endl;
}


void city:: quicksort(city bulgaria[], int left, int right)
{
    int  min;
    min = (left + right) / 2;
    cout << left << endl;
    cout << right << endl;
    int i = left;
    int j = right;
    int pivot = bulgaria[min].getDaljina();
    while (left < j || i < right)
    {
        while (bulgaria[i].getDaljina() < pivot)
            i++;
        while (bulgaria[i].getDaljina()>pivot)
            j--;
        if (i <= j)
        {
            city temp = bulgaria[i];
            bulgaria[i] = bulgaria[j];
            bulgaria[j] = temp;
            i++;
            j--;
        }
        else
        {
            if (left < j)
            {
                quicksort(bulgaria, left, j);
            }
            if (i < right)
            {
                quicksort(bulgaria, i, right);
            }
                return;

            }
        }

    return;
    }
    double city::getDaljina() {
    return GeografskaDaljina;
}

string city::getN() {
    return ime;
}
void city::Output()
{
    cout << "Imeto e " << ime << endl;
    cout << "Geografskata shirina e " << GeografskaShirina << endl;
    cout << "Geografskata duljina e " << GeografskaDaljina << endl;
    cout << "Nadmorskata visochina e " << NadmorskaVisochina << endl;
}
int main()
{
    int n;
    int i=0;
    cout << "Broi gradove : ";
    cin >> n;
    cout << endl;
    city *bulgaria = new city[n];
    bulgaria[i].quicksort(bulgaria, 0,n-1);

    for (int i = 0; i < n; i++)
    {
    bulgaria[i].Output();}
    return 0;}
A. A
2#
A. A Reply to 2018-01-12 16:10:08Z

You use the wrong index in the second while loop in city::quicksort. You schold use j to compare the right value with the pivot value:

while (bulgaria[j].getDaljina()>pivot)
        j--;
You need to login account before you can post.

About| Privacy statement| Terms of Service| Advertising| Contact us| Help| Sitemap|
Processed in 0.327128 second(s) , Gzip On .

© 2016 Powered by mzan.com design MATCHINFO