Rietveld Code Review Tool
Help | Bug tracker | Discussion group | Source code | Sign in
(600)

Delta Between Two Patch Sets: src/pkg/sort/sort.go

Issue 9612044: code review 9612044: sort: provide different stable sort algorithms (Closed)
Left Patch Set: diff -r 24deeb374803 https://code.google.com/p/go/ Created 10 years, 9 months ago
Right Patch Set: diff -r 41134e67106d https://code.google.com/p/go/ Created 10 years, 9 months ago
Left:
Right:
Use n/p to move between diff chunks; N/P to move between comments. Please Sign in to add in-line comments.
Jump to:
Left: Side by side diff | Download
Right: Side by side diff | Download
« no previous file with change/comment | « no previous file | src/pkg/sort/sort_test.go » ('j') | no next file with change/comment »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
LEFTRIGHT
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
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
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
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 */
LEFTRIGHT

Powered by Google App Engine
RSS Feeds Recent Issues | This issue
This is Rietveld f62528b