Bubble sorting is the simplest sorting algorithm out there. The technique involves making multiple passes over the input array and swapping unordered elements close to one another. The technique is called bubble sort, as the sorted list "bubbles" up from the tail end of the list.

All sorting algorithms accept a list of elements and return them ordered. The main difference between each algorithm is the manner in which the sorting is done. Bubble sorting works by swapping adjacent elements. This pushes the sorted elements toward the end of the list.

Snippet 2.1 shows the pseudocode for bubble sort. The algorithm involves three simple tasks, which...

Quick sort is a big improvement over bubble sort. This sorting technique was developed by British computer scientist Tony Hoare. The algorithm works in three main steps:

1. Select a pivot
2. Partition the list so that elements on the left of the pivot are less than the value of the pivot and the ones on the right are greater
3. Repeat steps 1 and 2 on the left and right parts separately

Since recursion is required for quick sort, we will begin this section by giving an example of recursion. Later, we will see how the partitioning in the quick sort algorithm works, and in the end, we will put the recursion techniques to use in the final part.

Recursion...

Although the quicksort on average is pretty fast, it still has the theoretical worst time complexity of O(n²). In this section, we shall examine another sorting algorithm, called merge sort, in which the worst time complexity is O(n log n). Similar to quick sort, merge sort belongs to the divide and conquer class of algorithms.

Merge sort can be summarized in three simple steps as follows: 

1. Split the array in the middle
2. Recursively sort each part separately
3. Merge the two sorted parts together

In the following section, we will develop the preceding steps gradually, at each turn slowly building our understanding of how merge sorting works.

Data structures are a way to organize data so that it is efficiently accessible for the problem you are trying to solve. Choosing the right data structure will depend on the type of problem you're trying to solve (dictating the manner you access your data), the amount of data you need to organize, and the medium you use to store your data (memory, disk, and so on).

We have already seen and used one example of a data structure. In the preceding sections, we have made extensive use of arrays. Arrays are the most primitive of data structures. They provide access to your data using an index and are fixed in size (also called static). This is opposed to other dynamic data structures that can grow and make more space for data whenever it's needed.

In this chapter, we laid the foundations for the more complex upcoming sections. In the first few sections, we saw how a simple problem such as sorting can have many solutions, all with different performance properties. We explored three main implementations, which were bubble, quick, and merge sort.

In later sections, we introduced data structures and studied various implementations and use cases of linked lists, queues, and stacks. We also saw how some data structures can be used as building blocks to build more complex ones on top. In the next chapter, we will study hash tables and binary trees, two important and widely used data structures.