Snippet MergeSort

Dirac

22710180
Reaction score
147
JASS:
library MergeSort /* v3.0.1

*/uses/*
*/  LinkedListModule    /* thehelper.net/forums/showthread.php/168775-LinkedListModule

A tool for sorting linked lists inside structs.

***********************************************************************
*
*   textmacro MERGE_SORT takes METHOD_NAME, COMPARE_BOOLEAN
*       -   Run at the end of the struct.
*
***********************************************************************
*
*   DEMONSTRATION
*
*   struct UnitsByLife extends array
*       implement LinkedList
*       unit target
*       //! runtextmacro MERGE_SORT ("sort","GetWidgetLife(v1.target)>GetWidgetLife(v2.target)")
*   endstruct
*
*   Assuming that you're going to insert instances to the UnitsByLife's
*   base then you can call UnitsByLife.sort(UnitsByLife.base) to cause
*   instances of the linked list to be sorted depending on each unit's
*   current life. Reffer to the instances as "v1" and "v2"

**********************************************************************/

    //! textmacro MERGE_SORT takes METHOD_NAME, COMPARE_BOOLEAN
        
        //*********************************************************************
        //  Ok this method is entitled to split and merge constatly until there
        //  is nothing left to split.
        private static method $METHOD_NAME$Ex takes thistype v1, thistype end returns thistype
            local thistype v2=v1
            local thistype list=v1
            local thistype result=v1.prev
            
            //*********************************************************************
            //  If the last node end.prev of the list is equal to the first node
            //  v1 then skip.
            if v1==end.prev then
                return v1
            endif
            
            //*********************************************************************
            //  Find the halfway through the list by iterating two pointers forward
            //  one twice as fast as the other.
            loop
                set v2=v2.next
                set list=list.next
                exitwhen list==end
                set list=list.next
                exitwhen list==end
            endloop
            
            //*********************************************************************
            //  Now it calls this function again but for each v2 (from v1 up
            //  to the previous node from the v2 and from the v2 up to the end)
            set v1=$METHOD_NAME$Ex(v1,v2)
            set v2=$METHOD_NAME$Ex(v2,end)
            
            //*********************************************************************
            //  Merges the list using 2 pointers: v1 and v2.
            loop
                if $COMPARE_BOOLEAN$ then
                    
                    //*********************************************************************
                    //  If the pointers pass the compare method it means that v2 needs to
                    //  be placed behind v1.
                    set list=v2.next

                    //*********************************************************************
                    //  So we remove v2 from the list...
                    call v2.removeNode()

                    //*********************************************************************
                    //  ...and place it behind v1.
                    call v1.insertNode(v2)
                    
                    //*********************************************************************
                    //  After that we need v2 to point towards the node that was previously
                    //  pointing to v2.next before, that's why i stored it inside "list" to
                    //  now retreive it.
                    exitwhen list==end
                    set v2=list
                else
                    
                    //*********************************************************************
                    //  If the value doesn't pass the compare method it means there's no
                    //  need for moving (the list is fine) and moves along
                    set v1=v1.next
                    exitwhen v1==v2
                endif
            endloop
            return result.next
        endmethod
        
        //*********************************************************************
        //  head.next is the first value of the list and the head.
        static method $METHOD_NAME$ takes thistype head returns nothing
            call $METHOD_NAME$Ex(head.next,head)
        endmethod
    //! endtextmacro
    
endlibrary

Post at the hive including Demo Map
 

tooltiperror

Super Moderator
Reaction score
231
This thread is a mess. You have all this gigantic shit clogging it up :confused:

I would much rather use SortUtils.
  • Better documentation
  • Better interface
  • Not restricted to coding with structs
  • Speed differences are likely negligible
  • Code quality is better
  • Group->UnitArray functionality
  • I trust grim's testing and stability over yours
  • More verbosity
 

Nestharus

o-o
Reaction score
84
This thread is a mess. You have all this gigantic shit clogging it up :confused:

I would much rather use SortUtils.
  • Better documentation
  • Better interface
  • Not restricted to coding with structs
  • Speed differences are likely negligible
  • Code quality is better
  • Group->UnitArray functionality
  • I trust grim's testing and stability over yours
  • More verbosity

You need to actually learn about sorting algorithms before you make your comments ;p.


Quicker Sort and Merge Sort are completely different sorting algorithms. They each have their pros and cons and both are perfectly fine to have.


Quicker Sort is faster than Merge Sort in a lot of cases, but Quicker Sort is an unstable sort. Merge Sort is 100% stable (always taking the same amount of time to sort w/e data), but it's usually a bit slower than quicker sort.


However, there are improved Merge Sort algorithms out there. The one php uses is a modified Merge Sort that's quite a lot faster than the standard merge sort. Rather than just scoffing merge sort off, which I know you'll probably do anyways since I doubt you'll actually do any research into sorting algorithms, why not get Dirac to upgrade it to the algorithm php uses?



Also, there are other pros and cons between merge sort and quicker sort besides just the operation count.



Also, @Dirac, I doubt you'll be able to write a better tutorial on Merge Sort than what's currently out there. The wikipedia page on it is quite awesome and it includes animations as to how the algorithm works. There are also other websites with animations on all the different types of sorting.

I'm personally of the opinion that common well known algorithms like quicker sort, merge sort, etc, don't need to be explained in their specific resources as there are plenty of explanations out there. It's like an AVL Tree resource in c# doesn't explain the mechanics and theory behind the AVL Tree, they expect you to google it.


thehelper.net resources section is being extremely unreasonable -.-, hence why I've pretty much stopped submitting stuff here. I got fed up with it.
 

tooltiperror

Super Moderator
Reaction score
231
> You need to actually learn about sorting algorithms before you make your comments ;p.
Comments like these are probably ones that lead to people not liking you, so I suggest you do not make such comments in the future.

> Quicker Sort is faster than Merge Sort in a lot of cases, but Quicker Sort is an unstable sort. Merge Sort is 100% stable (always taking the same amount of time to sort w/e data), but it's usually a bit slower than quicker sort.
Quicksort should be fine for the amount of data you're sorting in Wc3..

> However, there are improved Merge Sort algorithms out there. The one php uses is a modified Merge Sort that's quite a lot faster than the standard merge sort
PHP generally uses a Quicksort, buddy.

http://php.net/sort
Note: Like most PHP sorting functions, sort() uses an implementation of » Quicksort.

>Rather than just scoffing merge sort off, which I know you'll probably do anyways since I doubt you'll actually do any research into sorting algorithms, why not get Dirac to upgrade it to the algorithm php uses?
These are the exact kind of shitty responses that you post that piss people off. Stop being such a douchebag.

If you did not read my entire post and just decided to attack me, you'll notice I listed other reasons of using SortUtils than the sorting method, which I specified as negligible for WC3.
 

Nestharus

o-o
Reaction score
84
Hmmm, maybe I was thinking of python ; )

Quicksort should be fine for the amount of data you're sorting in Wc3..

Actually, a bubble sort is good enough for most of the data you'd be handling in wc3. The time you might want a merge sort however is sorting something like unit kills for all units on an entire map to perhaps find the unit that killed the most unit. However, in that situation, it might be better to just use a Red Black Tree (I say red black as the tree would be constantly updated and searches might be rather infrequent).

If you did not read my entire post and just decided to attack me, you'll notice I listed other reasons of using SortUtils than the sorting method, which I specified as negligible for WC3.

I agreed with you on the other points ; P. I only focused on the point I didn't agree with : ). There's no point in saying /agree is there : P? Sry if you got the wrong impression ; ).



What I am saying is that some people may want a stable sort, which is why merge sort is used. Also, SortUtils actually uses quicker sort, but you probably already knew that ; ).


edit
oh yes, the reason why I assumed that you didn't quite know what you were talking about was because of this comment ;p
Speed differences are likely negligible

It made it sound like you thought they were like the same thing or w/e ^)^.
 

Dirac

22710180
Reaction score
147
@tooltiperror
I'm sorry that i failed to explain why is this different from other sorts because you obviously don't get it.

Most sort would just go ahead and compare values and arrange them by smallest to greatest or vice-versa
Merge Sort is ideal when dealing with linked lists, and thats why being "restricted to coding with structs" isn't a bad thing, it's most likely the whole idea. So please stop arguing which is the best sort method, for this type of work Merge Sort is the best.
It also allows you to put inside the compare method whatever you want (you can deal with unit values or whatever), if you wish to sort a struct by one of their members you go ahead, you can do it with this system, you can't with SortUtils.

Would you like this thread more if i removed the whole simple explanation i did there? Because i can't really see that "clogging shit" you speak of.
It annoys me that you won't approve this resource because you don't trust my stability, what does that even mean? are you not approving any of my resources?
I find your criticism very destructive.

@Nestharus
If people were to google how merge sort works they would most likely understand the logic behind the sorting, but how to apply it to code is another whole explanation, which is what i'm doing here. The fact that i post a whole guide on how it works it's just a gesture of good will. (because there's no reason of why i should)
From you i wasn't expecting lessons on how to write a tutorial, but ways to improve the code / algorithm.

P.S. SortUtils is one big code bloat, like huge, he coded structs for every type of comparison, this snippet can handle them all,also the API is extremely extensive.
 

Nestharus

o-o
Reaction score
84
Your code is simple and straight forward =), however, it won't do well sorting runs ; P.


Try splitting based on runs rather than halves. You'll get a better operation count.
 

tooltiperror

Super Moderator
Reaction score
231
> I'm sorry that i failed to explain why is this different from other sorts because you obviously don't get it.
These are arrogant comments that are completely unnecessary. You should stop saying them, if you don't get it.

> Most sort would just go ahead and compare values and arrange them by smallest to greatest or vice-versa
Alright... is this different from a Mergesort?

> Merge Sort is ideal when dealing with linked lists, and thats why being "restricted to coding with structs" isn't a bad thing, it's most likely the whole idea. So please stop arguing which is the best sort method, for this type of work Merge Sort is the best.
Where did I say not to use a Mergesort? I said SortUtils was a better library, not because it uses a Quicksort, but for the reasons I listed in my post. So stop making bullshit conclusions, I don't care what sorting algorithm you use. And restricting me to code in a struct can be considered bad, SortUtils doesn't force me to code a struct, but can accomplish the same things that this does.

> It annoys me that you won't approve this resource because you don't trust my stability, what does that even mean? are you not approving any of my resources?
It means that I don't know if I would use a resource you have coded until I tested it extensively myself. I find this the case with most of the users on this site. I am not approving your resources for different reasons unique to your resources. Generally your code is things that have been done before and you just did it with a new interface, slight speed gains, and/or a small difference I've never needed. When your code is like this, it is very hard to review. Other coders make creative new things that are more exciting to review, hence why they are usually reviewed first.

> I find your criticism very destructive.
That's tough, all I posted was reasons I would rather use SortUtils, and I said that your thread was all clogged up. If you can not handle this I would suggest not submitting resources in the future.

You seem to think that I do not comprehend what this resource is, or why to use it, or how it works. I will assure you I understand it completely, and still do not like it. SortUtils and [LJASS]SortStructs[/LJASS] is likely all that I will ever need. You could have implemented this functionality without reinventing the wheel.
 

Nestharus

o-o
Reaction score
84
You seem to think that I do not comprehend what this resource is, or why to use it, or how it works. I will assure you I understand it completely, and still do not like it. SortUtils and SortStructs is likely all that I will ever need. You could have implemented this functionality without reinventing the wheel.

People should still have the option of either using a merge sort or a quicker sort though =).

Two resources may have the exact same functionality but have different strengths and weaknesses. That's why there are so many different sorting algorithms and trees on the net ; P.

I say the above paragraph to the below quote
You could have implemented this functionality without reinventing the wheel.



Also, I'm not sure where Dirac has reinvented the wheel here unless you can link me another approved resource that is a merge sort ^_-.
 

Dirac

22710180
Reaction score
147
@tooltiperror
I would like to rephrase that first quote you had to "I'm sorry because i didn't explain how the system works, it's not clear therefore you're not getting it" I'm not trying to teach you a lesson, i really mean it when i say that i didn't quite explain why would anyone use this over SortUtils, and the rest of that post tries to explain it. I feel that some of the quotes you point out are senseless if you read them out of context.
This system isn't trying to reinvent the wheel and this is why i think you don't get why is it different from other sorts. I'm trying to sort Linked Lists try that with any other sorting system you find and it will be impossible to do. I'm not trying to beat other system's speed. I'm not trying to render other systems useless. This system has its own usefulness.

@Nestharus
Try splitting based on runs rather than halves. You'll get a better operation count.
I'm not following.
I read somewhere that QuickSort performs faster when sorting random number arrays for the first time, after that if a node gets modified and gets re-sorted MergeSort performs better.
 

phyrex1an

Staff Member and irregular helper
Reaction score
446
Isn't there some standard list implementation somewhere? That you have to construct a new list just because you want it sorted kinda reduces the usefulness of this. I'd expect it to work well with some list implementation already in use. Perhaps you could abstract the access to next and prev in some way so that you could use this together with whatever lists you're already dealing with?

I kinda dislike the idea of tying the sort order to the concrete class which is sorted. With this you can't sort PlayerKills in both ascending or descending order (without resorting to a state-full compare method).

The example is rather bad. Who wants to sort random integers anyway? Show how you sort units according to distance from a point without repetitively recalculating the distance or something like that. Bonus points if you make up a real example which sorts on more than two variables at once [del]just to show people why SortUtils is a hack compared to this.[/del] [ins]Scratch that, you can sort on more than two variables with SortUtils if you sacrifice type safety...[/ins]

Edit: I agree with tooltip that you shouldn't have that description of what merge sort does in the submission post. It might be useful somewhere else but here it's just confusing. I imagine that some people think that you need to understand your (not exactly great) description of merge sort just to understand how to use this.
 

Dirac

22710180
Reaction score
147
That you have to construct a new list just because you want it sorted kinda reduces the usefulness of this.
The list is automatically created along with the allocation methods

Perhaps you could abstract the access to next and prev in some way so that you could use this together with whatever lists you're already dealing with?
next and prev are public, why would you want different linked lists in your struct? Remember you can allocate nodes, and use them as normal struct instances.

With this you can't sort PlayerKills in both ascending or descending order (without resorting to a state-full compare method).
Wrong, if you iterate the list the other way around (instead of looping this.next you loop this.prev) you can have both orders.

The example is rather bad. Who wants to sort random integers anyway? Show how you sort units according to distance from a point without repetitively recalculating the distance or something like that. Bonus points if you make up a real example which sorts on more than two variables at once just to show people why SortUtils is a hack compared to this
I'll upload a demo map with proper examples later, also, how on earth do you plan to sort anything else more than integers or reals with sort utils? I really can't understand tooltiperror when he says that sort utils is a good resource - it's good if you would like to learn how to count. How about you want to sort players by the amount of kills they have... how are you going to know which was the player with most kills after the sort is completed?

I agree with tooltip that you shouldn't have that description of what merge sort does in the submission post. It might be useful somewhere else but here it's just confusing. I imagine that some people think that you need to understand your (not exactly great) description of merge sort just to understand how to use this.
The description was more like the way i gave sense to the code rather than a way to explain merge sorts, it's not surprising that other people don't get it since I almost wrote out of my rambling logic.

Removed the description and updated the resource, now it allows multiple lists per struct
 

tooltiperror

Super Moderator
Reaction score
231
> How about you want to sort players by the amount of kills they have... how are you going to know which was the player with most kills after the sort is completed?

JASS:
library Example requires SortUtils

globals
    integer array Kills[12]  // I'll assume this is already filled up
endglobals

struct PlayerKills extends array
    player who
    integer kills

    private static method onInit takes nothing returns nothing
        local integer i = 0
        
        loop
            set thistype<i>.kills = Kills<i>
            set thistype<i>.who   = Player(i)
            set i = i + 1

            exitwhen i == 12
        endloop
    endmethod
endstruct

private function Comparison takes PlayerKills i returns real
    return I2R(PlayerKills<i>.kills)
endfunction

private function onInit takes nothing returns nothing
    local StructArray arr = StructArray.create(12)
    local integer i = 0

    loop
        arr<i> = PlayerKills<i>
        set i = i + 1

        exitwhen i == 12
    endloop

    call SortStructs(arr, Comparison)
    call BJDebugMsg(&quot;The player with the most kills is &quot; + GetPlayerName(arr[0].who))
endfunction

endlibrary
</i></i></i></i></i></i>
 

phyrex1an

Staff Member and irregular helper
Reaction score
446
The list is automatically created along with the allocation methods

next and prev are public, why would you want different linked lists in your struct? Remember you can allocate nodes, and use them as normal struct instances.

Wrong, if you iterate the list the other way around (instead of looping this.next you loop this.prev) you can have both orders.
Right. But that completely misses the point.

Here is a more complex example:
I have a struct representing heroes
JASS:
struct Hero
     private unit realHero
     private integer kills
     private integer sexyPoints
     private real travelDistance
endstruct

Now I have multiple multiboards that displays all this information to the players. There is a global multi board (where all heroes occurs) and several team multiboards (where the heroes from each team occurs). There are between 1 and 4 teams, depending on in game settings ("game mode"). Players can ofc change team during the game.
Naturally, I want to be able to sort each of these multiboards on kills, sexyPoints or travelDistance (also depending on game mode).
So I need a sort library. How do I do this with your library?

This is how I expect it to work (functionally, I couldn't care less about the syntactical bits):
JASS:
local Hero array heroes // initialized with the Hero instances for each player
local HeroList array teamHeroes // initialized with the Hero instances for each team
local HeroList allHeroes // initialized with all Hero instances (so the same content as heroes but in a different order)
local int gameMode //
if (gameMode == killEverything) then
      loop
            exitwhen i == numberOfTeams
            call teamHeroes<i>.sort(function compareKills)
            set i = i+1
      endloop
      call allHeroes.sort(function compareKills)
endif
// ...</i>


The points here are:
1. Not only must I be able to have more than one list per _struct type_, each _struct instance_ must be able to be a member of more than one list at once.
2. Not only must I be able to sort different lists in different ways, I must be able to sort the same list in different ways.

Check for example: http://msdn.microsoft.com/en-us/library/w56d4y5z.aspx or http://download.oracle.com/javase/1...ml#sort(java.util.List, java.util.Comparator)

SortUtils can do both of these things (but on arrays and not lists...). The code sucks, but it can do it.

Note: I don't have wc3 installed so I can't check your example map. It's possible that you've fixed these two points and I just don't see how :p
 

Dirac

22710180
Reaction score
147
Nono phyrex1an your point is good, last update i added functionality on multiple lists so you can sort lists for each player, but the compare method for different variables is missing. I'll probably add another module that takes a function as an argument to put into a trigger and evaluate as it's compare method.

@tooltiperror
That looks like a lot of overhead for sorting something. The single fact that you have to loop twice to put everything inside an array its just stupid, here you put your variables along you allocate the nodes for your list and just type list.sort()
 

phyrex1an

Staff Member and irregular helper
Reaction score
446
Isn't Radix sort faster than merge sort for all significant cases when multi-threading isn't possible?
Radix sort is asymptotically faster than all comparison based sorts. However, you can't sort all the things with radix sort. With radix sort you're more or less restricted to sorting (bounded) ints. Radix sort isn't really relevant in this case :)
 

Dirac

22710180
Reaction score
147
I'm sorry phyrex1an but there's no way to do what you're asking me without using function interfaces, if you wish to sort multiple variables you should create 1 struct per variable.
I don't think JASS supports Radix sort, and even if, this is sorting for linked lists, MergeSort is the best.
 
General chit-chat
Help Users
  • No one is chatting at the moment.

      The Helper Discord

      Staff online

      • Ghan
        Administrator - Servers are fun

      Members online

      Affiliates

      Hive Workshop NUON Dome World Editor Tutorials

      Network Sponsors

      Apex Steel Pipe - Buys and sells Steel Pipe.
      Top