Сортировка вектора объектов класса. QuickSort

87
09 ноября 2021, 12:40

Задача: Найти минимальное остовное дерево графа с помощью алгоритма Краскала. Сортировку нужно реализовать самому (пользоваться библиотечной сортировкой нельзя, лабораторная работа по проге)).

Реализация: для хранения графа

graph.h

#pragma once
#include <iostream>
#include <string>
#include <vector>
#include <fstream>
const unsigned short MIN_DIST = 0;
const unsigned short MAX_DIST = 1023;
const int MAX_NODES = 50;           // Максимальное кол-во вершин
const int MAX_EDGES = 1225;         // Полный граф с N вершинами имеет N(N-1)/2 рёбер
// класс ребра
class Edge
{
private:
    std::string FirstV, SecondV;    // вершины между которыми связь // имя вершины в паре с цветом
    int FirstVcolor, SecondVcolor;
    unsigned short dist;        // вес ребра с диапазоном 0-1023, проверяеться при вводе
public:
    // конструктор
    Edge() : dist(0), FirstVcolor(0), SecondVcolor(0), FirstV(""), SecondV("") {}
    unsigned short getDist() const {
        return dist;
    }
    void setDist(unsigned short dist) {
        this->dist = dist;
    }
    friend class Graph;
};
// класс Графа
class Graph 
{
private:
    std::vector<Edge> edges;            // ГРАФ - по сути массив ребер с вершинами
    std::vector<Edge> disjointSet;      // Минимальное остовное дерево Disjoint-set/Union-find Forest
    int colorOf(std::string str);
    void sortEdges(std::vector<Edge> disjointSet, int begin, int end);
    void quickSort(std::vector<Edge> edges, int begin, int end); //сортировка ребер по возрастанию
    void swapSort(std::vector<Edge> edges, Edge one, Edge Two);  // свап для сортировки
public:
    // конструктор
    Graph() : edges(0), disjointSet(0) {}
    void initGraphfromFile();       // Инициализация ГРАФА
    void sortQuickSort();           // сортировка по возрастанию весов ребер
    void Kruskal();                 // алгоритм Краскала
    void sortEdgesMST();            // Сортировка вершины в лексикографичеком порядке   
    void printUnionFindForest();    // вывод минимального остогого дерева на экран
};

Проблема: При сортировке вылетает, выдает это (см. рис.) Сортировка

graph.cpp

void Graph::sortQuickSort() {
            quickSort(edges, 0, edges.size()-1);
            std::cout << std::endl << "Сортировка ребер по возрастанию весов успешно завершена!" << std::endl;
        }
void Graph::swapSort(std::vector<Edge> edges, Edge one, Edge two) {
    Edge temp;
    temp = one;
    one = two;
    two = temp;
}
void Graph::quickSort(std::vector<Edge> edges, int begin, int end) { // ?????
    int i = begin;
    int j = end;
    int pivot = (int)(edges.size() / 2); // Выбор опорного элемента -- центр массива
    while (i <= j) {
        while (edges[i].getDist() < pivot) {
            i++;
        }
        while (edges[j].getDist() > pivot) {
            j--;
        }
        if (i <= j) {
            swapSort(edges, edges[i], edges[j]);
            i++;
            j--;
        }
    }
    if (j > begin) {
        quickSort(edges, begin, j);
    }
    if (i < end) {
        quickSort(edges, i, end);
    }
}

Прошу указать на ошибки, при возможности предложить решение. Заранее спасибо

Answer 1

Проблема в реализации сортировки - она "тупая" и при обращении к i j элементам массива, выходит за рамки массива (отрицательные или больше реального размера массива).

Answer 2

Вы объявили в классе фунцию_член void quickSort(std::vector<Edge> edges, int begin, int end); а при определении edges у вас ссылька. Сигнатура должна быть одинаковая...

P.S. по поводу вашего кода можно сделать много замечаний:

  • Конструкторы должны инициализировать все свои объекты-члены через список инициализаторов, если это возможно. Это более эффективно, чем присваивание внутри тела конструктора.
  • Уберите деструкторы из классов, они вообше не нужны. Дайте компилятору генерировать нормальный деструктор.
  • Константным обьектам нужно дать возможность вызвать свои селекторы (например Edge::getDist()), поэтому и во избежании случайных ошибок (попыток записи) они должны быть константными методами ( например void Edge::getDist() const)...
READ ALSO
Проблема с несовместимостью типов, с статическим и динамическим массивами

Проблема с несовместимостью типов, с статическим и динамическим массивами

Сразу к сути: выполнял задание с университета Мой код:

172
Переименовать вершины графа BOOST

Переименовать вершины графа BOOST

Как задавать имена вершинам в моем коде?

244
О наследовании в С++

О наследовании в С++

Задание от преподавателя ООП в вузеВычислить сумму чисел наследуемых классов используя методы доступа

86
Перенаправление вывода консоли в файл

Перенаправление вывода консоли в файл

Как перенаправить вывод cmd в файл

339