# _BubbleSort()

8 replies to this topic

### #1 buzz44

buzz44

Seriously funny.

• Active Members
• 1,388 posts

Posted 06 June 2005 - 06:27 AM

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.

Plain Text
```;===============================================================================
;
; 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 by buzz44, 13 May 2010 - 12:41 PM.

### #2 ezzetabi

ezzetabi

さくらが　さいた

• Active Members
• 2,011 posts

Posted 06 June 2005 - 08:42 AM

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?

### #3 jdickens

jdickens

Prodigy

• Active Members
• 150 posts

Posted 06 June 2005 - 01:32 PM

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.
Plain Text
```;^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
If I am too verbose, just say so. You don't need to run on and on.

### #4 buzz44

buzz44

Seriously funny.

• Active Members
• 1,388 posts

Posted 06 June 2005 - 02:10 PM

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 by buzz44, 29 December 2011 - 04:14 AM.

### #5 jdickens

jdickens

Prodigy

• Active Members
• 150 posts

Posted 06 June 2005 - 02:52 PM

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
If I am too verbose, just say so. You don't need to run on and on.

### #6 buzz44

buzz44

Seriously funny.

• Active Members
• 1,388 posts

Posted 06 June 2005 - 11:58 PM

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 by buzz44, 29 December 2011 - 04:14 AM.

### #7 blindwig

blindwig

Universalist

• Active Members
• 772 posts

Posted 07 June 2005 - 03:09 AM

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.

### #8 Nutster

Nutster

Developer at Large

• Developers
• 1,450 posts

Posted 07 June 2005 - 02:59 PM

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 by Nutster, 07 June 2005 - 03:02 PM.

David NuttallNuttall Computer ConsultingAutoIt allows me to re-invent the wheel so much faster.An Aquarius born during the Age of AquariusI'm off to write a wizard, a wonderful wizard of odd...

### #9 jdickens

jdickens

Prodigy

• Active Members
• 150 posts

Posted 08 June 2005 - 12:27 PM

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 by jdickens, 08 June 2005 - 12:30 PM.

If I am too verbose, just say so. You don't need to run on and on.

#### 0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users