Всем привет!!! Пытаюсь реализовать алгоритм по книге , там псевдокод, я попытался перенести всё на С++, вроде бы всё делаю правильно, но сортировка не сортирует
вот пример:
| 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
| #include "stdafx.h"
#include <time.h>
#include <vector>
#include <iostream>
#include <stdexcept>
int SIZE = 100000;
struct Arr{
std::vector<int> mas;
int hs;
};
void Fill(Arr & arr){
for (size_t i = 0; i < SIZE; ++i)
{
int key = rand();
arr.mas.push_back(key);
}
}
void ReFill(Arr & arr){
for (size_t i = 0; i < SIZE; ++i)
{
int key = rand();
arr.mas[i] = key;
}
}
void PrintArray(Arr & arr) {
for (size_t i = 0; i < arr.mas.size(); ++i)
{
std::cout << arr.mas[i] << " ";
if (i % 10 == 0 && i != 0)
{
std::cout << std::endl;
}
}
}
void test(Arr & mas)
{
for (size_t i = 1; i < mas.mas.size(); ++i) {
if (!(mas.mas[i - 1] <= mas.mas[i]))
{
throw std::exception("Un right sort!!! ERROR!");
}
}
}
void MergeSort(Arr & mas, int down, int up);
void testMerge();
int _tmain(int argc, _TCHAR* argv[])
{
srand(time(NULL));
Arr mas;
Fill(mas);
float fTimeStart;
float fTimeStop;
std::cout << "Merge sort : " << std::endl;
fTimeStart = clock() / (float)CLOCKS_PER_SEC;
testMerge();
fTimeStop = clock() / (float)CLOCKS_PER_SEC;
try {
test(mas);
}
catch (std::exception & e)
{
std::cout << std::endl << e.what() << std::endl;
return 1;
}
printf("Time of working == %f sec\n", fTimeStop - fTimeStart);
return 0;
}
/*
Merge Sort
*/
void Merge(Arr & arr, int left, int right, int middle);
void testMerge() {
Arr mas;
mas.mas.push_back(2);
mas.mas.push_back(3);
mas.mas.push_back(1);
MergeSort(mas, 0, mas.mas.size());
}
void MergeSort(Arr & arr, int left, int right) {
if (left < right) {
int middle = (left + right) / 2;
MergeSort(arr, left, middle);
MergeSort(arr, middle + 1, right);
Merge(arr, left, right, middle);
}
}
void Merge(Arr & arr, int left, int right, int middle) {
int countLeftElement = middle - left;
int countRightElement = right - middle;
std::vector<int> leftArray;
std::vector<int> rightArray;
int indexLeft = 0;
int indexRight = 0;
for (; indexLeft < countLeftElement; ++indexLeft) {
leftArray.push_back(arr.mas[left + indexLeft]);
}
for (; indexRight < countRightElement; ++indexRight) {
rightArray.push_back(arr.mas[middle + indexRight]);
}
leftArray.push_back(INT_MAX);
rightArray.push_back(INT_MAX);
indexLeft = 0;
indexRight = 0;
for (int i = left; i < right; ++i) {
if (leftArray[indexLeft] <= rightArray[indexRight]) {
arr.mas[i] = leftArray[indexLeft];
indexLeft++;
}
else {
arr.mas[i] = rightArray[indexRight];
indexRight++;
}
}
}
void printVector(std::vector<int> & vec)
{
for (int i = 0; i < vec.size(); ++i)
{
std::cout << vec[i] << " ";
}
}
void print(int * a, int up){
for (int i = 0; i < up; ++i)
{
std::cout << a[i] << " ";
}
std::cout << std::endl;
}
void printSides(std::vector<int> & a, int up, int down) {
for (int i = down; i < up; ++i)
{
std::cout << a[i] << " ";
}
std::cout << std::endl;
} |
|
Насколько я понимаю всё происходит из за того что я каким то образом не обрабатываю границу правую , то есть в моём примере число 1, у автора там в псевдокоеде, строка в процедуре merge, не
| C++ |
1
| int countLeftElement = middle - left; |
|
а, что то наподобие, ( там просто массивы а у меня vector)
| C++ |
1
| int countLeftElement = middle - left+1; |
|
и в той же процедуре merge во втором циле for
там не
| C++ |
1
| leftArray.push_back(arr.mas[left + indexLeft]); |
|
а что то наподобие( там просто массивы а у меня vector)
| C++ |
1
| leftArray.push_back(arr.mas[left + indexLeft - 1]); |
|
Но если я так напишу , у меня будет ошибка "Vector out of range"
Видел, много реализаций готовых, но всё равно не могу понять почему и где я ошибаюсь...
Может кто сталкивался с такой же проблемой при сортировке?
Спасибо за внимание!!!
(
