Table of contents
How to run the example
Sorting algorithms
Bubble Sort
Insertion Sort
Selection Sort
Shell Sort
Quick Sort
Merge Sort
Introduction
This is a subject that probably you did study at University, or if like me, you’re a self made coder, you never see formally but find many times along the way. This themes are many times hidden behind the language itself (Array and Array.sort i.e) and you don’t need to make nothing special to use it, but having the big picture sometimes gives you the extra power to solve a special hard challenge.
ActionScript byt itself is a slower language, as probably many of those not compiled, this is another reason actionscripters sometimes don’t think about this topics. If I’m in a turtle … what’s the difference between walking and running? Well, I agree that ActionScript is slow in comparison with compiled language like C or C++, but lately ActionScript 3 shows an impressive better performance, and the lately features like 3D acceleration trough the use of GDU makes room for new challenges.
With all this in mind, I return to the basics and did a quick walk trough basic themes trying to fill my knowledge blanks. This is by any means an expert conclusion of the topic, but instead my feelings after reading it. Since I’m not a math expert but the opposite, my concern was to not understand anything, but in the end I ask myself: why we have so panic when talking about math … in the end we are coders !!!
Before starting a big thanks
Of course my first panic was to code myself all this structures, but at my first shot, looking around at Michael Baczynksy classes for the use of lists, queues, stacks and trees at polygonal.de, I find a ready to use library at http://www.dpdk.nl/opensource/source-code, well written and documented, so I have just focus on study them and use. This is the reason this little tutorial exists, probably will take months to me to recreate the whole thing in ActionScript breaking the old rule that says “never reinvent the wheel”
So big thanks to Henri Torgemane and his great work
To see the running sample click here
This example was built using Flash Builder, amfphp and a mysql database, so in order to run it you should have some available server. Anyway there’s no need to run your own version, you can download the flex project to just read the source and check the running example here. Anyway if you want to run your own version follow this steps
- Download the source code from here , source include sql to generate the database and the php file to create the service.
- Import the project into Flex.
- You will find a rar file inside the main folder of the project with the SQL to generate the database table, the database is named “structures” but you can use any name as far as you change the PHP accordingly.
- You will find services.php file inside the main folder of the project that need to be copied to amfphp/services … if you dont know what amfphp is, probably you need to read first the Remoting tutorial
- Data structures are heavily based on dpdk opensource package. A copy is included in the lib folder of the project, but you can update with the latest source from http://www.dpdk.nl/opensource/source-code.
My example is just to feature the algorithms, his structure is probably a little messy, with sorting in the main mxml file while data structures manipulation lives each one in his own component.
Sorting Algorithm
Sorting an unordered list is a task easy to understand and many algorithms focus on it, some of them in trivial ways and others in a high sophisticated fashion. There are a lot of paths, but we will mention just the main ones, without entering into derivatives. Prior to enter the algorithms by itself, let’s talk about some of the metrics we use. One of the most important is the big O notation, that in mathematics and computer science is widely used to characterizes functions according to their growth rates: different functions with the same growth rate may be represented using the same O notation. In computer, the
running time or memory usage of an algorithm is often expressed as a function of the length of its input using big O notation. Common classifications in order of complexity are:
O(1) constant
O(log n) logarithmic
O(n) linear
O(n log n) linearithmic
O(n2) quadratic
O(n!) factorial
Usually sorts have a worst case, average case and better case when running, and the average is the one indicated as running time
Other characteristics are stable and adaptive. Stable means if the algorithm maintain the relative order of records with equal keys. A sorting algorithm falls into the adaptive sort family if it takes advantage of existing order in its input.
When we refer to space, this is related to memory space the algorithms requires to run properly.
Bubble Sort
Is a simple sorting algorithm that works by repeatedly stepping through the list to be sorted, comparing each pair of adjacent items and swapping them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted. Since is based on comparisons, it’s a comparison sort. Is it very slow and probably a bad choice for long lists.
Complexity
Stable
O(1) extra space
O(n2) comparisons and swaps
Adaptive: O(n) when nearly sorted
In pseudocode:
for i = 1:n,
swapped = false
for j = n:i+1,
if a[j] < a[j-1],
swap a[j,j-1]
swapped = true
→ invariant: a[1..i] in final position
break if not swapped
end
Insertion Sort
Every repetition of insertion sort removes an element from the input data, inserting it into the correct position in the already-sorted list, until no input elements remain. The choice of which element to remove from the input is arbitrary, and can be made using almost any choice algorithm. Is very similar on we order naturally a deck of cards, leaving on the left a stack of ordered cards, picking one each time from the rest.
Complexity
Stable
O(1) extra space
O(n2) comparisons and swaps
Adaptive: O(n) time when nearly sorted
Very low overhead
In pseudocode:
for i = 2:n,
for (k = i; k > 1 and a[k] < a[k-1]; k--)
swap a[k,k-1]
→ invariant: a[1..i] is sorted
end
Insertion sort is the algorithm of choice either when the data is nearly sorted (because it is adaptive) or when the problem size is small (because it has low overhead). Usually is used in conjunction with other “divide and conquer” algorithms when the parts become small.
Selection Sort
The algorithm works as follows:
1. Find the minimum value in the list
2. Swap it with the value in the first position
3. Repeat the steps above for the remainder of the list (starting at the second position and advancing each time)
Complexity:
Not stable
O(1) extra space
T(n2) comparisons
T(n) swaps
Not adaptive
In pseudocode
for i = 1:n,
k = i
for j = i+1:n, if a[j] < a[k], k = j
→ invariant: a[k] smallest of a[i..n]
swap a[i,k]
→ invariant: a[1..i] in final position
end
It has O(n2) complexity, making it inefficient on large lists, and generally performs worse than the similar insertion sort. However, selection sort has the property of minimizing the number of swaps, using less resources when swapping is expensive
Shell Sort
The principle of Shell sort is to rearrange the file so that looking at every nth element yields a sorted file. We call such a file h-sorted. If the file is then k-sorted for some other integer k, then the file remains h-sorted. For instance, if a list was 5-sorted and then 3-sorted, the list is now not only 3-sorted, but both 5- and 3-sorted. If this were not true, the algorithm would undo work that it had done in previous iterations, and would not achieve such a low running time. The gap used is know as the increment sequence that could be anything that finish with 1, anyway they’re sequences that probably works better than others.
In pseudocode
for i = 1:n,
k = i
for j = i+1:n, if a[j] < a[k], k = j
→ invariant: a[k] smallest of a[i..n]
swap a[i,k]
→ invariant: a[1..i] in final position
end
It’s basically an improvement of insertion sort by allowing the comparison and exchange of elements that are far apart. Because of its low overhead, relatively simple implementation, adaptive properties, and sub-quadratic time complexity, shell sort may be a viable alternative to the O(n·lg(n)) sorting algorithms for some applications when the data to be sorted is not very large.
Quicksort
Quicksort is a divide and conquer algorithm. Quicksort first divides a large list into two smaller sub-lists: the low elements and the high elements. Quicksort can then recursively sort the sub-lists.
The steps are:
1. Pick an element, called a pivot, from the list.
2. Reorder the list so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position. This is called the partition operation.
3. Recursively sort the sub-list of lesser elements and the sub-list of greater elements.
Complexity
Not stable
O(lg(n)) extra space (see discussion)
O(n2) time, but typically O(n·lg(n)) time
Not adaptive
In pseudocode
# choose pivot swap a[1,rand(1,n)] # 2-way partition k = 1 for i = 2:n, if a[i] < a[1], swap a[++k,i] swap a[1,k] → invariant: a[1..k-1] < a[k]
When carefully implemented, quick sort is robust and has low overhead. When a stable sort is not needed, quick sort is an excellent general-purpose sort — although the 3-way partitioning version should always be used instead. (conversely QuickSort3)
Merge Sort
Conceptually, a merge sort works as follows
If the list is of length 0 or 1, then it is already sorted. Otherwise:
Divide the unsorted list into two sub-lists of about half the size.
Sort each sub-list recursively by re-applying the merge sort.
Merge the two sub-lists back into one sorted list.
Merge sort incorporates two main ideas to improve its runtime: a small list will take fewer steps to sort than a large list, and fewer steps are required to construct a sorted list from two sorted lists than two unsorted lists. For example, you only have to traverse each list once if they’re already sorted.
Complexity
Stable
Θ(n) extra space for arrays (as shown)
Θ(lg(n)) extra space for linked lists
Θ(n·lg(n)) time
Not adaptive
Does not require random access to data
In pseudocode
# split in half m = n / 2 # recursive sorts sort a[1..m] sort a[m+1..n] # merge sorted sub-arrays using temp array b = copy of a[1..m] i = 1, j = m+1, k = 1 while i
Merge sort is the algorithm of choice for a variety of situations: when stability is required, when sorting linked lists, and when random access is much more expensive than sequential access (for example, external sorting on tape).

















