Welcome to the algorithms section of this course. The next few lessons are sure to be interesting as we are going to talk about some advanced topics in computer science. These algorithms will help walk you how programming works and will help give you the tools you'll need to building your own advanced programs.

We're going to start out by discussing sorting algorithms. The reason why we're starting with sorting is because it supplies some of the foundational knowledge that you'll be able to use in more advanced topics, as you'll see as you work through the section.

To explore sorting let's start by creating an array:

a = [1, 5, 1, 2, 10, 100, 3, 1]

If you want to sort these values in ascending order, all that you have to do is run:

a.sort

and the output is [1, 1, 2, 3, 5, 10, 100].

Since this sort method works great there's no real need to create your own sort method in Ruby. This brings up the next question of why is it important to learn about sorting algorithms when most languages already have sorting mechanisms in place?

There are a number of reasons why it's important to learn sorting algorithms, but the most critical is that by creating a sorting algorithm it will help you to better learn the intricacies of programming. Sorting algorithms will force you to combine all of the key programming techniques that you've learned through this course, including topics like:

• Working with collections
• Integrating conditionals
• Swapping values inside collections
• Various forms of looping

Now, let's look at the sorting algorithms that we are going to cover in this section.

In the subsequent guides we are going to cover bubble sort, quick sort and merge sort.

Bubble Sort

Bubble sort is an algorithm that we'll learn simply for practice because it's too simple and basic for any real-world use (and incredibly slow). At its core, bubble sort starts from the left-most value, and keeps moving to the right. When moving from left to right, if the next value being compared is greater than the previous one, then it's replaced by the higher value and the sorting continues. In other words, it's taking the largest element and bubbling it to the top, and this is why it's called bubble sort. Bubble sort requires many iterations to sort through a typical list since it analyzes one value at a time and finds its right position in the list. In an array of 97 elements, bubble sort would iterate 97 times before it sorted all the values in their right positions.

Quick sort

Quick sort, on the other hand, is a much faster sorting algorithm compared with bubble sort because it uses the concept of divide and conquer. This algorithm picks a pivot point, and divides the entire list into two groups - one that's below the pivot point and one that's greater than the pivot. And it continues to break the collection into smaller and smaller chunks.

This is an efficient algorithm because it sorts values very fast and breaks the entire value set into more manageable pieces. Due to these reasons, quick sort is one of the most widely used sorting algorithm out there, and most people like to use in their code. Also, the Ruby sort method that we used earlier uses the quick sort algorithm to rearrange values.

Merge Sort

The last type of sorting algorithm that we'll cover is merge sort, and this is similar to quick sort, as it uses the divide and conquer method. However, merge sort divides the entire collection into subsections, sorts each subsection and merges it with the next subsection to create a larger group of sorted values.

This type of sorting typically works as well as the quick sort algorithms, however quick sort is considered as the de-facto standard for sorting in most computer science circles.

Summary

We'll see how to implement all the three types of sorting algorithms in the subsequent lessons. Understanding this sorting method can be quite handy when you're learning a new concept, appearing for an exam or going through a coding interview.