An Introduction to Computer Science with AutoIt pt2

This page is still a work in progress.

Introduction to Sorting

In this tutorial we will cover a well known problem in data manipulation and programming: sorting. It is often critical for displaying the data to users (or for printing), but also it holds critical importance in a number of other algorithms we will cover. In particular, the binary search algorithm requires data to be sorted.

Sorting is a common problem that you will have to solve many times as a programmer. Fortunately, there are several well known techniques that you can use to sort your data, with varying time and memory complexities. You should pick an algorithm for your specific needs that balances ease-of-implementation with time complexity.

Data representation

Hold on a second, before we start sorting data we first need to decide on a universal way of storing sorted and unsorted data. The most common way is to store data in a 1+ dimension array, like this:

Dim $data[4]
$data[0] = 3 ;3 data entries
$data[1] = "cats"
$data[2] = "axcelottle"
$data[3] = "dogs"

Algorithms

Because we have a uniform way of passing around sorted and unsorted data, all these algorithms are now completely interchangeable. One can simply paste them into a script and change the name of their function call, and it will work out of the box.

Bubble Sort

Bubble sort is a very simple, stock-standard sorting algorithm that works by repeatedly swapping adjacent elements that are out of order; a process that is eventually garranteed to sort them. This algorithm is extremely simple to implement. The downside: O(n²) time complexity, but for most applications this doesnt matter.

Bubble Sort Algorithm

Conclusion

Sorting is one of those really basic tasks that everyone must tackle every once in a while. Hopefully, by now, you are getting used to the considerations of complexity (efficiency) and the idea of algorithms.

In the next part of the series we will look at datastructures. This field is concerned with the best way to store data so it can be stored, found (searched), inserted, and deleted with the minimum of time AND memory complexity. An Introduction to Computer Science with AutoIt pt3