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
Assignees
Milestone

Comments

@rsc
Copy link
Contributor

@rsc 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 rsc commented Sep 12, 2012

Comment 1:

Labels changed: added go1.1maybe.

@rsc
Copy link
Contributor Author

@rsc rsc commented Dec 10, 2012

Comment 2:

Labels changed: added size-m.

@rsc
Copy link
Contributor Author

@rsc rsc commented Dec 10, 2012

Comment 3:

Labels changed: added suggested.

@dsymonds
Copy link
Member

@dsymonds dsymonds commented Feb 13, 2013

Comment 4:

Owner changed to @dsymonds.

Status changed to Started.

@dsymonds
Copy link
Member

@dsymonds dsymonds commented Feb 14, 2013

Comment 5:

This issue was closed by revision 78cee8b.

Status changed to Fixed.

@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.
Projects
None yet
Linked pull requests

Successfully merging a pull request may close this issue.

None yet
3 participants
You can’t perform that action at this time.