A couple of days ago, while recovering from some flu, I managed to catch up a bit of me reading. If you know anything about the life of an independent contractor, you’d know that there’s never time for your personal projects or hobbies, so this was a most welcome break.
One of my favorite blogs is this one and I saw a great article on Sorting vectors in C++ by Nic Raboy. As it happens, C++ is one of my first commercial languages and I still make some moderate use of it for various mobile projects.
One thing that struck me, as I read the code, was how close this was to the Dart programming language. I’ve been doing a lot of Flutter development of late, and have been making more use of the Dart programming language. Mobile applications often contain complex logic, and this is where Dart has really proven it’s worth to me, in both being a concise and expressive language, but also being familiar enough that I didn’t have to learn everything from scratch to be productive.
In this short tutorial, we’ll take the quicksort algorithm Nic has built in C++ and convert it to Dart. Along the way, we’ll see how close Dart is to C++ and how much of your existing C++ knowledge easily transfers to the Dart environment.Read More
If you’re studying computer science, at some point you’re going to be exposed to the Quicksort algorithm. Even if you’re not a computer science student, chances are this particular algorithm will come up at some point in time as part of an interview. I’ve been asked about it plenty of times in interview processes and never once used it again.
Whether or not you’ll ever use the Quicksort algorithm, it is important to know and that is what we’re going to review in this back to the basics tutorial.
In this tutorial we’re going to sort a vector of integer values using the Quicksort algorithm. We’re going to use a vector because it is a commonly used data structure in C++.Read More
Previously you saw an implementation of Quicksort, one of the better sorting algorithms. This time we’re going to look at a much inferior sorting algorithm which generally makes its appearance in introduction to computer science type courses. I’m talking about the Bubble Sort algorithm.
Bubble Sort via Wikipedia:
Bubble sort, sometimes referred to as sinking sort, is a simple sorting algorithm that repeatedly steps through the list to be sorted, compares each pair of adjacent items and swaps them if they are in the wrong order.
The Bubble Sort algorithm is sub-par because of the outrageous time-complexity that it has for all sorting calls and we’re going to see why.Read More
Circling back to data structures and algorithms, we’re now going to take a look at the efficient sorting algorithm known as Quicksort.
Quicksort via Wikipedia:
Sometimes called partition-exchange sort, is an efficient sorting algorithm, serving as a systematic method for placing the elements of an array in order.
The idea behind Quicksort is to take a large array of values and divide it into two smaller arrays, doing this recursively, and swapping elements.
This is one of the fundamental algorithms you’ll learn in any computer science course. It is also a very good question that could be asked in a job interview for an engineering type position. I’m going to help you through it using Java.Read More
If you’ve been keeping up with my blog, I’ve made a topic regarding Binary Search Trees, but another very important topic in computer science and software engineering is in regards to Graphs.
Graphs via Wikipedia:
A graph data structure consists of a finite (and possibly mutable) set of nodes or vertices, together with a set of ordered pairs of these nodes (or, in some cases, a set of unordered pairs). These pairs are known as edges or arcs.
When interviewing for a new programming or software engineering position, it is incredibly likely that you are asked a question on this topic. Because of this, I figured it would be a good idea to go over a few of the Graph search algorithms.Read More
Reverse Polish Notation via Wikipedia:
A mathematical notation in which every operator follows all of its operands, in contrast to Polish notation, which puts the operator in the prefix position. It is also known as postfix notation and is parenthesis-free as long as operator arities are fixed.
In this phase two article, we’re going to look at how to solve a mathematical expression that has been parsed into Reverse Polish Notation (RPN).Read More
Anyone who knows how to program can probably solve a mathematical equation such as
5 + 3 * 6 - ( 5 / 3 ) + 7, but how might you get a computer to understand the appropriate order of operations? The equation I listed is in a format known as Infix Notation.
Infix Notation via Wikipedia:
Infix notation is the notation commonly used in arithmetical and logical formulae and statements. It is characterized by the placement of operators between operands.
This format is not the most ideal to work with when attempting to solve.
Instead it is more appropriate to use format such as
5 3 6 * + 5 3 / - 7 + which is more commonly known as Postfix Notation or Reverse Polish Notation (RPN). This conversion can be accomplished by what is known as the Shunting Yard algorithm.