Heap

Reading Time: 3 minutes

Description

Heap is a tree-based data structure with some special attributes embedded into it. Heap Data Structure has such characteristics;

It is a form of Complete Binary Tree,
It has a root node and its key is compared to the children nodes and the comparison is constantly carried out whenever a new node is aimed to be inserted.

In addition to the characteristics, the Heap can be internally implemented using Array or Priority Queues. The common practice is usually done with the Priority Queue.

Types of Heap

Heap Data Structure has mainly two types. These types correspond to how the order of the Heap is placed. Let’s have a look at the types in details;

Min Heap

The values of children are greater than or equal to the value of their parents; which indicates that parent nodes tend to have lower values than the children nodes.

Max Heap

The values of children are less than or equal to the value of their parents; which indicates that parent nodes tend to have greater values than the children nodes.

Complexity of Heap

The Time and Space complexities are summed up into a common table given as:

Usage Areas of Heap

Heap Data Structure makes great use in the following areas:

Heap Sort: Very efficient sorting algorithm whose time complexities are all the same O (n log n),
Priority Queues: The Priority version of Queue benefits efficiently from the Heap Data structure that provides insertion, deletion extract maximum and decrease key operations in the O (log n) time complexity

Terminology

Heapify

Heapifying is a recursive process of turning the Heap to the Max Heap type, our algorithm will go towards the non-leaf nodes and look for the largest node in the tree and in all possibilities, raise the greater values above top contentiously.

Parent Node

Left node of the Tree the presentation in the array: (index -1) / 2;

Left Node

Left node of the Tree the presentation in the array: 2 * index + 1;

Right Node

Right node of the Tree the presentation in the array: 2 * index + 2;

Heap Sort

Heap sort is a very efficient algorithm that performs very well in sorting arrays.

Time Complexity

All the cases are O(n log n)

Space Complexity

O(1)

Heap Sort Code

You can checkout my GitHub repository @ https://github.com/tugrulaslan/BlogCodeSnippets/tree/master/SortingAlgorithms

Radix Sort

Reading Time: 2 minutes

Definition

The optimal algorithm for the numbers range from 1 to n². Radix Sort algorithm favors of Counting Sort internally to sort the array. The given keys consists of the digits in each element in the array.
It starts from the Least Significant Digit which is the left digit, then goes to the Most Significant Digit which means to the right.

Each digit goes to a corresponding numbered buckets. After the buckets is filled with the elements in the array, the elements are sorted once again according to the bin position. Let’s us see an example illustration to better apprehend the logic, we will sort the numbers “551, 12, 346, 311”;

*Visual Array Status of Sorting Phases by Radix Sort*

Now we have more or less how the Radix Sort works out internally. There is one gap I’d like to point what happens to 12 which has two digits compared to the others that have three digits. Well in this situation such numbers are appended with leading 0s and they always sit on the bucket zero.
n numbers consisting of k digits

Complexity

Time Complexity

n: number of elements
k: the range of the keys for each number. We will also repeat the operation for this amount.
All of the Time Complexities of Radix Sort is always O(n*k)

Space Complexity

Space complexity of Radix Sort is O(n+k)

Code

You can checkout my GitHub repository @ https://github.com/tugrulaslan/BlogCodeSnippets/tree/master/SortingAlgorithms

Shell Sort

Reading Time: < 1 minute

Definition

Shell Sort is a variation of the Insertion Sort. Shell Sort is very fast algorithm that is compact in code size. A gap in other words a distance is set that will be used between the elements in the array
Sub lists are made out of the elements in the gap and the sub lists are compared. In the comparison lower element goes to the left and greater is on the right.
The process continues, later on the gap gets smaller until it becomes one. After the gap reaches to one, then the Insertion Sort is applied to sort the rest. Depending of this gap the time complexity of the algorithm varies.

Code

The code can be also found in my Github Repository @ https://github.com/tugrulaslan/BlogCodeSnippets/tree/master/SortingAlgorithms

Insertion Sort

Reading Time: < 1 minute

Definition

The 1st element is assumed to be sorted and the iteration starts from the second element towards the end. The difference in this algorithm compared to Bubble Sort,
it compares the element that are on the left of it. It all means that the sorting goes not forward, but backwards from the right to the left.
This algorithm is sufficient on smaller data sets like Bubble Sort, because its Time complexity is O(n²).
In the implementations of the Insertion Sort only space complexity changes;
*. Imperative: O(1)
*. Recursive: O(n) because of the stacks that are created
The both imperative and the recursive versions are very similar, except in the recursive version, the comparison will start when the i is in second elements index which is 2

Code

The code can be also found in my Github Repository @ https://github.com/tugrulaslan/BlogCodeSnippets/tree/master/SortingAlgorithms

Merge Sort

Reading Time: 2 minutes

Definition

Merge sort yet another sorting algorithm that benefits from the divide-and-conquer principle. The main goal in this algorithm is to split the given array into individuals and merge them back during the course of the comparison.
Merge Sort seems kind of similar to the Merge sort, in the Comparison below you can study the differences and similarities. However, there is one challenge as I see in this algorithm is the merge. I find this part very complex, but besides its very easy to apprehend the algorithm.

Complexity Analysis

Time Complexity

Best Case: O(n log n),
Average Case: O(n log n),
Worse Case: O(n log n)

Space Complexity

O(n)

Comparison to Quick Sort

In general terms, the Merge Sort is often compared to the Quick Sort. In some sense, they tend to act similarly as they inherit the same divide-and-conquer principle, to address a few of differences;

Merge Sort demands a copy of the data structure, whereas Quick Sort applies the changes with no requirement of extra space allocated,
Both of the algorithms split the given data structure. However, alternatively Merge Sort intends to split from the half to divide the left and right subsets into individual elements, whereas the Quick Sort picks a partition point and swaps the lower and greater values in the right and the left directions.

Operations

The algorithm divides the array into half smaller chunks until the individual items left with by using recursion,
once individuals created, they are compared and merged back from smaller to larger arrays
Merge sort requires extra space allocation which makes it space complexity as O(n), whereas Quick Sort only keeps a space while swapping which makes its space complexity as O(log n). However the only similarity is that because of the recursive calls, the stack traces will be created upon each call that’s also considered as a space

Terms

leftPointer: A pointer of the left/begin of the array
rightPointer: A pointer of the right/endof the array
middleElementPointer: Represents the element in the center of the array
leftArray: The elements of the left side as a temporary storage
rightArray: The elements of the rıght side as a temporary storage

Code

You can checkout my GitHub repository @ https://github.com/tugrulaslan/BlogCodeSnippets/tree/master/SortingAlgorithms

Quick Sort

Reading Time: < 1 minute

Definition

Quick sort is a very efficient algorithm that leverages the divide-and-conquer principle to sort a data structure. The calculated performance complexity of Quick Sort as follows;

Best Case: O(n log n),
Average Case: O(n log n),
Worse Case: O(n²), reason: the algorithm will select only one element in each iteration
Space Complexity: O(log n).

Terminology

Furthermore, for starters, it will be a good practice to apprehend the terms in this algorithm;

Pivot: A reference element that is used as a line whose left and rights elements are divided. There are a few Quick Sort implementations, whose suggestions vary from picking the Pivot from the beginning, middle, end or randomly,
Partition: It is a practice that swaps elements on the left and right ends, while using the Pivot as a reference. By the end of Partitioning, a partition point for the next divided subsets(those will be divided also) is returned,
Left Pointer: A pointer or an index value that traverses on the last/low/left subset of the designated array,
Right Pointer: A pointer or an index value that traverses on the last/low/right subset of the designated array,

Internal of the Algorithm

In every step, the Quick Sort divides the array to subsets and aims to collect the lower numbers on the left side, the greater numbers on the right side of the pivot in an ascending format. Let’s look at a glance how the code performs the operation;

Choosing a Pivot,
Beginning the partitioning by swapping the lower elements on the left, greater elements on the right side of the pivot,
Apply partitioning on the left side and later on the right side.

Code

you can checkout my GitHub repository @ https://github.com/tugrulaslan/BlogCodeSnippets/tree/master/SortingAlgorithms

Selection Sort

Reading Time: < 1 minute

Description

Selection Sort searches through the list of array to find the smallest item in the unsorted list.
Sorting starts from the left to the right, all the sorted elements reside on the left side of the array.
Selection sort is not a fast algorithm, because it uses nested loops to sort. It comes handy when we sort smaller data sets. It’s worse-case run time complexity is O(n²)

Code

The code can be also found in my Github Repository @ https://github.com/tugrulaslan/BlogCodeSnippets/tree/master/SortingAlgorithms

Bubble Sort

Reading Time: < 1 minute

Description

Bubble sort will repeatedly compare and swap adjacent items. If the item on the left is greater, it swaps it with the right item. Basically the greater items are shifted towards the right direction.
Furthermore, the second iteration is stopped because the last items are sorted already we wont go though them again. Furthermore, Bubble Sort is not an efficient sorting algorithm because it uses nested loops. It is only useful for small data sets. It’s worse-case run time complexity is O(n²)

Code

The code can be also found in my Github Repository @ https://github.com/tugrulaslan/BlogCodeSnippets/tree/master/SortingAlgorithms