質問編集履歴
2
現在の実装を追加
test
CHANGED
|
File without changes
|
test
CHANGED
|
@@ -3,6 +3,8 @@
|
|
|
3
3
|
なるべく余分なメモリを確保せずに高速にソートしたいです。
|
|
4
4
|
|
|
5
5
|
ソート部分は自分で書かずにstd::sortなどをつかいたいです。
|
|
6
|
+
|
|
7
|
+
現在は構造体の配列に詰め直してからソートする実装になっているので入力と同じサイズのワーキングスペースを使っています。
|
|
6
8
|
|
|
7
9
|
うまい方法はないでしょうか？
|
|
8
10
|
|
|
@@ -39,3 +41,95 @@
|
|
|
39
41
|
}
|
|
40
42
|
|
|
41
43
|
```
|
|
44
|
+
|
|
45
|
+
```C++
|
|
46
|
+
|
|
47
|
+
// 現在の実装
|
|
48
|
+
|
|
49
|
+
// ワーキングスペースとして入力と同じサイズの配列を用いてしまっている
|
|
50
|
+
|
|
51
|
+
template <typename T> struct k1_k2 {
|
|
52
|
+
|
|
53
|
+
int k1;
|
|
54
|
+
|
|
55
|
+
int k2;
|
|
56
|
+
|
|
57
|
+
T val;
|
|
58
|
+
|
|
59
|
+
bool operator<(const k1_k2<T> &obj){
|
|
60
|
+
|
|
61
|
+
return k1 < obj.k1 || (k1 == obj.k1 && k2 < obj.k2);
|
|
62
|
+
|
|
63
|
+
}
|
|
64
|
+
|
|
65
|
+
bool operator>(const k1_k2<T> &obj){
|
|
66
|
+
|
|
67
|
+
return k1 > obj.k1 || (k1 == obj.k1 && k2 > obj.k2);
|
|
68
|
+
|
|
69
|
+
}
|
|
70
|
+
|
|
71
|
+
};
|
|
72
|
+
|
|
73
|
+
template <typename T> struct k2_k1 {
|
|
74
|
+
|
|
75
|
+
int k1;
|
|
76
|
+
|
|
77
|
+
int k2;
|
|
78
|
+
|
|
79
|
+
T val;
|
|
80
|
+
|
|
81
|
+
bool operator<(const k2_k1<T> &obj){
|
|
82
|
+
|
|
83
|
+
return k2 < obj.k2 || (k2 == obj.k2 && k1 < obj.k1);
|
|
84
|
+
|
|
85
|
+
}
|
|
86
|
+
|
|
87
|
+
bool operator>(const k2_k1<T> &obj){
|
|
88
|
+
|
|
89
|
+
return k2 > obj.k2 || (k2 == obj.k2 && k1 > obj.k1);
|
|
90
|
+
|
|
91
|
+
}
|
|
92
|
+
|
|
93
|
+
};
|
|
94
|
+
|
|
95
|
+
|
|
96
|
+
|
|
97
|
+
template <typename T> sort(const int flag,int *k1,int *k2,T *v,const int n){
|
|
98
|
+
|
|
99
|
+
if(flag & K1_K2){
|
|
100
|
+
|
|
101
|
+
vector< k1_k2<T> > vec(n);
|
|
102
|
+
|
|
103
|
+
for(int i=0 ; i<n ; ++i){ vec[i].k1 = k1[i]; vec[i].k2 = k2[i]; vec.val[i] = v[i]; }
|
|
104
|
+
|
|
105
|
+
if(flag & ASC){
|
|
106
|
+
|
|
107
|
+
std::sort(vec.begin(),vec.end(),less< k1_k2<T> >());
|
|
108
|
+
|
|
109
|
+
}else{
|
|
110
|
+
|
|
111
|
+
std::sort(vec.begin(),vec.end(),greater< k1_k2<T> >());
|
|
112
|
+
|
|
113
|
+
}
|
|
114
|
+
|
|
115
|
+
}else{
|
|
116
|
+
|
|
117
|
+
vector< k2_k1<T> > vec(n);
|
|
118
|
+
|
|
119
|
+
for(int i=0 ; i<n ; ++i){ vec[i].k1 = k1[i]; vec[i].k2 = k2[i]; vec.val[i] = v[i]; }
|
|
120
|
+
|
|
121
|
+
if(flag & ASC){
|
|
122
|
+
|
|
123
|
+
std::sort(vec.begin(),vec.end(),less< k2_k1<T> >());
|
|
124
|
+
|
|
125
|
+
}else{
|
|
126
|
+
|
|
127
|
+
std::sort(vec.begin(),vec.end(),greater< k2_k1<T> >());
|
|
128
|
+
|
|
129
|
+
}
|
|
130
|
+
|
|
131
|
+
}
|
|
132
|
+
|
|
133
|
+
}
|
|
134
|
+
|
|
135
|
+
```
|
1
ソートの定義の変更
test
CHANGED
|
File without changes
|
test
CHANGED
|
@@ -10,11 +10,9 @@
|
|
|
10
10
|
|
|
11
11
|
//sample.cpp
|
|
12
12
|
|
|
13
|
-
template <typename T> sort(int *k1,int *k2,T *v,const int n){
|
|
13
|
+
template <typename T> sort(const int flag,int *k1,int *k2,T *v,const int n){
|
|
14
14
|
|
|
15
|
-
// keys1 をプライマリキー
|
|
16
|
-
|
|
17
|
-
// k
|
|
15
|
+
// flagによってk1とk2のどちらをプライマリキーとするか制御してソート
|
|
18
16
|
|
|
19
17
|
// 不安定なソートでもよい
|
|
20
18
|
|