Skip to main content

Posts

Showing posts from November, 2020

Heap Sort Java Program

This tutorial shows how to write Heap sort program in Java which is an in-place sorting algorithm. Heap sort uses heap data structure for sorting the elements so the obvious question is what is heap? Table of contents Heap data structure Heap sort algorithm How to create heap from array Heap Sort Java program Heap sort time and space complexity Heap data structure A heap is a binary tree so each node can have maximum two children and it has following properties- It is a complete binary tree which means reading from left to right it is completely filled in (all the nodes have 2 children) except the last row which need not be full. Each node in the heap satisfies the condition that each node is greater than or equal to its child nodes in case of Max heap. Node is less than or equal to its child nodes in case of Min heap. Heap sort algorithm Steps for writing the Heap Sort Java program are as follows- Create a max heap from input array. Usin

Tree Sort Java Program

This tutorial shows how to write Tree sort program in Java. Tree sort uses a Binary Search Tree (BST) for sorting the elements. What is a Binary Search Tree Binary Search Tree (BST) is a special kind of binary tree where node’s left child has a value less than its parent node and the node’s right child has a value greater than or equal to its parent node. Following image shows a Binary search tree with nodes. As you can see left subtree has nodes with values less than the root node and the right subtree has nodes with values greater than the root node. Tree Sort Algorithm Tree sort work as follows- Using the elements in an input array create a Binary search tree. Do an in-order traversal of the BST to get elements in sorted order. In-order traversal is done by first visiting the left subtree nodes then root node and then the right subtree nodes. Tree Sort Java Program To represent a BST node a Node class is required which has two references to itself. These refer

Radix Sort Java Program

This tutorial shows how to write Radix sort program in Java. Radix sort is also one of the linear sort algorithm which runs in O(n) time like Counting sort and Bucket sort making Radix sort faster than Quick sort or Merge sort which run in O(n*logn) time. Radix sort algorithm Radix sort works by doing the sorting in passes moving from least significant digit to most significant digit. Radix sort also uses buckets, in each pass you need to get digit of the number based on the pass (1s place, 10s place etc.) and store those digits in buckets. In each pass you can use a stable sort like Counting sort to sort the numbers on the digit. Steps for the Radix sort algorithm can be summarized as follows- Get the maximum number in the input array. Iterate each digit of the maximum number starting from the least significant digit i.e. unit place moving towards the most significant digit. For each element in the array get the digit at that position and store it in the bucket

Bucket Sort Java Program

This tutorial shows how to write Bucket sort program in Java. Bucket sort is also one of the linear sort algorithm which runs in O(n) time like Radix sort and Counting sort making it faster than Quick sort or Merge sort   both of which run in O(n*logn) time. Bucket sort makes some assumption about the data that it should be uniformly distributed over a range. Bucket Sort Algorithm Bucket sort works by distributing the element over different buckets. Bucket term used here is also an array and the distribution of elements to these buckets is done by using a hash function. The hash function used for calculating hash value must follow these requirements- It returns array indices in range 0..bucket_array_length-1 It is ordered: if A[i] < A[j] then hash(A[i]) < hash(A[j]) The steps in Bucket sort are as follows- Distribute elements to the bucket array using hash function. Associate a list with each bucket array index, if two elements have a same hash i.e. ther

Counting Sort Java Program

This tutorial shows how to write Counting sort program in Java. Counting sort is an integer sort algorithm. It is different from other comparison based algorithms like merge sort , selection sort as it doesn’t sort by comparing values. In counting sort, frequency of each element is counted and using it final position of each element is calculated. One of the restriction while using Counting sort is that range of elements (maximum element) has to be known. Counting sort also needs extra space for storing frequency of elements. Counting Sort Algorithm 1- In counting sort initially you need to count the frequency of each element and keep that in count array. So first thing is to create a count array. Length of the count array is calculated as– Max element in the input array + 1 . For example if the maximum element in the input array is 10 then length of count array is 11. 2- Each index in the count array maps to element 0 to max element in input array. So increment the count at

Quick Sort Java Program

This tutorial shows how to write Quick sort program in Java. Quick sort is also a "divide and conquer algorithm" like Merge sort . Quick Sort Algorithm Quick sort works as follows- Chose an element as pivot and then partition all the elements around that pivot. All the elements having value less than the pivot come before the pivot. All the elements having value higher than the pivot come after the pivot. Once the elements are partitioned around pivot you get two sub-arrays. One on the left of the pivot having values smaller than the pivot and another on the right of the pivot having values greater than the pivot. Steps 1-3 are executed recursively for these 2 sub-arrays. One of the decision you have to make while implementing Quick sort is what value should be chosen as pivot, options are- First element as pivot. Last element as pivot (Quick sort implementation in this post uses this approach) Middle element as pivot. Median of the item

Shell Sort Java Program

This tutorial shows how to write Shell sort program in Java. Shell sort is also an in place sorting algorithm like Bubble sort , Selection sort but it is faster than these algorithms. Shell sort algorithm Shell sort is based on Insertion sort and it improves on it to make sorting more efficient. In insertion sort if a small element is farther on the right that will require shifting a lot of element to bring it at its proper place on the left. In Shell sort insertion sorting is done on elements at certain interval. Once these elements are sorted interval is reduced and sorting is done on elements at the new interval, once those elements are sorted interval is further reduced and so on. This process is repeated until the interval between elements is 1. At that time adjacent elements are compared and shell sort effectively becomes insertion sort in that iteration. By the time, interval becomes 1 and adjacent elements are compared array is already ' almost sorted ' be

Merge Sort Java Program

This tutorial shows how to write Merge sort program in Java. Merge sort is termed as a " divide and conquer algorithm " and it is considered to be more efficient than the simple sort algorithms like selection sort and insertion sort . Merge sort algorithm The algorithm for merge sort is based on the process of merging where two sorted arrays are merged to form a large sorted array. To merge the smaller arrays first you do need to divide your array into smaller arrays too so effectively Merge sort is a two step process. Divide the input array into two halves this process is carried out recursively until you get sub-arrays with only one element which is the base case for the recursive division. These sub-arrays of one element each are considered as sorted arrays. In this step these smaller arrays are sorted and merged recursively until you again get the larger sorted array. Merging process starts from bottom where a pair of single element sub-arrays are sorted an

Insertion Sort Java Program

This tutorial shows how to write Insertion sort program in Java. Insertion sort is considered the best among the three simple sorting algorithms, the other two simple sorting algorithms are Bubble sort and Selection sort . Though the time complexity of Insertion sort is also O(n 2 ) but it is considered much faster than bubble sort because of less number of swaps and faster than Selection sort in most scenarios. Insertion sort algorithm Insertion sort works on the concept of “partially sorted”, at any given point elements on the left hand side of the current index are considered sorted. Note that those elements are considered sorted among themselves as they are not yet at their final position that is why term “partially sorted”. Any remaining element (element at the current index or the remaining elements on the right side) may have to inserted in between the previously sorted elements which will require shifting of the elements to the right to make place for the inserted ele

Selection Sort Java Program

This post shows how to write Selection sort program in Java. Selection sort is also an in place sorting algorithm like Bubble sort that works by comparing and swapping elements in each pass. Selection sort algorithm Selection sort works as follows- Start with the left most element (index 0) and compare it with the elements on the right side to see if there is any element smaller than that element. If yes then this new element becomes the lowest element for further comparisons in that iteration. By the end of the iteration you get the index of the lowest element. Swap the lowest element with the leftmost element. So, by the end of the first pass you have the lowest element at its proper place. In the next pass start with index 1 and again follow the same process. For example if array is {5, 4, 7, 1, 8} then start with element at index 0 and compare it with adjacent element. After first pass you have the index of the lowest element which is then swapped with

Bubble Sort Java Program

This tutorial shows how to write Bubble sort program in Java. Bubble sort is considered the simplest sorting algorithm out of the three simple sort algorithms, other two being Selection sort and Insertion sort , that work by comparing and swapping elements in each pass. Since there are a large number of comparisons and swaps Bubble sort is also considered the slowest sorting algorithm. Bubble sort algorithm Bubble sort works as follows- You start from the left end and compare the first two elements (i.e. element at index 0 and index 1). If element on the left is greater than the element on right ( element at 0 > element at 1) you swap those two. Move to next index and compare the two adjacent elements (i.e. element at index 1 and index 2). Again if element on the left is greater than the element on right you swap them. This process is repeated until you reach the rightmost element. This is the first pass of the bubble sort and by the end of the first pass you have the g

Java TreeSet With Examples

TreeSet in Java is one of the implementation of the Set interface. How it differs from the other popular implementation HashSet is that unlike HashSet which is unordered, TreeSet stores its element in sorted order. The elements in TreeSet are ordered using their natural ordering, or by a Comparator provided at set creation time, depending on which constructor is used to create the TreeSet. TreeSet implementation in Java If you have idea about the HashSet Internal Implementation in Java then you must be knowing that internally HashSet uses HashMap to store its element. Same way TreeSet internally uses TreeMap . TreeSet in Java is a NavigableSet implementation based on a TreeMap. Features of TreeSet in Java Some of the features of the TreeSet which are discussed in this post are as follows- TreeSet stores only unique elements like other Set implementations. TreeSet stores its element in sorted order. Null elements are not permitted in TreeSet. TreeSet is not