Better Sorting Method Than Cocktail Sort

Author

Message

anwserman

13

Years of Service

User Offline

Joined: 20th May 2011

Location: Wisconsin

Posted: 10th Jan 2012 19:16

Link

I'm currently stuck -

I implemented a Cocktail Sort into my application, to help speed up my program logic - the speed improvements are fantastic, but I know that I could get faster results than using a modified bubblesort algorithm.

Problem is, all of the more involved sorting algorithms I've looked up online are based on one field alone, when I need to sort on multiple fields.

My data type is:

+ Code Snippet

type TYPE_WATER_DROPLET
    X as integer ---- third sorted field, descending
    Y as integer ---- second sorted field, descending
    active as integer ---- first sorted field, descending
    id as integer ---- not sorted on
endtype

I was able to get Cocktail sort working using my knowledge of overriding sort functions in Visual Basic, but I'm not sure how to do this with other ones - like Insert or Quicksort. Anyone have any ideas?

Hi there. My name is Dug. I have just met you, and I love you.

Back to top

Profile PM Email Website

Hodgey

15

Years of Service

User Offline

Joined: 10th Oct 2009

Location: Australia

Posted: 14th Jan 2012 12:47

Link

I love these sorts (I also love puns) of challenges.

I had a go at sorting your UDT using the "Insertion" sort. It displays an elapsed time so you can compare it with your current sorting algorithms.

// our UDT
type TYPE_WATER_DROPLET
    X as integer //---- third sorted field, descending
    Y as integer //---- second sorted field, descending
    active as integer //---- first sorted field, descending
    id as integer //---- not sorted on
endtype

// Create an array
SizeOfArray = 10
Dim Array[SizeOfArray] as Type_Water_Droplet

// Fill each element of the array with a random number
For n = 0 to SizeOfArray
    Array[n].X = Random(1, 1000)
    Array[n].Y = Random(1, 1000)
    Array[n].active = Random(1, 1000)
Next n

// Sort each element
// Using the insertion sort
CurrentValue as integer
CurrentIndex as integer = 1

SortIndex as integer

BeginTime# = timer()

While CurrentIndex <= SizeOfArray
    SortIndex = 0
    // dealing with the already sorted half of the array
    While SortIndex < CurrentIndex

// sort the x's
        If Array[CurrentIndex].X > Array[SortIndex].X
            // Store the larger value and then shuffle the sorted part down
            Temp = Array[CurrentIndex].X

// shuffle the portion of the sorted part of the array down to make room for the value to be inserted
            SortCount = SortIndex
            EndIndex = CurrentIndex
            While EndIndex > SortCount
                Array[EndIndex].X = Array[EndIndex-1].X
                EndIndex = EndIndex - 1
            Endwhile

// insert the larger value into its correct place
            Array[SortIndex].X = Temp

Endif

// Sort the y's
        If Array[CurrentIndex].Y > Array[SortIndex].Y
            // Store the larger value and then shuffle the sorted part down
            Temp = Array[CurrentIndex].Y

// shuffle the portion of the sorted part of the array down to make room for the value to be inserted
            SortCount = SortIndex
            EndIndex = CurrentIndex
            While EndIndex > SortCount
                Array[EndIndex].Y = Array[EndIndex-1].Y
                EndIndex = EndIndex - 1
            Endwhile

// insert the larger value into its correct place
            Array[SortIndex].Y = Temp

Endif

// Sort the actives's
        If Array[CurrentIndex].Active > Array[SortIndex].Active
            // Store the larger value and then shuffle the sorted part down
            Temp = Array[CurrentIndex].Active

// shuffle the portion of the sorted part of the array down to make room for the value to be inserted
            SortCount = SortIndex
            EndIndex = CurrentIndex
            While EndIndex > SortCount
                Array[EndIndex].Active = Array[EndIndex-1].Active
                EndIndex = EndIndex - 1
            Endwhile

// insert the larger value into its correct place
            Array[SortIndex].Active = Temp

Endif

// increase the sort index
        SortIndex = SortIndex + 1
    Endwhile

// Increase the current index
    CurrentIndex = CurrentIndex + 1
Endwhile

Endtime# = timer()

ElapsedTime# = EndTime# - BeginTime#
// create a bunch of text objects to display our results
For n = 0 to SizeOfArray
    //For the x's
    CreateText(n, str(Array[n].X))
    SetTextPosition(n, 0, n*8)

// For the y's
    CreateText(n+11, str(Array[n].Y))
    SetTextPosition(n+11, 20, n*8)

// The actives
    CreateText(n+22, str(Array[n].Active))
    SetTextPosition(n+22, 40, n*8)

Next n

// Create a text object for the elapsed time
CreateText(40, str(ElapsedTime#) + " sec")
SetTextPosition(40, 60, 80)

// a loop
do
    sync()
loop

+ Code Snippet

// our UDT
type TYPE_WATER_DROPLET
    X as integer //---- third sorted field, descending
    Y as integer //---- second sorted field, descending
    active as integer //---- first sorted field, descending
    id as integer //---- not sorted on
endtype

// Create an array
SizeOfArray = 10
Dim Array[SizeOfArray] as Type_Water_Droplet

// Fill each element of the array with a random number
For n = 0 to SizeOfArray
    Array[n].X = Random(1, 1000)
    Array[n].Y = Random(1, 1000)
    Array[n].active = Random(1, 1000)
Next n

// Sort each element
// Using the insertion sort
CurrentValue as integer
CurrentIndex as integer = 1

SortIndex as integer

BeginTime# = timer()

While CurrentIndex <= SizeOfArray
    SortIndex = 0
    // dealing with the already sorted half of the array
    While SortIndex < CurrentIndex

        // sort the x's
        If Array[CurrentIndex].X > Array[SortIndex].X
            // Store the larger value and then shuffle the sorted part down
            Temp = Array[CurrentIndex].X

            // shuffle the portion of the sorted part of the array down to make room for the value to be inserted
            SortCount = SortIndex
            EndIndex = CurrentIndex
            While EndIndex > SortCount
                Array[EndIndex].X = Array[EndIndex-1].X
                EndIndex = EndIndex - 1
            Endwhile


            // insert the larger value into its correct place
            Array[SortIndex].X = Temp

        Endif

        // Sort the y's
        If Array[CurrentIndex].Y > Array[SortIndex].Y
            // Store the larger value and then shuffle the sorted part down
            Temp = Array[CurrentIndex].Y

            // shuffle the portion of the sorted part of the array down to make room for the value to be inserted
            SortCount = SortIndex
            EndIndex = CurrentIndex
            While EndIndex > SortCount
                Array[EndIndex].Y = Array[EndIndex-1].Y
                EndIndex = EndIndex - 1
            Endwhile


            // insert the larger value into its correct place
            Array[SortIndex].Y = Temp

        Endif

        // Sort the actives's
        If Array[CurrentIndex].Active > Array[SortIndex].Active
            // Store the larger value and then shuffle the sorted part down
            Temp = Array[CurrentIndex].Active

            // shuffle the portion of the sorted part of the array down to make room for the value to be inserted
            SortCount = SortIndex
            EndIndex = CurrentIndex
            While EndIndex > SortCount
                Array[EndIndex].Active = Array[EndIndex-1].Active
                EndIndex = EndIndex - 1
            Endwhile


            // insert the larger value into its correct place
            Array[SortIndex].Active = Temp

        Endif


        // increase the sort index
        SortIndex = SortIndex + 1
    Endwhile

    // Increase the current index
    CurrentIndex = CurrentIndex + 1
Endwhile

Endtime# = timer()

ElapsedTime# = EndTime# - BeginTime#
// create a bunch of text objects to display our results
For n = 0 to SizeOfArray
    //For the x's
    CreateText(n, str(Array[n].X))
    SetTextPosition(n, 0, n*8)

    // For the y's
    CreateText(n+11, str(Array[n].Y))
    SetTextPosition(n+11, 20, n*8)

    // The actives
    CreateText(n+22, str(Array[n].Active))
    SetTextPosition(n+22, 40, n*8)

Next n

// Create a text object for the elapsed time
CreateText(40, str(ElapsedTime#) + " sec")
SetTextPosition(40, 60, 80)

// a loop
do
    sync()
loop

Back to top

Profile PM Email

anwserman

13

Years of Service

User Offline

Joined: 20th May 2011

Location: Wisconsin

Posted: 14th Jan 2012 16:53

Link

Hey Hodgey -
Thank you for the contribution! However, I think there is a bug with your code. It isn't as apparent with a random dataset, but I came up with a sample base set.

The UDT's values are supposed to be kept grouped together. Instead, this insertion sort sorts out the fields independently of each other.

For instance, the UDT with values of:

+ Code Snippet

X=54
Y=45
Active=1

should come out in the list before

+ Code Snippet

X=559
Y=410
Active=0

Because the active field is of a higher value than the second one. Does that make sense? I appreciate your effort, and I'll try to look at your code to see if I can further make changes.

-Jeff

// our UDT
type TYPE_WATER_DROPLET
    X as integer //---- third sorted field, descending
    Y as integer //---- second sorted field, descending
    active as integer //---- first sorted field, descending
    id as integer //---- not sorted on
endtype

// Create an array
SizeOfArray = 10
Dim Array[SizeOfArray] as Type_Water_Droplet

// Fill each element of the array with a random number
remstart
For n = 0 to SizeOfArray
    Array[n].X = Random(1, 1000)
    Array[n].Y = Random(1, 1000)
    Array[n].active = Random(1, 1000)

if Array[n].active >= 500
        Array[n].active = 0
    else
        Array[n].active = 1
    endif
Next n
remend

Array[0].X = 23
    Array[0].Y = 55
    Array[0].active = 0

Array[1].X = 421
    Array[1].Y = 86
    Array[1].active = 1

Array[2].X = 999
    Array[2].Y = 445
    Array[2].active = 1

Array[3].X = 742
    Array[3].Y = 548
    Array[3].active = 1

Array[4].X = 44
    Array[4].Y = 123
    Array[4].active = 1

Array[5].X = 764
    Array[5].Y = 3
    Array[5].active = 0

Array[6].X = 1999
    Array[6].Y = 300
    Array[6].active = 1

Array[7].X = 559
    Array[7].Y = 410
    Array[7].active = 0

Array[8].X = 111
    Array[8].Y = 865
    Array[8].active = 1

Array[9].X = 123
    Array[9].Y = 201
    Array[9].active = 0

Array[10].X = 54
    Array[10].Y = 45
    Array[10].active = 1
// Sort each element
// Using the insertion sort
CurrentValue as integer
CurrentIndex as integer = 1

SortIndex as integer

BeginTime# = timer()

While CurrentIndex <= SizeOfArray
    SortIndex = 0
    // dealing with the already sorted half of the array
    While SortIndex < CurrentIndex

// sort the x's
        If Array[CurrentIndex].X > Array[SortIndex].X
            // Store the larger value and then shuffle the sorted part down
            Temp = Array[CurrentIndex].X

// shuffle the portion of the sorted part of the array down to make room for the value to be inserted
            SortCount = SortIndex
            EndIndex = CurrentIndex
            While EndIndex > SortCount
                Array[EndIndex].X = Array[EndIndex-1].X
                EndIndex = EndIndex - 1
            Endwhile

// insert the larger value into its correct place
            Array[SortIndex].X = Temp

Endif

// Sort the y's
        If Array[CurrentIndex].Y > Array[SortIndex].Y
            // Store the larger value and then shuffle the sorted part down
            Temp = Array[CurrentIndex].Y

// shuffle the portion of the sorted part of the array down to make room for the value to be inserted
            SortCount = SortIndex
            EndIndex = CurrentIndex
            While EndIndex > SortCount
                Array[EndIndex].Y = Array[EndIndex-1].Y
                EndIndex = EndIndex - 1
            Endwhile

// insert the larger value into its correct place
            Array[SortIndex].Y = Temp

Endif

// Sort the actives's
        If Array[CurrentIndex].Active > Array[SortIndex].Active
            // Store the larger value and then shuffle the sorted part down
            Temp = Array[CurrentIndex].Active

// shuffle the portion of the sorted part of the array down to make room for the value to be inserted
            SortCount = SortIndex
            EndIndex = CurrentIndex
            While EndIndex > SortCount
                Array[EndIndex].Active = Array[EndIndex-1].Active
                EndIndex = EndIndex - 1
            Endwhile

// insert the larger value into its correct place
            Array[SortIndex].Active = Temp

Endif

// increase the sort index
        SortIndex = SortIndex + 1
    Endwhile

// Increase the current index
    CurrentIndex = CurrentIndex + 1
Endwhile

Endtime# = timer()

ElapsedTime# = EndTime# - BeginTime#
// create a bunch of text objects to display our results
For n = 0 to SizeOfArray
    //For the x's
    CreateText(n, str(Array[n].X))
    SetTextPosition(n, 0, n*8)

// For the y's
    CreateText(n+11, str(Array[n].Y))
    SetTextPosition(n+11, 20, n*8)

// The actives
    CreateText(n+22, str(Array[n].Active))
    SetTextPosition(n+22, 40, n*8)

Next n

// Create a text object for the elapsed time
CreateText(40, str(ElapsedTime#) + " sec")
SetTextPosition(40, 60, 80)

// a loop
do
    sync()
loop

+ Code Snippet

// our UDT
type TYPE_WATER_DROPLET
    X as integer //---- third sorted field, descending
    Y as integer //---- second sorted field, descending
    active as integer //---- first sorted field, descending
    id as integer //---- not sorted on
endtype

// Create an array
SizeOfArray = 10
Dim Array[SizeOfArray] as Type_Water_Droplet

// Fill each element of the array with a random number
remstart
For n = 0 to SizeOfArray
    Array[n].X = Random(1, 1000)
    Array[n].Y = Random(1, 1000)
    Array[n].active = Random(1, 1000)

    if Array[n].active >= 500
        Array[n].active = 0
    else
        Array[n].active = 1
    endif
Next n
remend

    Array[0].X = 23
    Array[0].Y = 55
    Array[0].active = 0

    Array[1].X = 421
    Array[1].Y = 86
    Array[1].active = 1

    Array[2].X = 999
    Array[2].Y = 445
    Array[2].active = 1

    Array[3].X = 742
    Array[3].Y = 548
    Array[3].active = 1

    Array[4].X = 44
    Array[4].Y = 123
    Array[4].active = 1

    Array[5].X = 764
    Array[5].Y = 3
    Array[5].active = 0

    Array[6].X = 1999
    Array[6].Y = 300
    Array[6].active = 1

    Array[7].X = 559
    Array[7].Y = 410
    Array[7].active = 0

    Array[8].X = 111
    Array[8].Y = 865
    Array[8].active = 1

    Array[9].X = 123
    Array[9].Y = 201
    Array[9].active = 0

    Array[10].X = 54
    Array[10].Y = 45
    Array[10].active = 1
// Sort each element
// Using the insertion sort
CurrentValue as integer
CurrentIndex as integer = 1

SortIndex as integer

BeginTime# = timer()

While CurrentIndex <= SizeOfArray
    SortIndex = 0
    // dealing with the already sorted half of the array
    While SortIndex < CurrentIndex

        // sort the x's
        If Array[CurrentIndex].X > Array[SortIndex].X
            // Store the larger value and then shuffle the sorted part down
            Temp = Array[CurrentIndex].X

            // shuffle the portion of the sorted part of the array down to make room for the value to be inserted
            SortCount = SortIndex
            EndIndex = CurrentIndex
            While EndIndex > SortCount
                Array[EndIndex].X = Array[EndIndex-1].X
                EndIndex = EndIndex - 1
            Endwhile


            // insert the larger value into its correct place
            Array[SortIndex].X = Temp

        Endif

        // Sort the y's
        If Array[CurrentIndex].Y > Array[SortIndex].Y
            // Store the larger value and then shuffle the sorted part down
            Temp = Array[CurrentIndex].Y

            // shuffle the portion of the sorted part of the array down to make room for the value to be inserted
            SortCount = SortIndex
            EndIndex = CurrentIndex
            While EndIndex > SortCount
                Array[EndIndex].Y = Array[EndIndex-1].Y
                EndIndex = EndIndex - 1
            Endwhile


            // insert the larger value into its correct place
            Array[SortIndex].Y = Temp

        Endif

        // Sort the actives's
        If Array[CurrentIndex].Active > Array[SortIndex].Active
            // Store the larger value and then shuffle the sorted part down
            Temp = Array[CurrentIndex].Active

            // shuffle the portion of the sorted part of the array down to make room for the value to be inserted
            SortCount = SortIndex
            EndIndex = CurrentIndex
            While EndIndex > SortCount
                Array[EndIndex].Active = Array[EndIndex-1].Active
                EndIndex = EndIndex - 1
            Endwhile


            // insert the larger value into its correct place
            Array[SortIndex].Active = Temp

        Endif


        // increase the sort index
        SortIndex = SortIndex + 1
    Endwhile

    // Increase the current index
    CurrentIndex = CurrentIndex + 1
Endwhile

Endtime# = timer()

ElapsedTime# = EndTime# - BeginTime#
// create a bunch of text objects to display our results
For n = 0 to SizeOfArray
    //For the x's
    CreateText(n, str(Array[n].X))
    SetTextPosition(n, 0, n*8)

    // For the y's
    CreateText(n+11, str(Array[n].Y))
    SetTextPosition(n+11, 20, n*8)

    // The actives
    CreateText(n+22, str(Array[n].Active))
    SetTextPosition(n+22, 40, n*8)

Next n

// Create a text object for the elapsed time
CreateText(40, str(ElapsedTime#) + " sec")
SetTextPosition(40, 60, 80)

// a loop
do
    sync()
loop

Hi there. My name is Dug. I have just met you, and I love you.

Back to top

Profile PM Email Website

anwserman

13

Years of Service

User Offline

Joined: 20th May 2011

Location: Wisconsin

Posted: 14th Jan 2012 17:07 Edited at: 14th Jan 2012 17:13

Link

So, I threw in my current sorting method into your framework Hodgey, just to see how fast my code was.... and I found a sorting bug - the X values weren't being sorted correctly (ascending and not descending!)

So I really thank you for attempting this, because I would have been blissfully unaware otherwise.

I have attached my Cocktail sort with your framework base, so you can see how my code sorts out the array. It's quite fast, but that could be due to the small dataset (which bubblesorts excel at completing faster.)

BTW, I'll be putting you in my "thank you's" for my game - I appreciate you pointing me in the right direction

EDIT: The items with an active value of 0 are not sorted because they're ignored by the game during gameplay anyway, and I'd rather not spend time sorting values that won't be used anyway.

// our UDT
type TYPE_WATER_DROPLET
    X as integer //---- third sorted field, descending
    Y as integer //---- second sorted field, descending
    active as integer //---- first sorted field, descending
    id as integer //---- not sorted on
endtype

// Create an array
SizeOfArray = 10
Dim Array[SizeOfArray] as Type_Water_Droplet

Array[0].X = 23
    Array[0].Y = 55
    Array[0].active = 0

Array[1].X = 421
    Array[1].Y = 86
    Array[1].active = 1

Array[2].X = 999
    Array[2].Y = 445
    Array[2].active = 1

Array[3].X = 742
    Array[3].Y = 548
    Array[3].active = 1

Array[4].X = 44
    Array[4].Y = 123
    Array[4].active = 1

Array[5].X = 764
    Array[5].Y = 3
    Array[5].active = 0

Array[6].X = 1999
    Array[6].Y = 300
    Array[6].active = 1

Array[7].X = 559
    Array[7].Y = 410
    Array[7].active = 0

Array[8].X = 111
    Array[8].Y = 300  `865
    Array[8].active = 1

Array[9].X = 123
    Array[9].Y = 201
    Array[9].active = 0

Array[10].X = 54
    Array[10].Y = 45
    Array[10].active = 1
// Sort each element
// Using the insertion sort
CurrentValue as integer
CurrentIndex as integer = 1

SortIndex as integer

BeginTime# = timer()

SortWaterDroplets()

Endtime# = timer()

ElapsedTime# = EndTime# - BeginTime#
// create a bunch of text objects to display our results
For n = 0 to SizeOfArray
    //For the x's
    CreateText(n, str(Array[n].X))
    SetTextPosition(n, 0, n*8)

// For the y's
    CreateText(n+11, str(Array[n].Y))
    SetTextPosition(n+11, 20, n*8)

// The actives
    CreateText(n+22, str(Array[n].Active))
    SetTextPosition(n+22, 40, n*8)

Next n

// Create a text object for the elapsed time
CreateText(40, str(ElapsedTime#) + " sec")
SetTextPosition(40, 60, 80)

// a loop
do
    sync()
loop

function SortWaterDroplets()
    swapped as integer
    i as integer

repeat
        swapped = 0

for i = 1 to 10

if Array[i - 1].active = 1 and Array[i].active = 1
                    if Array[i - 1].Y < Array[i].Y
                        SwapDroplets(i)
                        swapped = 1
                    elseif Array[i - 1].Y = Array[i].Y
                        if Array[i - 1].X < Array[i].X
                            SwapDroplets(i)
                            swapped = 1
                        endif
                    endif
                elseif Array[i - 1].active = 0 and Array[i].active = 1
                    SwapDroplets(i)
                    swapped = 1
                endif
            `endif
        next

for i =  10 to 1 step - 1

if Array[i - 1].active = 1 and Array[i].active = 1
                    if Array[i - 1].Y < Array[i].Y
                        SwapDroplets(i)
                        swapped = 1
                    elseif Array[i - 1].Y = Array[i].Y
                        if Array[i - 1].X < Array[i].X
                            SwapDroplets(i)
                            swapped = 1
                        endif
                    endif
                elseif Array[i - 1].active = 0 and Array[i].active = 1
                    SwapDroplets(i)
                    swapped = 1
                endif

next
    until swapped = 0

endfunction

function SwapDroplets(i as integer)
    tX as integer
    tY as integer
    tActive as integer
    tID as integer

tX = Array[i - 1].X
    tY = Array[i - 1].Y
    tActive = Array[i - 1].active
    tID = Array[i - 1].id

Array[i - 1].X = Array[i].X
    Array[i - 1].Y = Array[i].Y
    Array[i - 1].active = Array[i].active
    Array[i - 1].id = Array[i].id

Array[i].X = tX
    Array[i].Y = tY
    Array[i].active = tActive
    Array[i].id = tID
endfunction

+ Code Snippet

// our UDT
type TYPE_WATER_DROPLET
    X as integer //---- third sorted field, descending
    Y as integer //---- second sorted field, descending
    active as integer //---- first sorted field, descending
    id as integer //---- not sorted on
endtype

// Create an array
SizeOfArray = 10
Dim Array[SizeOfArray] as Type_Water_Droplet

    Array[0].X = 23
    Array[0].Y = 55
    Array[0].active = 0

    Array[1].X = 421
    Array[1].Y = 86
    Array[1].active = 1

    Array[2].X = 999
    Array[2].Y = 445
    Array[2].active = 1

    Array[3].X = 742
    Array[3].Y = 548
    Array[3].active = 1

    Array[4].X = 44
    Array[4].Y = 123
    Array[4].active = 1

    Array[5].X = 764
    Array[5].Y = 3
    Array[5].active = 0

    Array[6].X = 1999
    Array[6].Y = 300
    Array[6].active = 1

    Array[7].X = 559
    Array[7].Y = 410
    Array[7].active = 0

    Array[8].X = 111
    Array[8].Y = 300  `865
    Array[8].active = 1

    Array[9].X = 123
    Array[9].Y = 201
    Array[9].active = 0

    Array[10].X = 54
    Array[10].Y = 45
    Array[10].active = 1
// Sort each element
// Using the insertion sort
CurrentValue as integer
CurrentIndex as integer = 1

SortIndex as integer

BeginTime# = timer()

SortWaterDroplets()

Endtime# = timer()

ElapsedTime# = EndTime# - BeginTime#
// create a bunch of text objects to display our results
For n = 0 to SizeOfArray
    //For the x's
    CreateText(n, str(Array[n].X))
    SetTextPosition(n, 0, n*8)

    // For the y's
    CreateText(n+11, str(Array[n].Y))
    SetTextPosition(n+11, 20, n*8)

    // The actives
    CreateText(n+22, str(Array[n].Active))
    SetTextPosition(n+22, 40, n*8)

Next n

// Create a text object for the elapsed time
CreateText(40, str(ElapsedTime#) + " sec")
SetTextPosition(40, 60, 80)

// a loop
do
    sync()
loop

function SortWaterDroplets()
    swapped as integer
    i as integer

    repeat
        swapped = 0

        for i = 1 to 10

              if Array[i - 1].active = 1 and Array[i].active = 1
                    if Array[i - 1].Y < Array[i].Y
                        SwapDroplets(i)
                        swapped = 1
                    elseif Array[i - 1].Y = Array[i].Y
                        if Array[i - 1].X < Array[i].X
                            SwapDroplets(i)
                            swapped = 1
                        endif
                    endif
                elseif Array[i - 1].active = 0 and Array[i].active = 1
                    SwapDroplets(i)
                    swapped = 1
                endif
            `endif
        next

        for i =  10 to 1 step - 1

                if Array[i - 1].active = 1 and Array[i].active = 1
                    if Array[i - 1].Y < Array[i].Y
                        SwapDroplets(i)
                        swapped = 1
                    elseif Array[i - 1].Y = Array[i].Y
                        if Array[i - 1].X < Array[i].X
                            SwapDroplets(i)
                            swapped = 1
                        endif
                    endif
                elseif Array[i - 1].active = 0 and Array[i].active = 1
                    SwapDroplets(i)
                    swapped = 1
                endif

        next
    until swapped = 0

endfunction

function SwapDroplets(i as integer)
    tX as integer
    tY as integer
    tActive as integer
    tID as integer

    tX = Array[i - 1].X
    tY = Array[i - 1].Y
    tActive = Array[i - 1].active
    tID = Array[i - 1].id

    Array[i - 1].X = Array[i].X
    Array[i - 1].Y = Array[i].Y
    Array[i - 1].active = Array[i].active
    Array[i - 1].id = Array[i].id

    Array[i].X = tX
    Array[i].Y = tY
    Array[i].active = tActive
    Array[i].id = tID
endfunction

Hi there. My name is Dug. I have just met you, and I love you.

Back to top

Profile PM Email Website

Hodgey

15

Years of Service

User Offline

Joined: 10th Oct 2009

Location: Australia

Posted: 15th Jan 2012 00:00 Edited at: 15th Jan 2012 00:08

Link

Quote: "Thank you for the contribution! However, I think there is a bug with your code. "

Quote: "The UDT's values are supposed to be kept grouped together. Instead, this insertion sort sorts out the fields independently of each other."

Actually, that's not a bug. It's me misinterpreting your intentions.

Ok answerman, this had better work because it took me ages to write and debug this (a single typo was causing the whole thing to crash!!!).

// our UDT
type TYPE_WATER_DROPLET
    X as integer //---- third sorted field, descending
    Y as integer //---- second sorted field, descending
    active as integer //---- first sorted field, descending
    id as integer //---- not sorted on
endtype

// NEW TYPE
type INSERTION_SORT_ARRAY
    Value as integer
    A_Type as integer
endtype

// Create an array
SizeOfArray = 10
Dim Array[SizeOfArray] as Type_Water_Droplet

// Fill each element of the array with a random number
For n = 0 to SizeOfArray
    Array[n].X = Random(1, 1000)
    Array[n].Y = Random(1, 1000)
    Array[n].active = Random(1, 1000)
Next n

// Start the clock
BeginTime# = timer()

// Create a separate array and fill it
NewArraySize as integer
NewArraySize = 33

Dim SortArray[NewArraySize] as INSERTION_SORT_ARRAY

// Fill this array with values of the original array we want sorted
For n = 0 to SizeOfArray // size of original array
    // X's // Using our A_Type values above
    SortArray[n].Value = Array[n].X
    SortArray[n].A_Type = 1

// Y's // Using our A_Type values above
    SortArray[n+11].Value = Array[n].Y
    SortArray[n+11].A_Type = 2

// Actives // Using our A_Type values above
    SortArray[n+22].Value = Array[n].Active
    SortArray[n+22].A_Type = 3
Next n

// Sort each element
// Using the insertion sort
CurrentValue as integer
CurrentIndex as integer = 1

SortIndex as integer

BeginTime# = timer()

While CurrentIndex <= SizeOfArray
    SortIndex = 0
    // dealing with the already sorted half of the array
    While SortIndex < CurrentIndex

// sort the x's
        If SortArray[CurrentIndex].Value > Array[SortIndex].Value
            // Store the larger value and then shuffle the sorted part down
            TempValue = SortArray[CurrentIndex].Value
            TempType = SortArray[CurrentIndex].A_Type

// shuffle the portion of the sorted part of the array down to make room for the value to be inserted
            SortCount = SortIndex
            EndIndex = CurrentIndex
            While EndIndex > SortCount
                SortArray[EndIndex].X = SortArray[EndIndex-1].X
                SortArray[EndIndex].A_Type = SortArray[EndIndex-1].A_Type
                EndIndex = EndIndex - 1
            Endwhile

// insert the larger value into its correct place
            SortArray[SortIndex].Value = TempValue
            SortArray[SortIndex].A_Type = TempType

Endif

// increase the sort index
        SortIndex = SortIndex + 1
    Endwhile

// Increase the current index
    CurrentIndex = CurrentIndex + 1
Endwhile

// Copy the sort algorithm back into the original algorithm
// Counts for each element we are sorting
Xcount as integer = 0
Ycount as integer = 0
ActiveCount as integer = 0

For n = 0 to NewArraySize
    If SortArray[n].A_Type = 1
        Array[Xcount].X = SortArray[n].Value

Xcount = Xcount + 1
    Else
        If SortArray[n].A_Type = 2
            Array[Ycount].Y = SortArray[n].Value

Ycount = Ycount + 1
        Else
            If SortArray[n].A_Type = 3
                Array[ActiveCount].Active = SortArray[n].Value
                ActiveCount = ActiveCount + 1
            Endif
        Endif
    Endif
Next n

Endtime# = timer()

ElapsedTime# = EndTime# - BeginTime#
// create a bunch of text objects to display our results
For n = 0 to SizeOfArray
    //For the x's
    CreateText(n, str(Array[n].X))
    SetTextPosition(n, 0, n*8)

// For the y's
    CreateText(n+11, str(Array[n].Y))
    SetTextPosition(n+11, 20, n*8)

// The actives
    CreateText(n+22, str(Array[n].Active))
    SetTextPosition(n+22, 40, n*8)

Next n

// Create a text object for the elapsed time
CreateText(40, str(ElapsedTime#) + " sec")
SetTextPosition(40, 60, 80)

// a loop
do
    sync()
loop

+ Code Snippet

// our UDT
type TYPE_WATER_DROPLET
    X as integer //---- third sorted field, descending
    Y as integer //---- second sorted field, descending
    active as integer //---- first sorted field, descending
    id as integer //---- not sorted on
endtype

// NEW TYPE
type INSERTION_SORT_ARRAY
    Value as integer
    A_Type as integer
endtype

// Create an array
SizeOfArray = 10
Dim Array[SizeOfArray] as Type_Water_Droplet

// Fill each element of the array with a random number
For n = 0 to SizeOfArray
    Array[n].X = Random(1, 1000)
    Array[n].Y = Random(1, 1000)
    Array[n].active = Random(1, 1000)
Next n

// Start the clock
BeginTime# = timer()

// Create a separate array and fill it
NewArraySize as integer
NewArraySize = 33

Dim SortArray[NewArraySize] as INSERTION_SORT_ARRAY

// Fill this array with values of the original array we want sorted
For n = 0 to SizeOfArray // size of original array
    // X's // Using our A_Type values above
    SortArray[n].Value = Array[n].X
    SortArray[n].A_Type = 1

    // Y's // Using our A_Type values above
    SortArray[n+11].Value = Array[n].Y
    SortArray[n+11].A_Type = 2

    // Actives // Using our A_Type values above
    SortArray[n+22].Value = Array[n].Active
    SortArray[n+22].A_Type = 3
Next n



// Sort each element
// Using the insertion sort
CurrentValue as integer
CurrentIndex as integer = 1

SortIndex as integer

BeginTime# = timer()

While CurrentIndex <= SizeOfArray
    SortIndex = 0
    // dealing with the already sorted half of the array
    While SortIndex < CurrentIndex

        // sort the x's
        If SortArray[CurrentIndex].Value > Array[SortIndex].Value
            // Store the larger value and then shuffle the sorted part down
            TempValue = SortArray[CurrentIndex].Value
            TempType = SortArray[CurrentIndex].A_Type


            // shuffle the portion of the sorted part of the array down to make room for the value to be inserted
            SortCount = SortIndex
            EndIndex = CurrentIndex
            While EndIndex > SortCount
                SortArray[EndIndex].X = SortArray[EndIndex-1].X
                SortArray[EndIndex].A_Type = SortArray[EndIndex-1].A_Type
                EndIndex = EndIndex - 1
            Endwhile


            // insert the larger value into its correct place
            SortArray[SortIndex].Value = TempValue
            SortArray[SortIndex].A_Type = TempType

        Endif



        // increase the sort index
        SortIndex = SortIndex + 1
    Endwhile

    // Increase the current index
    CurrentIndex = CurrentIndex + 1
Endwhile

// Copy the sort algorithm back into the original algorithm
// Counts for each element we are sorting
Xcount as integer = 0
Ycount as integer = 0
ActiveCount as integer = 0

For n = 0 to NewArraySize
    If SortArray[n].A_Type = 1
        Array[Xcount].X = SortArray[n].Value

        Xcount = Xcount + 1
    Else
        If SortArray[n].A_Type = 2
            Array[Ycount].Y = SortArray[n].Value

            Ycount = Ycount + 1
        Else
            If SortArray[n].A_Type = 3
                Array[ActiveCount].Active = SortArray[n].Value
                ActiveCount = ActiveCount + 1
            Endif
        Endif
    Endif
Next n




Endtime# = timer()

ElapsedTime# = EndTime# - BeginTime#
// create a bunch of text objects to display our results
For n = 0 to SizeOfArray
    //For the x's
    CreateText(n, str(Array[n].X))
    SetTextPosition(n, 0, n*8)

    // For the y's
    CreateText(n+11, str(Array[n].Y))
    SetTextPosition(n+11, 20, n*8)

    // The actives
    CreateText(n+22, str(Array[n].Active))
    SetTextPosition(n+22, 40, n*8)

Next n

// Create a text object for the elapsed time
CreateText(40, str(ElapsedTime#) + " sec")
SetTextPosition(40, 60, 80)

// a loop
do
    sync()
loop

It's poorly commented because I was pretty frustrated when I decided to retype the whole thing after copy/pasting the bugged code into DBP and solving it from there.

It's hard to see that it has actually sorted the array from the results printed but run it through your tests and let me know the results.

Quote: "The items with an active value of 0 are not sorted because they're ignored by the game during gameplay anyway, and I'd rather not spend time sorting values that won't be used anyway."

I'm sure you can fix that up.

Edit: Forgot to explain what it actually does. What it does is creates a new UDT array, one field for storing the value and the other for storing the element which it came from. For example you have this:

Array[1].X = 10
Array[1].Y = 40
Array[1].Acive = 0

In the new array the above would look like this:
The X
SortArray[1].Value = 10
SortArray[1].A_Type = 1

The Y
SortArray[2].Value = 40
SortArray[2].A_Type = 2

The Active
SortArray[3].Value = 0
SortArray[3].A_Type = 3

Using the A_Type legend:
X = 1
Y = 2
Active = 3.

So all of those values are stored into the new array along with their 'types', are then sorted, and then copied back into the orginal array into their correct fields using the A_Type value.

I hope that makes sense.

Back to top

Profile PM Email

anwserman

13

Years of Service

User Offline

Joined: 20th May 2011

Location: Wisconsin

Posted: 17th Jan 2012 11:44

Link

Hey Hodgey,
I haven't looked at this yet but I'll get to it soon. Thank you once again for your assistance! If I have questions, I'll be sure to ask you!

Hi there. My name is Dug. I have just met you, and I love you.

Back to top

Profile PM Email Website

JimHawkins

15

Years of Service

User Offline

Joined: 26th Jul 2009

Location: Hull - UK

Posted: 17th Jan 2012 11:51

Link

It may be worth pointing out that for short lists or arrays, using QuickSort, ShellSort etc can be substantially slower than an augmented BubbleSort, because the algorithms are more complex.

-- Jim

Back to top

Profile PM Website

Hodgey

15

Years of Service

User Offline

Joined: 10th Oct 2009

Location: Australia

Posted: 20th Jan 2012 11:15

Link

Quote: "I haven't looked at this yet but I'll get to it soon. Thank you once again for your assistance!"

You're welcome mate, always happy to help.

Quote: "It may be worth pointing out that for short lists or arrays, using QuickSort, ShellSort etc can be substantially slower than an augmented BubbleSort, because the algorithms are more complex."

This is why I like insertion sort, it's pretty much an all-rounder but the more values to sort, the slower it may be compared to other algorithms sorting the same values.

http://www.sorting-algorithms.com/
A nice way to compare algorithms.

Back to top

Profile PM Email

anwserman

13

Years of Service

User Offline

Joined: 20th May 2011

Location: Wisconsin

Posted: 23rd Jan 2012 00:40

Link

That's a really cool website hodgey. As my data is mostly sorted, bubble sort actually works quite well on it. Not nearly as fast as insertion sort, but still a cool way to visualize the sorting

Hi there. My name is Dug. I have just met you, and I love you.

Back to top

Profile PM Email Website

Sorry your browser is not supported!

AppGameKit Classic Chat / Better Sorting Method Than Cocktail Sort