Sortowanie bąbelkowe vectora 2D

Odpowiedz Nowy wątek
2011-04-10 17:57
0

Mam problem, otóż próbuję posortować liczby, które są umieszczone w vectorze 2D, mianowicie - każdy "wiersz" to osobna liczba, a każda "komórka" to osobna cyfra tej liczby.

vector <int> character(1);
vector < vector <int> > line(1, character);

(Dane są wczytywane w pętli z pliku.)

I chciałbym te liczby (wiele z nich przekracza zakres long long int) posortować od najmniejszej do największej - robię to tak:

//Bubble sort :)
    for (int i=0; i<line.size()-1; i++)
    {
        for (int j=0; j<line.size()-i-1; j++)
        {
            if (line[j].size()>line[j+1].size()) swap(line[j],line[j+1]);
            else if (line[j].size()==line[j+1].size())
            {
                for (int k=0; k<line[j].size()-1; k++)
                {
                    if (line[j][k]>line[j+1][k]) {swap(line[j],line[j+1]); break;}
                }
            }
        }
    }

No i owszem, według ilości cyfr liczby te są świetnie posortowane - ale liczby o tej samej długości już nie.
W najbardziej wewnętrznej pętli oparłem się na założeniu, że należy porównywać kolejne cyfry k (od lewej, np. od tysięcy do jedności) danych dwóch liczb j i j+1, by określić która jest większa.
Czy ktoś jest mi w stanie wskazać co jest nie tak?

edytowany 5x, ostatnio: TeoTN, 2011-04-10 18:26
jak MOGĄ przekraczać zakres long long, skoro trzymasz zwykłe inty? - Azarien 2011-04-12 11:47

Pozostało 580 znaków

2011-04-10 18:16
0

Spróbuj porównać wewnętrznym algorytmem dwie liczby poniżej (przykład):

30003
10001

I co?? wykonasz funkcję swap(...) dwa razy! Pierwszy raz przy pierwszym znaku i drugi raz przy ostatnim (bo za każdym razem 3 > 1). Musisz po pierwszym wykryciu "większości" zakończyć porównywanie.


Not Found
The requested URL /wypasiona_sygnaturka.txt was not found in this brain.
-----
Human/1.0.00 (Earth) Server at Poland Port 65535

Pozostało 580 znaków

2011-04-10 18:24
0

Ach, tak, zapomniałem o "break;"
Ale z nim - czy bez niego - dalej nie działa poprawnie [zaraz dopiszę w 1. poście, może w złym miejscu umieszczam?]

Pozostało 580 znaków

2011-04-12 09:43
0
#include <algorithm>

bool lessIntVectorComparator(const vector <int>& a, const vector <int>& b)
{
    if (a.size()!=b.size())
         return a.size()<b.size(); 

    ....
    return result;
}

std::sort(line.begin(), line.end(), lessIntVectorComparator);

Jeśli chcesz pomocy, NIE pisz na priva, ale zadaj dobre pytanie na forum.
edytowany 2x, ostatnio: MarekR22, 2011-04-12 09:46

Pozostało 580 znaków

2011-04-12 16:24
0

Działa! :) Stokrotne dzięki :)

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0