Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

sort: possible way to use fewer comparisons #2585

Closed
rsc opened this issue Dec 19, 2011 · 5 comments
Closed

sort: possible way to use fewer comparisons #2585

rsc opened this issue Dec 19, 2011 · 5 comments
Labels
FrozenDueToAge Suggested Issues that may be good for new contributors looking for work to do.
Milestone

Comments

@rsc
Copy link
Contributor

rsc commented Dec 19, 2011

the current pivot loop retests data[b] 
each time it moves c.  that's needlessly
repeated work.  maybe something like
this is better.  the comparisons in the
second loop when c == b+1 are also
redundant, but a smaller source of comparisons.

should measure number of comparisons and
do this if it makes sense.

    for {
        for b < c {
            if data.Less(b, pivot) {  // data[b] < pivot
                b++
            } else if !data.Less(pivot, b) {  // data[b] = pivot
                data.Swap(a, b)
                a++
                b++
            } else {
                break
            }
        }
        for b < c {
            if data.Less(pivot, c-1) {  // data[c-1] > pivot
                c--
            } else if !data.Less(c-1, pivot) {  // data[c-1] = pivot
                data.Swap(c-1, d-1)
                c--
                d--
            } else {
                break
            }
        }
        if b >= c {
            break
        }
        // data[b] > pivot; data[c-1] < pivot
        data.Swap(b, c-1)
        b++
        c--
    }
@rsc
Copy link
Contributor Author

rsc commented Sep 12, 2012

Comment 1:

Labels changed: added go1.1maybe.

@rsc
Copy link
Contributor Author

rsc commented Dec 10, 2012

Comment 2:

Labels changed: added size-m.

@rsc
Copy link
Contributor Author

rsc commented Dec 10, 2012

Comment 3:

Labels changed: added suggested.

@dsymonds
Copy link
Contributor

Comment 4:

Owner changed to @dsymonds.

Status changed to Started.

@dsymonds
Copy link
Contributor

Comment 5:

This issue was closed by revision 78cee8b.

Status changed to Fixed.

@rsc rsc added fixed Suggested Issues that may be good for new contributors looking for work to do. labels Feb 14, 2013
@rsc rsc added this to the Go1.1 milestone Apr 14, 2015
@rsc rsc removed the go1.1maybe label Apr 14, 2015
@golang golang locked and limited conversation to collaborators Jun 24, 2016
This issue was closed.
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Labels
FrozenDueToAge Suggested Issues that may be good for new contributors looking for work to do.
Projects
None yet
Development

No branches or pull requests

3 participants