Before writing an algorithm, it’s always worth thinking about how you would solve the same problem “by hand”.
After all, you can’t write instructions for how to do something if you don’t know how to do it yourself.
The problem we’re currently interested in is sorting — given a list, put its values in order.
There are hundreds of algorithms which solve this problem, but ultimately every sorting algorithm does one of two things:Apr 092018
Before attempting these exercises, you should read the post on linear and binary search.Feb 192018
Before attempting these exercises, you should read the posts about array-lists and linked lists.Feb 192018
When designing a data structure, there are always choices to make.
In the previous post we described the array-list data structure implementing the list data type; in that post, we made the choice to store the list values in an “underlying array” so the list values would all be together in memory.
In this post we’ll show that this really was a choice, by developing a list data structure which stores the list values in separate objects, rather than a single array object.Feb 192018
In earlier posts we described lists and arrays.
We described lists as an abstract data type, meaning we said what a list is and what we should be able to do with one.
However, we didn’t say how a list is implemented — we didn’t describe a data structure for a list — so we don’t yet have a scheme for representing lists in memory.(1)
On the other hand, when we described arrays, we did also describe how to represent them in memory.Feb 122018
A type defines not just the possible values that some data can take, but also the operations which can be performed on that data.
For example, the
int type represents integers, and supports arithmetic operations, bitwise operations and comparison operations.