teratail
回答率
85.48%
質問するログイン新規登録
トップに関する質問algorithm　quicksort　渡す配列の汎用化

編集履歴

質問編集履歴

4

追記

2016/12/08 05:54

投稿

may88seiji
may88seiji

スコア79

test CHANGED
File without changes
test CHANGED
@@ -84,74 +84,86 @@
84
84
 
85
85
 
86
86
 
87
+ 追々記
88
+
89
+ 再帰のところで止まってしまうようです。。。
90
+
87
- お二人の回答を受けての追記
91
+ 間違っているところを指摘いただければ幸いです。
88
92
 
89
93
  ```javascript
90
94
 
91
- function quickSort(a){
95
+ function startQuickSort(a, startID, endID){
92
96
 
93
- var newArray = [];
97
+ function quickSort(startID, endID){
94
98
 
95
- var newArray = a;
99
+ var pivot = a[Math.floor((startID + endID)/2)];
96
100
 
97
- var pivot = newArray[Math.floor((0 + newArray.length-1)/2)];
101
+ var left = startID;
98
102
 
99
- var left = newArray[0];
103
+ var right = endID;
100
-
101
- var right = newArray[newArray.length-1];
102
104
 
103
105
 
104
106
 
105
- while(true){
107
+ while(true){
106
108
 
107
- while(newArray[left]<pivot){
109
+ while(a[left]<pivot){
108
110
 
109
- left++;
111
+ left++;
112
+
113
+ }
114
+
115
+ while(pivot<a[right]){
116
+
117
+ right--;
118
+
119
+ }
120
+
121
+ if(right <= left){
122
+
123
+ break;
124
+
125
+ }
126
+
127
+ var tmp =a[left];
128
+
129
+ a[left] =a[right];
130
+
131
+ a[right] =tmp;
132
+
133
+ left++;
134
+
135
+ right--;
136
+
137
+ }
138
+
139
+ if(startID < left-1){
140
+
141
+ quickSort(startID,left-1);
142
+
143
+ }
144
+
145
+ if(right+1 < endID){
146
+
147
+ quickSort(right+1,endID);
148
+
149
+ }
150
+
151
+ }
152
+
153
+
154
+
155
+ quickSort(a, startID, endID);
156
+
157
+
110
158
 
111
159
  }
112
160
 
113
- while(pivot<newArray[right]){
114
161
 
115
- right--;
116
-
117
- }
118
-
119
- if(right <= left){
120
-
121
- break;
122
-
123
- }
124
-
125
- var tmp =newArray[left];
126
-
127
- newArray[left] =newArray[right];
128
-
129
- newArray[right] =tmp;
130
-
131
- left++;
132
-
133
- right--;
134
-
135
- }
136
-
137
- if(newArray[0] < left-1){
138
-
139
- quickSort(newArray[0],left-1);
140
-
141
- }
142
-
143
- if(right+1 < endID){
144
-
145
- quickSort(right+1,newArray[newArray.length-1]);
146
-
147
- }
148
-
149
- return newArray;
150
-
151
- }
152
162
 
153
163
  var a = [3,7,2,4,6,1,9,8,5];
154
164
 
165
+ startQuickSort(a, 0, a.length-1);
166
+
155
- quickSort(a);
167
+ console.log(a);
156
168
 
157
169
  ```

3

追記しました。

2016/12/08 05:54

投稿

may88seiji
may88seiji

スコア79

test CHANGED
File without changes
test CHANGED
@@ -81,3 +81,77 @@
81
81
  console.log(a);
82
82
 
83
83
  ```
84
+
85
+
86
+
87
+ お二人の回答を受けての追記
88
+
89
+ ```javascript
90
+
91
+ function quickSort(a){
92
+
93
+ var newArray = [];
94
+
95
+ var newArray = a;
96
+
97
+ var pivot = newArray[Math.floor((0 + newArray.length-1)/2)];
98
+
99
+ var left = newArray[0];
100
+
101
+ var right = newArray[newArray.length-1];
102
+
103
+
104
+
105
+ while(true){
106
+
107
+ while(newArray[left]<pivot){
108
+
109
+ left++;
110
+
111
+ }
112
+
113
+ while(pivot<newArray[right]){
114
+
115
+ right--;
116
+
117
+ }
118
+
119
+ if(right <= left){
120
+
121
+ break;
122
+
123
+ }
124
+
125
+ var tmp =newArray[left];
126
+
127
+ newArray[left] =newArray[right];
128
+
129
+ newArray[right] =tmp;
130
+
131
+ left++;
132
+
133
+ right--;
134
+
135
+ }
136
+
137
+ if(newArray[0] < left-1){
138
+
139
+ quickSort(newArray[0],left-1);
140
+
141
+ }
142
+
143
+ if(right+1 < endID){
144
+
145
+ quickSort(right+1,newArray[newArray.length-1]);
146
+
147
+ }
148
+
149
+ return newArray;
150
+
151
+ }
152
+
153
+ var a = [3,7,2,4,6,1,9,8,5];
154
+
155
+ quickSort(a);
156
+
157
+ ```

2

説明の追加

2016/12/05 08:20

投稿

may88seiji
may88seiji

スコア79

test CHANGED
@@ -1 +1 @@
1
- algorithm　quicksort
1
+ algorithm　quicksort　渡す配列の汎用化
test CHANGED
File without changes

1

誤字修正

2016/12/05 07:03

投稿

may88seiji
may88seiji

スコア79

test CHANGED
File without changes
test CHANGED
@@ -10,7 +10,7 @@
10
10
 
11
11
  この関数を配列bなど他の配列に対応するためにはどのようにしたらよいでしょうか。
12
12
 
13
- (動的にソートする配列を関数に渡すためにはどうしたらよいでしょうか)
13
+ (汎用的にソートする配列を関数に渡すためにはどうしたらよいでしょうか)
14
14
 
15
15
 
16
16