Sort for container/list

[Yiannis Marangos]

Hi,

I'm new to Go and as far as I have read slices are prefered than list.List.
But how someone can sort list.List? As I understand sort.Interface can not be used.

Regards.

[parais...@gmail.com]

Create your own type embedding a list and Add the sort interface methods.

type Foo struct{

 *list.List 

}

func (f *Foo) Reverse(i,j int){ ... }

 ....

Of course , if list.List was an interface itself it would have been better at first place.

[Konstantin Khomoutov]

On Mon, 11 Jan 2016 06:01:36 -0800 (PST)
parais...@gmail.com wrote:

> Create your own type embedding a list and Add the sort interface
> methods.
>
> type Foo struct{
> *list.List
> }
>
> func (f *Foo) Reverse(i,j int){ ... }

^^^ I think you rather meant implementing sort.Interface [1].

The problem is that this interface while *in theory* applicable to any
container type which implements indexing, is still targeted for
containers for which index lookup is a O(1) operation, but for linked
lists it's O(N). So I'd say to sort a container/list collection,
some other approach is called for -- like using a temporary supporting
slice which would map collection indexes to elements while sorting.
But this precludes using of the standard mechanisms of the sort package.

Another approach could be just making a slice of (pointers to) elements
in the linked list, sorting them using the sort package and then
creating another linked list off the slice's contents.

1. https://golang.org/pkg/sort/#Interface

[Nick Craig-Wood]

Or merge sort for lists

http://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.html


--
Nick Craig-Wood <ni...@craig-wood.com> -- http://www.craig-wood.com/nick

[Ilya Kostarev]

Or insertion sort because
- insertion operation very cheap on list
- since list used quite rare in common libs (like stdlib) you most
likely would produce it yourself inserting anyway, and you can sort
while producing

--
Ilya Kostarev