Форум программистов, компьютерный форум CyberForum.ru
Наши страницы

АТД "MyVector" - методы сортировки выбора и слияния - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Поворот треугольника (вокруг центра) http://www.cyberforum.ru/cpp-beginners/thread1492053.html
Есть функция которая рисует треугольник по трём точкам. Эти точки заданы координатами(ху). В классе переменной pvo содержатся все 6 координат(x1,y1 -1 точка, x,y - 2 точка, x2,y2 - третья точка)....
C++ В каком формате лучше хранить историю работы приложения? Подскажите, в чем обычно хранят данные различные игры под windows, которые не онлайн? Просто в бинарных файлах своей структуры без баз данных? http://www.cyberforum.ru/cpp-beginners/thread1491995.html
Реализовать простое 2-3 дерево происка C++
Помогите пожалуйста реализовать простое 2-3 дерево происка на C++, ни в интернете ни на форуме такой реализации не нашёл. Добавлено через 20 часов 26 минут может кто помоч?
Баг в счётчике сортировки "вставка" (insert) C++
Всем добрый день. У меня есть программа по сортировкам на стадии бета-версии. Суть отсортировать строки исходного массива по возрастанию. И есть одна проблема с сортировкой методом "вставка". Вроде...
C++ Вывести из файла среднюю оценку каждого ученика http://www.cyberforum.ru/cpp-beginners/thread1491937.html
Необходима помощь в следующей задаче. Файл содержит оценки учащихся класса в формате: Фамилия, оценки по 10 предметам. Например: Иванов 5 8 6 4 9 7 6 8 9 10 Петров 10 4 9 6 7 8 9 9 9 7 Клюшкин...
C++ Структура "Рейс самолета". Функция удаления Имеется код, который считывает структурный тип из файла и просто записывает его в файл результатов: #define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include <conio.h> #include <stdlib.h>... подробнее

Показать сообщение отдельно
creator_it
1 / 1 / 0
Регистрация: 20.11.2014
Сообщений: 17

АТД "MyVector" - методы сортировки выбора и слияния - C++

02.07.2015, 21:42. Просмотров 233. Ответов 0
Метки (Все метки)

Подскажите, что не так в методах сортировки выбора и слияния? Уточнение: в методе выбора (sort_case) - хз, полный; в слиянии(sort_merge и merge), вроде как происходит зацикливание, причина не понятна( P.S Все остальное нормально работает ... Спасибо заранее!!! И да, это не совсем АТД, но препода не переубедишь

вот код :

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
main.cpp
 
#include <iostream>
#include "interface.h"
#include <vector>
using namespace std;
 
int
main()
{
    vector <int> s;
    s.push_back(1);
    s.push_back(17);
    s.push_back(-4);
    s.push_back(25);
    s.push_back(2);
    s.push_back(12);
    s.push_back(9);
    s.push_back(4);
    s.push_back(42);
    s.push_back(22);
    MyVector <int> object(s);
    system("pause");
    return 0;
}
 
interface.h
 
#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>
 
using namespace std;
 
template <typename Type>
class MyVector : public std::vector<Type>
{
public:
    MyVector(vector <Type> str) : std::vector<Type>(str)
    {
        //sort_merge(0, size());
        sort_shell();
        print();
        rand_fill();
        sort_shell();
        print();
        //sort_case();
    }
 
    ~MyVector()
    {
        cout << endl << " Object to destroyed!!!";
    }
 
    void print() // output to the screen
    {
        int i = 0;
        auto it = begin();
        while (it != end())
        {
            if (i > 0)
                cout << " ";
            cout << *it;
            ++it;
            ++i;
        }
        cout << endl;
    }
 
    void rand_fill() // vector fills randomly numbers
    {
        srand(time(0));
        for (auto it = begin(); it != end(); it++)
        {
            *it = rand() % 100000;
        }
        cout << endl;
    }
 
    int min(int it) // finds the minimum number of vector
    {
        int *min = 2147483647;
        auto s;
        for (; it != end(); it++)
        {
            if (*it < *min) {
                *min = *it;
                s = it;
            }
        }
        return s;
    }
 
    void sort_shell() // method by Shell
    {
        int step = size() / 2;
        while (step > 0)
        {
            for (int i = 0; i < (size() - step); i++)
            {
                int j = i;
                while (j >= 0 && at(j) > at(j + step))
                {
                    int temp = at(j);
                    at(j) = at(j + step);
                    at(j + step) = temp;
                    j--;
                }
            }
            step = step / 2;
        }
    }
    
    void merge(int first, int last)
    {
        int middle, start, final, j;
        int *mas = new int[100];
        middle = (first + last) / 2;
        start = first; 
        final = middle + 1;
        for (j = first; j < last; j++)
        if ((start <= middle) && ((final > last) || (at(start) < at(final))))
        {
            mas[j] = at(start);
            start++;
        }
        else
        {
            mas[j] = at(final);
            final++;
        }
        for (j = first; j < last; j++) 
            at(j) = mas[j];
        delete []mas;
    };
 
    void sort_merge(int first, int last)
    {
        {
            if (first < last)
            {
                sort_merge(first, (first + last) / 2); 
                sort_merge((first + last) / 2 + 1, last);
                merge(first, last);
            }
        }
    };
 
    void sort_case()
    {
        for (auto it = begin(); it != end(); it++)
        {
            swap((begin(), min(it));
        }
    }
    void find_direct();
    void find_fibonachi();
};

задание на всякий случай :
1. На базе шаблона класса vector разработать (спроектировать (см приложение А), реализовать и провести тестовые испытания) АТД «my_vector» путем добавления следующих методов (алгоритмов):
 вывод вектора на экран;
 заполнение вектора с помощью датчика случайных чисел;
 sort1, sort2, , sort3, реализующие операции сортировки массива указанными в варианте задания методами;
 find 1, find2, реализующие операции поиска элемента в упорядоченном массиве указанным в варианте задания методами (см таблицу 4.1.1).
Таблица 4.1.1 – Варианты заданий по методам сортировки и поиска
№ вар Метод сортировки 1 Метод сортировки 2 Метод сортировки 3 Метод поиска 1 Метод поиска 2
Нчт Метод «пузырька» Метод вставок Сортировка подсчетом Двоичный Интерполяционный
Чт Метод выбора Сортировка Шелла Сортировка слиянием Прямой Фибоначчи
Для тестирования эффективности алгоритмов интерфейс разрабатываемого АТД должен включать следующие дополнительные операции:
- опрос числа выполненных сравнений;
- опрос числа выполненных обменов.
2. Реализовать АТД «my_vector» в виде класса C++.
3. Разработать наборы тестов для тестирования операций над массивами в разрабатываемых приложениях.
4. Выполнить отладку и тестирование отдельных операций АТД с помощью меню операций.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru