An intro to Algorithms: Searching and Sorting algorithms
One of the seemingly most-overused words in tech is “algorithm”. From the apps on your phone to the sensors in your wearables and how posts appear in your Facebook News Feed, you’ll be pushed to find a service that isn’t powered by some form of algorithm. I am too fascinated how algorithms made an impact in our day-to-day lives
An algorithm is a finite sequence of precise instructions for performing a computation or for solving a problem.
For example, here is an algorithm for singing that annoying song “99 Bottles of Beer on the Wall”, for arbitrary values of 99:
As Donald Knuth wrote in The Art of Computer Programming– which could be described as the encyclopedia of algorithms and data structures– it’s a confusing word that looks like someone mashed up logarithm and arithmetic.
Properties of Algorithms
- Input -An algorithm has input values from a specified set.
- Output -From each set of input values an algorithm produces output values from a specified set. The output values are the solution to the problem.
- Definiteness -The steps of an algorithm must be defined precisely.
- Correctness -An algorithm should produce the correct output values for each set of input values.
- Finiteness -An algorithm should produce the desired output after a finite (but perhaps large) number of steps for any input in the set.
- Effectiveness -It must be possible to perform each step of an algorithm exactly and in a finite amount of time.
- Generality -The procedure should be applicable for all problems of the desired form, not just for a particular set of input values
Now before heading up to main topic, I want to share the basics of analysis of the algorithms including time complexity and space complexity.
Time Complexity and Space Complexity in algorithms
Always a question arises -
When does an algorithm provide a satisfactory solution to a problem?
- One measure of efficiency is the time used by a computer to solve a problem using the algorithm, when input values are of a specified size
- second measure is the amount of computer memory required to implement the algorithm when input values are of a specified size
Questions such as these involve the computational complexity of the algorithm. An analysis of the time required to solve a problem of a particular size involves the time complexity of the algorithm. An analysis of the computer memory required involves the space complexity of the algorithm.
There are three types of time complexity — Best, average and worst case.
In simple words for an algorithm, if we could perform and get what we want in just one(eg. on first instance) computational approach, then that is said as O(1) i.e. Time complexity here falls into “Best case” category.
Say for example, same algorithm results into many iterations/recursions or say n times it had to perform to get the result, then the example used for this algorithm describes it’s worst case time complexity.
Below are some common time complexities with simple definitions. Feel free to check out Wikipedia, though, for more in-depth definitions.
Simple example with code -
So scenario on time complexity for this above given example would be -
Asymptotic Notations
Asymptotic Notations are languages that allow us to analyze an algorithm’s running time by identifying its behavior as the input size for the algorithm increases. This is also known as an algorithm’s growth rate.
The following 3 asymptotic notations are mostly used to represent time complexity of algorithms:
Big Oh (O)
Big Oh is often used to describe the worst-case of an algorithm by taking the highest order of a polynomial function and ignoring all the constants value since they aren’t too influential for sufficiently large input.
Big Omega (Ω)
Big Omega is the opposite of Big Oh, if Big Oh was used to describe the upper bound (worst-case) of a asymptotic function, Big Omega is used to describe the lower bound of a asymptotic function. In analysis algorithm, this notation is usually used to describe the complexity of an algorithm in the best-case, which means the algorithm will not be better than its best-case.
Big Theta (Θ)
When an algorithm has a complexity with lower bound = upper bound, say that an algorithm has a complexity O(n log n) and Ω(n log n), it’s actually has the complexity Θ(n log n), which means the running time of that algorithm always falls in n log n in the best-case and worst-case.
If you want to dive deep into time complexity, then refer Michael Olorunnisola ‘s article:
or look at Shilpa Jain ‘s article —
Space Complexity
Space complexity deals with finding out how much (extra)space would be required by the algorithm with change in the input size. For e.g. it considers criteria of a data structure used in algorithm as Array or linked list.
How to calculate space complexity of an algorithm — https://www.quora.com/How-do-we-calculate-space-time-complexity-of-an-algorithm
I’ll cover up at least 2 practically used algorithms in each category based on searching and sorting. I had written pseudocode and explanation in my personal notes(images here).
Searching Algorithms
Search algorithms form an important part of many programs. Some searches involve looking for an entry in a database, such as looking up your record in the IRS database. Other search algorithms trawl through a virtual space, such as those hunting for the best chess moves. Although programmers can choose from numerous search types, they select the algorithm that best matches the size and structure of the database to provide a user-friendly experience.
The general searching problem can be described as follows: Locate an element x in a list of distinct elements a1,a2,...an or determine that it is not in the list. The solution to this search problem is the location of the term in the list that equals x and is 0 if x is not in the list.
Linear Search
The linear search is the algorithm of choice for short lists, because it’s simple and requires minimal code to implement. The linear search algorithm looks at the first list item to see whether you are searching for it and, if so, you are finished. If not, it looks at the next item and on through each entry in the list.
How does it work ?
Linear search is the basic search algorithm used in data structures. It is also called as sequential search. Linear search is used to find a particular element in an array. It is not compulsory to arrange an array in any order (Ascending or Descending) as in the case of binary search.
Into Linear Search
Given a sample array as shown in figure and value we want to search for is 7, then it’ll traverse in linear way.
Pseudocode
Here is the pseudocode as divided into two images -
Linear search is rarely used practically because other search algorithms such as the binary search algorithm and hash tables allow significantly faster searching comparison to Linear search.
Time complexity
The time complexity of above algorithm is O(n).
Simple code in python -
Binary Search
Binary Search is one of the most fundamental and useful algorithms in Computer Science. It describes the process of searching for a specific value in an ordered collection.
Binary search is a popular algorithm for large databases with records ordered by numerical key. Example candidates include the IRS database keyed by social security number and the DMV records keyed by driver’s license numbers. The algorithm starts at the middle of the database — if your target number is greater than the middle number, the search will continue with the upper half of the database. If your target number is smaller than the middle number, the search will continue with the lower half of the database. It keeps repeating this process, cutting the database in half each time until it finds the record. This search is more complicated than the linear search but for large databases it’s much faster than a linear search.
This algorithm can be used when the list has terms occurring in order of increasing size
Binary Search is generally composed of 3 main sections:
- Pre-processing — Sort if collection is unsorted.
- Binary Search — Using a loop or recursion to divide search space in half after each comparison.
- Post-processing — Determine viable candidates in the remaining space.
How does it work ?
In its simplest form, Binary Search operates on a contiguous sequence with a specified left and right index. This is called the Search Space. Binary Search maintains the left, right, and middle indices of the search space and compares the search target or applies the search condition to the middle value of the collection; if the condition is unsatisfied or values unequal, the half in which the target cannot lie is eliminated and the search continues on the remaining half until it is successful. If the search ends with an empty half, the condition cannot be fulfilled and target is not found.
Into Binary Search
Given a sample array, first we find out midpoint and split it out. If midpoint is the search value, then it’s game over. So O(1) time complexity is achieved.
But if it’s not the midpoint’s value, then we have to go on an enchanted search for the value in divided halves. Because of this, now we can achieve time complexity in order of log(n) or n i.e. O(logn) or O(n).
You can see here in above example that 19 was found after so much of divisions of a single array(lists in python).
Pseudocode
There are two pesudocodes possible for this algorithm. 1. Iterative 2. Recursive.
You can find difference between iteration and recursion as part of debates in reddit or stackoverflow .
Time complexity
The time complexity of Binary Search can be written as
T(n) = T(n/2) + cBinary search implementation in python -
Sorting Algorithms
Ordering the elements of a list is a problem that occurs in many contexts. For example, to produce a telephone directory it is necessary to alphabetize the names of subscribers. Similarly, producing a directory of songs available for downloading requires that their titles be put in alphabetic order.
Putting addresses in order in an e-mail mailing list can determine whether there are duplicated addresses. Creating a useful dictionary requires that words be put in alphabetical order. Similarly, generating a parts list requires that we order them according to increasing part number.
The Art of Computer Programming, Donald Knuth devotes close to 400 pages to sorting, covering around 15 different sorting algorithms in depth! More than 100 sorting algorithms have been devised, and it is surprising how often new sorting algorithms are developed.
Bubble Sort
Bubble sort algorithm starts by comparing the first two elements of an array and swapping if necessary, i.e., if you want to sort the elements of array in ascending order and if the first element is greater than second then, you need to swap the elements but, if the first element is smaller than second, you mustn’t swap the element. Then, again second and third elements are compared and swapped if it is necessary and this process go on until last and second last element is compared and swapped. This completes the first step of bubble sort.
To carry out the bubble sort, we perform the basic operation, that is, interchanging a larger element with a smaller one following it, starting at the beginning of the list, for a full pass. We iterate this procedure until the sort is complete.
It is one of the most inefficient sorting algorithms because of how simple it is. While asymptotically equivalent to the other algorithms, it will require O(n²) swaps in the worst-case.
Pseudocode (Source — Wikipedia)
Suppose a is an array size n
swapped = true
while swapped
swapped = false
for j from 0 to N - 1
if a[j] > a[j + 1]
swap( a[j], a[j + 1] )
swapped = trueTime Complexity
- Worst and Average Case Time Complexity: O(n*n). Worst case occurs when array is reverse sorted.
- Best Case Time Complexity: O(n). Best case occurs when array is already sorted.
Insertion Sort
Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort. However, insertion sort provides several advantages:
How it works
To sort a list with n elements, the insertion sort begins with the second element. The insertion sort compares this second element with the first element and inserts it before the first element if it does not exceed the first element and after the first element if it exceeds the first element. At this point, the first two elements are in the correct order. The third element is then compared with the first element, and if it is larger than the first element, it is compared with the second element; it is inserted into the correct position among the first three elements.
Into Insertion Sort
Pseudocode
Time Complexity: O(n*n)
Auxiliary Space: O(1)
Boundary Cases: Insertion sort takes maximum time to sort if elements are sorted in reverse order. And it takes minimum time (Order of n) when elements are already sorted.
Uses: Insertion sort is used when number of elements is small. It can also be useful when input array is almost sorted, only few elements are misplaced in complete big array.
Implementation of Insertion Sort in python -
Conclusion
So, these were some basic algorithms that will provide a glimpse before diving deep into advanced and complex algorithms. As I titled it “I” part, I think I’ll be making part 2 covering more greedy and dynamic algorithms in future.
Also If I have been missing some topic to cover or maybe fault in my notes please put suggestions in comment.
Thank you for spending your time to read this article. Keep coding !
https://cdn.dribbble.com/users/571755/screenshots/3516921/big-data.jpg
Resources :
✉️ Subscribe to CodeBurst’s once-weekly Email Blast, 🐦 Follow CodeBurst on Twitter, view 🗺️ The 2018 Web Developer Roadmap, and 🕸️ Learn Full Stack Web Development.
