Left: | ||
Right: |
LEFT | RIGHT |
---|---|
1 // Copyright 2009 The Go Authors. All rights reserved. | 1 // Copyright 2009 The Go Authors. All rights reserved. |
2 // Use of this source code is governed by a BSD-style | 2 // Use of this source code is governed by a BSD-style |
3 // license that can be found in the LICENSE file. | 3 // license that can be found in the LICENSE file. |
4 | 4 |
5 // Package sort provides primitives for sorting slices and user-defined | 5 // Package sort provides primitives for sorting slices and user-defined |
6 // collections. | 6 // collections. |
7 package sort | 7 package sort |
8 | 8 |
9 // A type, typically a collection, that satisfies sort.Interface can be | 9 // A type, typically a collection, that satisfies sort.Interface can be |
10 // sorted by the routines in this package. The methods require that the | 10 // sorted by the routines in this package. The methods require that the |
(...skipping 346 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
357 return | 357 return |
358 } | 358 } |
359 | 359 |
360 mid := a + (b-a)/2 | 360 mid := a + (b-a)/2 |
361 n := mid + m | 361 n := mid + m |
362 start := 0 | 362 start := 0 |
363 if m > mid { | 363 if m > mid { |
364 start = n - b | 364 start = n - b |
365 r, p := mid, n-1 | 365 r, p := mid, n-1 |
366 for start < r { | 366 for start < r { |
367 » » » c := (start + r) / 2 | 367 » » » c := start + (r-start)/2 |
rsc
2013/06/10 18:06:29
This should be c := start + (r-start) / 2, the sam
volker.dobler
2013/06/24 21:28:58
Done.
| |
368 if !data.Less(p-c, c) { | 368 if !data.Less(p-c, c) { |
369 start = c + 1 | 369 start = c + 1 |
370 } else { | 370 } else { |
371 r = c | 371 r = c |
372 } | 372 } |
373 } | 373 } |
374 } else { | 374 } else { |
375 start = a | 375 start = a |
376 r, p := m, n-1 | 376 r, p := m, n-1 |
377 for start < r { | 377 for start < r { |
378 » » » c := (start + r) / 2 | 378 » » » c := start + (r-start)/2 |
rsc
2013/06/10 18:06:29
Here too.
volker.dobler
2013/06/24 21:28:58
Done.
| |
379 if !data.Less(p-c, c) { | 379 if !data.Less(p-c, c) { |
380 start = c + 1 | 380 start = c + 1 |
381 } else { | 381 } else { |
382 r = c | 382 r = c |
383 } | 383 } |
384 } | 384 } |
385 } | 385 } |
386 end := n - start | 386 end := n - start |
387 rotate(data, start, m, end) | 387 rotate(data, start, m, end) |
388 symMerge(data, a, start, mid) | 388 symMerge(data, a, start, mid) |
(...skipping 30 matching lines...) Expand all Loading... | |
419 } | 419 } |
420 swapRange(data, p-i, p, i) | 420 swapRange(data, p-i, p, i) |
421 } | 421 } |
422 | 422 |
423 /* | 423 /* |
424 Complexity of Stable Sorting | 424 Complexity of Stable Sorting |
425 | 425 |
426 | 426 |
427 Complexity of block swapping rotation | 427 Complexity of block swapping rotation |
428 | 428 |
429 Algorithm: Wolog assume |u| < |v|. | 429 Each Swap puts one new element into its correct, final position. |
430 Terminates once |u| = |v| using |u| Swaps. | |
431 Swap u vl vr to vr vl u using |u| Swaps. | |
432 Block u is now in the proper position and order. | |
433 Iterate on vr vl with |vr| = |u|. | |
434 | |
435 On each (non-terminating) iteration |u| elements are brought to their | |
436 final position using |u| Swaps and the process continues with the | |
437 remaining |v|-|u| elements. | |
438 The terminating iteration requires at most |u| Swaps. | |
439 So each Swap puts one new element into its correct, final position. | |
440 Elements which reach their final position are no longer moved. | 430 Elements which reach their final position are no longer moved. |
441 Thus block swapping rotation needs |u|+|v| calls to Swaps. | 431 Thus block swapping rotation needs |u|+|v| calls to Swaps. |
442 This is best possible as each element might need a move. | 432 This is best possible as each element might need a move. |
443 | 433 |
444 Pay attention when comparing to other optimal algorithms which | 434 Pay attention when comparing to other optimal algorithms which |
445 typically count the number of assignments instead of swaps: | 435 typically count the number of assignments instead of swaps: |
446 E.g. the optimal algorithm of Dudzinski and Dydek for in-place | 436 E.g. the optimal algorithm of Dudzinski and Dydek for in-place |
447 rotations uses O(u + v + gcd(u,v)) assignments which is | 437 rotations uses O(u + v + gcd(u,v)) assignments which is |
448 better than our O(3 * (u+v)) as gcd(u,v) <= u. | 438 better than our O(3 * (u+v)) as gcd(u,v) <= u. |
449 | 439 |
(...skipping 25 matching lines...) Expand all Loading... | |
475 Above results should generalize to arbitrary n = 2^k + p | 465 Above results should generalize to arbitrary n = 2^k + p |
476 and should not be influenced by the initial insertion sort phase: | 466 and should not be influenced by the initial insertion sort phase: |
477 Insertion sort is O(n^2) on Swap and Less, thus O(bs^2) per block of | 467 Insertion sort is O(n^2) on Swap and Less, thus O(bs^2) per block of |
478 size bs at n/bs blocks: O(bs*n) Swaps and Less during insertion sort. | 468 size bs at n/bs blocks: O(bs*n) Swaps and Less during insertion sort. |
479 Merge sort iterations start at i = log(bs). With t = log(bs) constant: | 469 Merge sort iterations start at i = log(bs). With t = log(bs) constant: |
480 Calls to Less O((log(n)-t) * n + bs*n) = O(log(n)*n + (bs-t)*n) | 470 Calls to Less O((log(n)-t) * n + bs*n) = O(log(n)*n + (bs-t)*n) |
481 = O(n * log(n)) | 471 = O(n * log(n)) |
482 Calls to Swap O(n * log^2(n) - (t^2+t)/2*n) = O(n * log^2(n)) | 472 Calls to Swap O(n * log^2(n) - (t^2+t)/2*n) = O(n * log^2(n)) |
483 | 473 |
484 */ | 474 */ |
LEFT | RIGHT |