buzz44 Posted June 6, 2005 Share Posted June 6, 2005 (edited) 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 qq Link to comment Share on other sites More sharing options...
ezzetabi Posted June 6, 2005 Share Posted June 6, 2005 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? Link to comment Share on other sites More sharing options...
jdickens Posted June 6, 2005 Share Posted June 6, 2005 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 If I am too verbose, just say so. You don't need to run on and on. Link to comment Share on other sites More sharing options...
buzz44 Posted June 6, 2005 Author Share Posted June 6, 2005 (edited) 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 qq Link to comment Share on other sites More sharing options...
jdickens Posted June 6, 2005 Share Posted June 6, 2005 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. Link to comment Share on other sites More sharing options...
buzz44 Posted June 6, 2005 Author Share Posted June 6, 2005 (edited) 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 qq Link to comment Share on other sites More sharing options...
blindwig Posted June 7, 2005 Share Posted June 7, 2005 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=12136I 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. My UDF Threads:Pseudo-Hash: Binary Trees, Flat TablesFiles: Filter by Attribute, Tree List, Recursive Find, Recursive Folders Size, exported to XMLArrays: Nested, Pull Common Elements, Display 2dSystem: Expand Environment Strings, List Drives, List USB DrivesMisc: Multi-Layer Progress Bars, Binary FlagsStrings: Find Char(s) in String, Find String in SetOther UDF Threads I Participated:Base64 Conversions Link to comment Share on other sites More sharing options...
Nutster Posted June 7, 2005 Share Posted June 7, 2005 (edited) 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 David NuttallNuttall Computer Consulting An Aquarius born during the Age of Aquarius AutoIt allows me to re-invent the wheel so much faster. I'm off to write a wizard, a wonderful wizard of odd... Link to comment Share on other sites More sharing options...
jdickens Posted June 8, 2005 Share Posted June 8, 2005 (edited) 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 If I am too verbose, just say so. You don't need to run on and on. Link to comment Share on other sites More sharing options...
Recommended Posts
Create an account or sign in to comment
You need to be a member in order to leave a comment
Create an account
Sign up for a new account in our community. It's easy!
Register a new accountSign in
Already have an account? Sign in here.
Sign In Now