_BubbleSort()

[buzz44]

Learnt about this in school today and thought I would implement it in AutoIt instead of Psuedocode.

Bubble Sort Algorithm:

Is a simple sorting algorithm. It works by repeatedly stepping through the array to be sorted, comparing two items at a time, swapping these two items if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which means the array is sorted.

Bubble sort is asymptotically equivalent in running time to insertion sort, but the two algorithms differ greatly in the number of swaps necessary.

expandcollapse popup

;===============================================================================
;
; Function Name:    _BubbleSort()
; Description:      Sort a 1 dimensional Array of numbers on a specific index
;                   using the bubblesort algorithm.
; Parameter(s):     $avArray      - Array
;                   $iReverse - Sort ascending when 0 / Sort descending when 1
;                   $iStart   - Start sorting at this Array entry.
;                   $iEnd     - End sorting at this Array entry. Default UBound($avArray) - 1
;
; Requirement(s):   None
; Return Value(s):  On Success - 1 and the sorted array is set
;                   On Failure - 0 and sets @ERROR = 1 when $avArray is not an array
;===============================================================================

#include <Array.au3>

Dim $Array[10]

$Array[0] = 500
$Array[1] = 19
$Array[2] = 2
$Array[3] = 7
$Array[4] = 1
$Array[5] = 21
$Array[6] = 17
$Array[7] = 23
$Array[8] = 46
$Array[9] = 3

_ArrayDisplay($Array,"UnSorted" )
_BubbleSort($Array)
_ArrayDisplay($Array,"Sort Ascending" )
_BubbleSort($Array,1)
_ArrayDisplay($Array,"Sort Decending" )

Func _BubbleSort($avArray, $iReverse = 0, $iStart = 0, $iEnd = 0)
   If Not IsArray($avArray) Then
      SetError(1) ; Isn't an array.
      Return 0
   EndIf
   If $iEnd < 1 Or $iEnd > UBound($avArray) - 1 Then $iEnd = UBound($avArray) - 1
   If $iStart < 0 Or $iStart > UBound($avArray) - 1 Then $iStart = 0
   If $iReverse <> 1 Then $iReverse = 0
   While $iEnd > $iStart
      For $I = $iStart To $iEnd - 1
         If $iReverse = 1 Then
            If $avArray[$I] < $avArray[$I + 1] Then _ArraySwap($avArray[$I], $avArray[$I + 1])
         ElseIf $iReverse = 0 Then
            If $avArray[$I] > $avArray[$I + 1] Then _ArraySwap($avArray[$I], $avArray[$I + 1])
         EndIf
      Next
      $iEnd = $iEnd - 1
   Wend
   Return 1
EndFunc

Edited May 13, 2010 by buzz44

[ezzetabi]

Just for personal knowledge, why should we use bubble sort since Autoit have no data structures without random access iterators and bubble sort is quite slow?

[jdickens]

I thought I had a purpose for it... that's why I racked my brain this weekend trying to remember college days!

What kind of sort is mine? Sorry, it is for a specific use, where the key is stored in the [x] [0] dimension and the contents are in [x] [1]. [0] [0] is used as temp storage.

This sort is pretty good for an array that is already somewhat sorted, such as mine was.

;^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v

Func SortCardsRA($StartIndex = 1)
    $Temp = 0
    $IsSorted = $FALSE
    While Not $IsSorted
        For $CurIndex = $StartIndex To UBound($CardsRA) - 1 - 1
            If $CardsRA[$CurIndex] [0] > $CardsRA[$CurIndex + 1] [0] Then
            ;Out of Sort -- Swap two items and reset $CurIndex
                $IsSorted = $FALSE
            ;MsgBox(0, "Original List is Out-of-Sort", $CardsRA[$CurIndex] [0] & _
            ;       ", at Index " & String($CurIndex) & " was found before " & $CardsRA[$CurIndex + 1] [0] & ".  Sorting...  ", 1))
                $OOSort = $CurIndex + 1
                $CardsRA[$Temp] [0] = $CardsRA[$OOSort] [0]
                $CardsRA[$Temp] [1] = $CardsRA[$OOSort] [1]
                $CardsRA[$OOSort] [0] = $CardsRA[$CurIndex] [0]
                $CardsRA[$OOSort] [1] = $CardsRA[$CurIndex] [1]
                $CardsRA[$CurIndex] [0] = $CardsRA[$Temp] [0]
                $CardsRA[$CurIndex] [1] = $CardsRA[$Temp] [1]
                $CardsRA[$Temp] [0] = ""
                $CardsRA[$Temp] [1] = ""
                
                $StartIndex = $CurIndex - 2 ;Go back one extra in case two were out of sort in a row
                If $StartIndex < 1 Then
                    $StartIndex = 1
                EndIf               
                ExitLoop
            Else
                $IsSorted = $TRUE
            EndIf
        Next
    WEnd
    Return $IsSorted
EndFunc  ;==>SortCardsRA
;^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v

J

[buzz44]

Just for personal knowledge, why should we use bubble sort since Autoit have no data structures without random access iterators and bubble sort is quite slow?

As I said I learnt about this today I thought I might put it to practical use. I didn't do it so that I could use it, I done it so I knew I could do it, and for learning purposes. I added this to 'Scrips and Scraps' in the hope that others who are at the same learning stage as me might want to take some insight from it as bubble sort is one of the simplist, if not the simplist, sorting algorithms and a great place to start for learning.

why should we use...

I am not forcing you to use this, that is your own personal opinion and decision.

I thought I had a purpose for it... that's why I racked my brain this weekend trying to remember college days!

What kind of sort is mine? Sorry, it is for a specific use, where the key is stored in the [x] [0] dimension and the contents are in [x] [1]. [0] [0] is used as temp storage.

This sort is pretty good for an array that is already somewhat sorted, such as mine was.

Its sort of like a Bubble Sort I think... Except instead of doing multiple Pass's you only do one, but you are still comparing if the item is greater then the next. Edited December 29, 2011 by buzz44

[jdickens]

Nice work, Burrup. I believe one thing that makes AutoIt awesome is the forums. Try finding one equivalent forum for other languages.

One idea: I tried to copy your code and paste it into Scite, but it loses all semblance of formatting. Am I missing something basic, or do you need to dl an au3 file to make that come out nice?

J

[buzz44]

Its most probably because I write all my scripts in notepad, I do all tab's/indentations myself etc, and only use Scite when I need to replace functions or tidy etc. It often happens to me , you can correct by using 'Tidy' in Scite or right clickin on the .au3 file.

Edit: Just realised the real problem, its because I used a [*CODEBOX] instead of [*CODE]. Difference between a code and codebox is that the code box's height is limited and uses vertical and horizontal scroll bars to save space, a plain code bracket doesn't do this. You can still fix it usung Scite but .

Edited December 29, 2011 by buzz44

[blindwig]

I thought I had a purpose for it... that's why I racked my brain this weekend trying to remember college days!

What kind of sort is mine?  Sorry, it is for a specific use, where the key is stored in the [x] [0] dimension and the contents are in [x] [1].  [0] [0] is used as temp storage.

This sort is pretty good for an array that is already somewhat sorted, such as mine was.

<{POST_SNAPBACK}>

I'm working on a library for dealing with those types of structures. See my thread:

http://www.autoitscript.com/forum/index.php?showtopic=12136

I haven't done a sorting routine yet (haven't needed one in my programs)

I wrote my functions with [x][2] arrays in mind, but was careful not to disallow [x][y] arrays from working properly.

[Nutster]

I thought I had a purpose for it... that's why I racked my brain this weekend trying to remember college days!

What kind of sort is mine?  Sorry, it is for a specific use, where the key is stored in the [x] [0] dimension and the contents are in [x] [1].  [0] [0] is used as temp storage.

This sort is pretty good for an array that is already somewhat sorted, such as mine was.

<Code Removed>

J

<{POST_SNAPBACK}>

This looks like a poor implementation of bubble sort for a two-dimensional keyed array. I saw poor because if your first two elements are in order, but everything else is a mess, then it will stop after the first pass because you set $IsSorted to true on the first set of in-order elements. The more appropriate thing to do is to assume that the array is sorted unless you have to do a swap. Get rid of the $IsSorted = $TRUE and put $IsSorted = $False at the end of the swapping section.

Edit: I guess I could have read your intent and not just your code. Of course it is for a keyed two-dimensional array.

Edited June 7, 2005 by Nutster

[jdickens]

I see what you are saying Nutster, but note that execution won't get out of the For Next loop if the two first elements are sorted. So, though the assignment of true to $IsSorted is illogical, it won't give back an unsorted array. The $IsSorted var should be called $IsSortedSoFar.

There is a bug, however, because I had intended (for my own nefarious reasons) to be able to sort only above a certain index, thus passing the $StartIndex parameter to the fn call; but this can fail at the place where I reassign $StartIndex to 1 or to $StartIndex - 2. It should be reassigned to the value made during the fn call AT A MINIMUM.

J

Edited June 8, 2005 by jdickens