| 140203 | }; |
| 140204 | } |
| 140205 | function quicksort(ids, dists, left, right) { |
| 140206 | if (right - left <= 20) for(let i = left + 1; i <= right; i++){ |
| 140207 | const temp = ids[i]; |
| 140208 | const tempDist = dists[temp]; |
| 140209 | let j = i - 1; |
| 140210 | while(j >= left && dists[ids[j]] > tempDist)ids[j + 1] = ids[j--]; |
| 140211 | ids[j + 1] = temp; |
| 140212 | } |
| 140213 | else { |
| 140214 | const median = left + right >> 1; |
| 140215 | let i = left + 1; |
| 140216 | let j = right; |
| 140217 | swap(ids, median, i); |
| 140218 | if (dists[ids[left]] > dists[ids[right]]) swap(ids, left, right); |
| 140219 | if (dists[ids[i]] > dists[ids[right]]) swap(ids, i, right); |
| 140220 | if (dists[ids[left]] > dists[ids[i]]) swap(ids, left, i); |
| 140221 | const temp = ids[i]; |
| 140222 | const tempDist = dists[temp]; |
| 140223 | while(true){ |
| 140224 | do i++; |
| 140225 | while (dists[ids[i]] < tempDist); |
| 140226 | do j--; |
| 140227 | while (dists[ids[j]] > tempDist); |
| 140228 | if (j < i) break; |
| 140229 | swap(ids, i, j); |
| 140230 | } |
| 140231 | ids[left + 1] = ids[j]; |
| 140232 | ids[j] = temp; |
| 140233 | if (right - i + 1 >= j - left) { |
| 140234 | quicksort(ids, dists, i, right); |
| 140235 | quicksort(ids, dists, left, j - 1); |
| 140236 | } else { |
| 140237 | quicksort(ids, dists, left, j - 1); |
| 140238 | quicksort(ids, dists, i, right); |
| 140239 | } |
| 140240 | } |
| 140241 | } |
| 140242 | function swap(arr, i, j) { |
| 140243 | const tmp = arr[i]; |
| 140244 | arr[i] = arr[j]; |