Algorithms

“Programming is the art of algorithm design and the craft of debugging errant code.”

What is an algorithm?

An algorithm is merely a set of instructions for completing a task. They’re the fundamental components of programming, allowing computers, smartphones, and websites to function and make decisions.

Different types of algorithms

• Brute Force Algorithm

A brute force algorithm basically tries all the possibilities until it finds one that works. This is the most basic and straightforward type of algorithm. These algorithms are often used to find the optimal or best solution since they verify all possible solutions. It’s also used to find a workable (but not ideal) solution, essentially stopping when a solution to the problem is found. It is a straightforward approach to dealing with a problem, and it is the first thing that comes to mind after we observe the problem.

• Recursive Algorithm

Recursion is used in this type of algorithm. In recursion, an issue is deciphered by breaking it down into similar subproblems and calling itself over and over until the problem is solved with the help of a base condition. It correctly solves the base case and then recurs with a more straightforward or simpler input each time. It is used to deal with problems that may arise.

• Dynamic Programming Algorithm

The memoization method is another name for this kind of algorithm. This is because the thought is to save the recently determined result in order to avoid having to figure it out again and again. Partition the unexpected issue into more manageable covering subproblems and save the outcome for later in Dynamic Programming. In simple terms, it remembers the past outcome and applies it to the discovery of new outcomes.

• Divide and Conquer Algorithm

The Divide and Conquer algorithm divides the problem into two sections; the first section divides the problem into subproblems of a similar nature. The second section is to deal with the more minor issue on its own, then combine the results to produce the final answer to the problem.

• Greedy Algorithm

Now we’ll look at another kind, which is a greedy algorithm, in which the solution is built piece by piece. The decision to choose the next role is made with the intention of providing immediate assistance and never considering the alternatives that had previously been considered.

Sorting Algorithms

Let’s talk about sorting algorithms for a moment. A sorting algorithm is a computer science term for an algorithm that arranges elements of a list in a specific order. Sorting is important for improving the efficiency of other algorithms that require sorted lists as input data.

COUNTING SORT

It’s a sorting method based on keys that fall within a certain range. It works by determining the number of objects with unique key values (kind of hashing). The position of each object in the output sequence is then calculated using arithmetic. It is not a contrast since counting sort takes key values as indexes into an array, and the (n log n) lower bound for comparison sorting does not apply to it.

TIME COMPLEXITY

O(n+k) time complexity, where n is the number of elements in the input array and k is the input range.
O(n+k) Auxiliary Space

Here input is the input array to be sorted, key returns the numeric key of each item in the input array, count is an auxiliary array used first to store the numbers of items with each key, and then (after the second loop) to store the positions where items with each key should be placed, k is the maximum value of the non-negative key values and output is the sorted output array.

In summary, the algorithm loops over the items in the first loop, computing a histogram of the number of times each key occurs within the input collection. After that, it then performs a prefix sum computation on count to determine, for each key, the position range where the items having that key should be placed in; i.e. items of key {\displaystyle i}

should be placed starting in position count[{\displaystyle i}

]. This is done through the second loop. Finally, it loops over the items again in the third loop, moving each item into its sorted position in the output array.[1][2][3] The relative order of items with equal keys is preserved here; i.e., this is a stable sort.

SHELL SORT

ShellSort is essentially an Insertion Sort variant. We only move elements one position forward in insertion sort. Many movements are required when an element must be moved far ahead. The goal of shellSort is to allow for the exchange of items from afar. For a large value of h, we use shellSort to sort the array. We reduce the value of h until it equals one. An array is said to be h-sorted if all sublists of every h’th element is sorted.

Time Complexity: Worst case time complexity: Θ(N (log N)^2) comparisons

• Average case time complexity: Θ(N (log N)^2) comparisons
• Best case time complexity: Θ(N log N)
• Space complexity: Θ(1).

Shellsort (also known as Shell sort or Shell’s method) is an in-place comparison based sorting algorithm.

By taking advantage of the fact that using Insertion Sort on a partially sorted array results in fewer moves, Shell Sort increases its time complexity.

It is a generalization of:

• sorting by exchange (bubble sort)
• sorting by insertion (insertion sort)

If the gap sequence is (5,3,1) and the array consists of 14 elements (a1, a2, …, a14), then, there are three passes.

• In the first pass, the elements are grouped as (a1, a6, a11), (a2, a7, a12), (a3, a8, a13), (a4, a9, a14), (a5, a10). Each group is sorted using Insertion Sort.
• In the second pass, the 3-sorting is performed on groups (a1, a4, a7, a10, a13), (a2, a5, a8, a11, a14), (a3, a6, a9, a12).
• In the third (last) pass, 1-sorting is performed on (a1, a2, …, a14).
• Applications of Shell Sort includes:
• Shellsort performs more operations and has higher cache miss ratio than quicksort.
• However, since it can be implemented using little code and does not use the call stack, some implementations of the qsort function in the C standard library targeted at embedded systems use it instead of quicksort. Shellsort is, for example, used in the uClibc library. For similar reasons, an implementation of Shellsort is present in the Linux kernel.
• Shellsort can also serve as a sub-algorithm of introspective sort, to sort short subarrays and to prevent a slowdown when the recursion depth exceeds a given limit. This principle is employed, for instance, in the bzip2 compressor.

Pseudo Code

These are two of the lesser popular sorting techniques. But both are unique in their own way and will help you overcome your sorting problems. Where counting sort sorts without comparing Shellsort is a variation of insertion sort. Hope these will be of use to you.

Happy Coding!