PDA

View Full Version : Help to set up sorting algorithm



Quasar
24th May 2012, 18:48
Hi all. I'm working on car simulator. The core is the class car who implements the physics of veicles. This class have a public function that return Qtime, the minimum time to go through a part of a track.
One of the outputs of my application would be a table in a sqlite db like this:
Lap | iDCar | LapTime | TotalTime | Position
For this i have implemented a code like this (i'm not posing the original code couse a lot of function's names are not in english)


QString query = " Insert into tablename ";
QVector<Part> track;
QVector<Car> cars;
//fill vectots
QMap<QString, QTime> total_time;
QTime lapTime, partTime;
for(int lap=1; lap<=nLap; lap++)
{
for(int id=0; id<cars.size(); id++)
{
lapTime = QTime(0,0,0,0);
for(int part=0; part<track.size(); part++)
{
partTime = cars[id].getTime(track.at(part));
lapTime = lapTime.addMsec(partTime.msecTo(QTime(0,0))); //really, qAbs() of partTime.msecTo()
total_time[cars.at(id).pilotId()] = total_time[cars.at(id).pilotId()].addMsec(lapTime.msecTo(QTime(0,0)));
s.append( // built a "select - union all" query.
}
}
}
qsqlQuery q;
q.exec(query);


Now the problem is that i can't figure out how to get the position of the car at that determinated lap. I know that i have to do something with the QMap total_time that have unique car id as keys, and total time as values, but i don't know how to sort QMap values witout losing the corrispondence with keys.
I hope someone could help me, and i apologize for my English.

Quasar
25th May 2012, 15:09
Solved Creating a custom Class based upon QList.
It works very well, it use a QList<QPair<QString, QTime>> as member and like a QMap have unique keys as QStrings.
I'm posting the header of that class, so if anyone has troubles like mine, can implement a custom class like this, for exemple based on different QPair.

PairTimeList.h


#ifndef PAIRTIMELIST_H
#define PAIRTIMELIST_H
#include <QList>
#include <QString>
#include <QStringList>
#include <QTime>
#include <QPair>

class PairTimeList
{
public:
PairTimeList();
PairTimeList( QList< QPair<QString, QTime> > list);

bool contains(const QString key) const;
bool contains(const QPair<QString, QTime> pair) const;
bool insert(const QString str, const QTime t);
bool insert(const QPair<QString, QTime> pair);
bool erase(const QString key);
bool erase(const QPair<QString, QTime> pair);
bool erase(int position);
void clear();
void removeFirst();
void removeLast();
bool replace(int position, const QPair<QString, QTime> newpair);
bool replace(const QString key, const QTime newTime);
int position(const QString key) const; //return -1 if key doesn't exists
QPair<QString, QTime> data(int position) const;
const QPair<QString, QTime> at(int position) const;
QTime time(const QString key) const;
QList<QTime> times() const;
QStringList keys();
QStringList keys(const QTime value); //return all keys(QString) with QTime=value
QStringList keysBetween(const QTime fromTime, const QTime toTime);
const QList< QPair<QString, QTime> > sort_byTime() ; //BubbleSort
const QList< QPair<QString, QTime> > sort_byStrings(); //BubbleSort
const QList< QPair<QString, QTime> > getList() const ;
QString print();
int size() const;
void setTime(int position, QTime t);
void setTime(int position, int h, int min, int sec=0, int msec=0);
void setTime(const QString key, QTime t);
void setTime(const QString key, int h, int min, int sec=0, int msec=0);
void addSec(int position, int sectoAdd);
void addSec(const QString key, int sectoAdd);
void addMsec(int position, int msecToAdd);
void addMsec(const QString key, int msecToAdd);
QTime deltaTime(int from1, int to2);
int msecBetween(int position1, int position2);
int msecBetween(const QString key1, QString key2);
int secBetween(int position1, int position2);
int secBetween(const QString key1, QString key2);
private:
QList< QPair<QString, QTime> > mylist;
};

#endif // PAIRTIMELIST_H

Ashtechsmith
12th June 2012, 01:16
Bucket sort, or bin sort, is a sorting algorithm that works by partitioning an array into a number of buckets. Each bucket is then sorted individually, either using a different sorting algorithm, or by recursively applying the bucket sorting algorithm. It is a distribution sort, and is a cousin of radix sort in the most to least significant digit flavour. Bucket sort is a generalization of pigeonhole sort. Since bucket sort is not a comparison sort, the Ω(n log n) lower bound is inapplicable. The computational complexity estimates involve the number of buckets.

function bucketSort(array, n) is
buckets ← new array of n empty lists
for i = 0 to (length(array)-1) do
insert array[i] into buckets[msbits(array[i], k)]
for i = 0 to n - 1 do
nextSort(buckets[i])
return the concatenation of buckets[0], ..., buckets[n-1]
Here array is the array to be sorted and n is the number of buckets to use. The function msbits(x,k) returns the k most significant bits of x (floor(x/2^(size(x)-k))); different functions can be used to translate the range of elements in array to n buckets, such as translating the letters A–Z to 0–25 or returning the first character (0–255) for sorting strings. The function nextSort is a sorting function; using bucketSort itself as nextSort produces a relative of radix sort; in particular, the case n = 2 corresponds to quicksort