Counting sort implementation in Java

Please refer the below Github repo to know the counting sort implementation in Java

https://github.com/dkbalachandar/bucketsorting.git

Time complexity is O(n+m), here m is the number of elements in the array.

Advertisements

Binary Tree, Binary Search Tree, Heap, Min-Heap and Max-Heap

Binary Tree is a tree representation of data which satisfy the below condition
1. Each node in a tree contains at most two nodes.

Binary Search Tree is a tree representation of data which satisfy the below condition
1. Each node in a tree contains at most two nodes.
2. The value of the root node is greater than the value of the left node
3. The value of the right node is greater than the value of the root node

Heap is a tree based data structure which satisfies the below conditions

1. Its a complete Binary Tree which means all the levels are completely filled

2. All nodes are greater than/Smaller than its children. If the parent node is greater than its children, then that heap is called as Max Heap. If the parent node is less than its children then that is called as Min Heap

Remove Git Repository History

Please follow the below steps to completely remove the commit history

1. Clone the Git repository
2. Run rm -rf .git to remove all the .git files
3. Then run the below command to initialize the repo again and commit the changes


git init
git add .
git commit -m "Commit message"

4. Push the changes to Git


git remote add origin REPO_URL
git push -u --force origin master

Bucket Sorting In Java

This algorithm works by distributing the element into a buckets, then sorting the bucket contents, finally combining the all the buckets one by one

Best case and Average case Time complexity is O(n+m), where m is the largest number in the data set

Worst case time complexity is O(n^2)

Please refer the below GitHub repository

https://github.com/dkbalachandar/bucketsorting

Algorithm Time Complexity

O(1) – Completes the operation/process in a single step. Best example is the number to search in an array is present in the first index itself
O(n) – Completes the operation/process in n steps. So the time gets increased linearly. Best example is the number to find in an array is present in the last index only
O(log n) – Completes the operation/process in n/2 steps. Best example, do a binary search in a sorted array.
O(n^2) – Completes the operation n^2 steps. Best example is sorting an array by bubble sort.
O(n log n) – Completes the operation n*n/2 steps. Best example is sorting an array by quick sort.