.png)
Sorting
Sorting
What is sorting?
Sorting means to arrange, in the real world, suppose we have different colored marbles with us and we wish to sort them out based on their colors so what are we going to do?
We will simply by hand pick up each marble and add it to the respective pile. Now, what if we want to arrange our data in some manner to form a relation?
We can do the same using sorting.
In programming, Sorting refers to arranging data in increasing or decreasing order to form a logical relationship between the data.
There are a number of ways to perform sorting but here we will have a look at 2 ways namely
Bubble Sort
Quick Sort
Bubble Sort
Introduction
It is a sorting algorithm that is used to sort the arrays by comparing the elements and swap them if they are not in the desired order.
The order of the elements can be increasing or decreasing as per our choice.
To understand bubble sort in more detail let us look at an example
In the example above we are given an array that is in random order and we want to arrange them in ascending order then we can do that by using bubble sort.
Iteration 1
In bubble sort, we start with the element at the 0th position i.e 6. So, 6 is compared with 4 and 6>4, so the position of 4 and 6 are swapped.
Then 6 is compared with 1 and 6 > 1, so the position of 1 and 6 are swapped.
After that 6 is compared with 2 and again 6 > 2, so the position of 6 and 2 are swapped. Now, 6 is compared with 5 and 6 > 5 so the positions are swapped again. With this, we complete the First iteration, but still, our array is not sorted so we continue further.
Iteration 2
In the second iteration, the 0th element i.e 4 is compared with the 1st element i.e 1 and 4>1 so they are swapped. Now 4 is compared with 2 and 4>2, so they are swapped. Now 4 is compared with 5 but 4 <5 therefore, the elements are not swapped.
The same process is repeated in the third and fourth iteration and finally, we have an array that is sorted.
After going through the example above, we now have a clear understanding of bubble sort. Let us look at some code to understand in even more details
In the example above we started by creating loops. We start the loop from 0 and put the check constraint on the size of length i.e the upper bound of the loop should be the size of the array.
We are nesting the loops so that there can be multiple iterations and the array can be sorted because for each value of i the entire loop of j is executed and one iteration is completed.
Inside the nested, for loops, we have an if condition which checks that if the current element is greater than the next element. If it is greater than the elements are swapped and if they are not then no action is performed.
Now if we look at the console we will see the following output
Here is the link for the code sandbox where you can try playing with code and learn about bubble sort in more detail
stupefied-lewin-nf9g1 - CodeSandbox
Quick Sort
Bubble sort is a great way to sort but takes a lot of time to iterate over the elements and to find their correct place. So, we have some other sorting algorithms with us that are much more efficient in performing the operation.
One of these is quicksort.
In this section, we will just grab an overview of quick sort because going into details might be quite overwhelming.
Quicksort works on the algorithm of divide and conquer. We divide the given elements into smaller parts based on some conditions and then we perform the sorting operations on the divided parts.
By using this method we can divide a large group of elements into relatively smaller parts. Following are the steps that we perform in quicksort.
An element is selected which is called a pivot.
All the elements are compared with the selected pivot and are arranges in such a way that elements less than the pivot are to its left and elements greater than the pivot are to its right.
The same operation is repeated to both the sides of the pivot
The above-explained steps are just a brief to quicksort and we will look into more details in build a dev nano degree course