Tech Tutorials

Showing posts with label sorting algorithms. Show all posts

Tuesday, May 21, 2024

Bubble Sort Program in Java

In this post we’ll see how to write Bubble sort program in Java. Out of the three simpler sorting algorithms Bubble sort, Insertion sort and Selection sort, Bubble sort is considered the simplest sorting algorithm and the slowest too because of a proportionally large number of swaps along with the comparisons.

How Bubble sort works

In bubble sort you start by comparing the first two elements (index 0 and index 1). If element at index 0 is greater than the element at index 1 then those two elements are swapped, if it is not then you do nothing. Then the next 2 elements are compared (index 1 and index 2) and elements are swapped based on the same logic.

So the steps for bubble sort are as follows-

Compare the adjacent elements.
If element at the left is greater than the element at the right then swap the elements.
Move one position right.

You continue doing that until you reach the last element, by then you have the greatest element at the right. Since the biggest elements bubble up to the top end thus the name “Bubble sort”.

This is the first pass, in the next iteration again you start from the two leftmost elements and compare the elements and swap if required. Since the rightmost element is already in its sorted position so this iteration runs till (N-1) elements.

For example if you have an array [5, 2, 6, 1] then in the first iteration-

Initially 5 is compared with 2, since 5 (element at left) is greater than 2 (element at right), elements are swapped making the array [2, 5, 6, 1].
Move over one position and compare 5 and 6, since 5 is not greater than 6 so nothing is done and array remains [2, 5, 6, 1].
Again move over one position and compare 6 and 1, since 6 is greater than 1 elements are swapped giving us the array as [2, 5, 1, 6].

In the next iteration last element is not included in the comparison as it is already at its final position.

Bubble Sort Java program

public class BubbleSort {

  public static void main(String[] args) {
    int[] intArr = {47, 85, 62, 34, 7, 10, 92, 106, 2, 54};
    int[] sortedArray = bubbleSort(intArr);
    System.out.println("Sorted array is- ");
    for(int num : sortedArray){
      System.out.print(num + " ");
    }
  }
    
  private static int[] bubbleSort(int[] intArr){
    // right to left 
    for(int i = intArr.length; i > 1; i--){
      for(int j = 0; j < i - 1; j++){
        //if greater swap elements
        if(intArr[j] > intArr[j+1]){
          swapElements(j, intArr);
        }
      }            
    }
    return intArr;
  }
    
  private static void swapElements(int index, int[] intArr){
    int temp = intArr[index];
    intArr[index] = intArr[index+1];
    intArr[index+1] = temp;        
  }
}

Output

Sorted array is- 
2 7 10 34 47 54 62 85 92 106

Time and Space complexity of Bubble sort

For bubble sort there are two loops that go through the elements that makes it a complexity of N*N i.e. O(N²). In bubble sort the number of swaps is also high which makes it slow.

Bubble sort is an in place sorting algorithm so there is no auxiliary space requirement. Thus the space complexity of Bubble sort is O(1).

That's all for this topic Bubble Sort Java Program. If you have any doubt or any suggestions to make please drop a comment. Thanks!

>>>Return to Java Programs Page

Related Topics

You may also like-

Monday, April 22, 2024

What is In-place Algorithm

An in-place algorithm is an algorithm that doesn’t use any auxiliary space to transform the input. Though theoretically that would mean if you have an array of length n then you should use that n space itself to transform the input array but in reality you will definitely use some variables and index for array and that kind of auxiliary space is allowed for an in-place algorithm.

Examples of in-place algorithm are sorting algorithms like Bubble sort, Selection Sort, Insertion Sort which doesn’t require any extra space to perform sorting. That is why space complexity for these algorithms is O(1).

Merge sort, Bucket sort are examples of not in-place or out-of-place sorting algorithms.

In-place algorithm example

Let’s try to understand this auxiliary space requirement of in-place algorithm by taking an algorithm to reverse an array by using separate input and output arrays making it a not in-place algorithm.

import java.util.Arrays;

public class ReverseArray {
  public static void main(String[] args) {
    int[] intArr = {47, 85, 47, 34, 7, 10, 0, 106, 2, 54};
    reverseArray(intArr);
  }
    
  static void reverseArray(int[] intArray) {
    int n = intArray.length;
    // Using another array
    int[] tempArray = new int[n];
    for (int i = 0; i < n; i++) { 
      tempArray[n - i - 1] = intArray[i]; 
    } 
    System.out.println("Reversed Array- " + Arrays.toString(tempArray));
  }
}

But the algorithm to reverse an array can very well be written to use the same input array to reverse it. There is no need to use a separate array making it an in-place algorithm.

public class ReverseArray {
  public static void main(String[] args) {
    int[] intArr = {47, 85, 47, 34, 7, 10, 0, 106, 2, 54};
    reverseArray(intArr);
  }
    
  static void reverseArray(int[] intArray) {
    int n = intArray.length;
    for (int i = 0; i < n / 2; i++) {
      int temp = intArray[i];
      intArray[i] = intArray[n - 1 - i];
      intArray[n - 1 - i] = temp;
    }
    System.out.println("Reversed Array- " + Arrays.toString(intArray));
  }
}

That's all for this topic What is In-place Algorithm. If you have any doubt or any suggestions to make please drop a comment. Thanks!

>>>Return to Java Programs Page

Related Topics

You may also like-

Thursday, January 4, 2024

Bubble Sort Program in Python

In this post we’ll see how to write Bubble sort program in Python. Bubble sort is considered the simplest sorting algorithm out of the three simpler sorting algorithms bubble sort, insertion sort and selection sort. Bubble sort is considered the slowest too because of a proportionally large number of swaps along with the comparisons.

How does Bubble sort work

In Bubble sort adjacent elements are compared and swapped if element at left is greater than element at right. For example if n[0] and n[1] are compared and n[0] > n[1] then n[0] and n[1] are swapped. Then you move by one index and compare the adjacent elements i.e. n[1] and n[2].

By the end of first pass you should have the maximum element in the list at the rightmost position. Since the maximum element bubbles up to the top thus the name Bubble sort.

To sum up the steps for bubble sort-

Compare the adjacent elements.
If element at the left is greater than the element at the right then swap the elements.
Move one position right. Start from point 1.

In the next pass again you start from the two leftmost elements and compare the elements and swap if required. Since the rightmost element is already in its sorted position so this pass runs till (N-1) elements.

For example if you have an array [5, 3, 8, 2] then in the first pass-

Iteration 1- Initially 5 is compared with 3, since 5 (element at left) is greater than 3 (element at right), elements are swapped making the array [3, 5, 8, 2].

Iteration 2- Move to next position and compare element at index 1 and index 2 (5 and 8), since 5 is not greater than 8 so swapping is not done and array remains [3, 5, 8, 2].

Iteration 3- Again move over one position and compare 8 and 2. Since 8 is greater than 2, elements are swapped giving us the array as [3, 5, 2, 8].

As you can see by the end of first pass the maximum element is at the rightmost position. In the next pass last element is not included in the comparison as it is already at its final position so the array that is considered for comparison and swapping effectively becomes [3, 5, 2].

Bubble Sort Python program

def bubble_sort(nlist):
  list_length = len(nlist)
  # reduce length by 1 in each pass
  for i in range(list_length-1, 0, -1):
    for j in range(i):
      # compare
      if nlist[j] > nlist[j+1]:
        # swap elements
        nlist[j+1], nlist[j] = nlist[j], nlist[j+1]

nlist = [47, 85, 62, 34, 7, 10, 92, 106, 2, 54]
print('Original List-', nlist)
bubble_sort(nlist)
print('Sorted List-', nlist)

Output

Original List- [47, 85, 62, 34, 7, 10, 92, 106, 2, 54]
Sorted List- [2, 7, 10, 34, 47, 54, 62, 85, 92, 106]

Time and Space complexity of Bubble sort

In Bubble sort (N-1) comparisons are required in the first pass, (N-2) comparisons in the second pass, (N-3) comparisons in the third pass and so on.

So the total number of comparisons is- N(N-1)/2

Thus the time complexity of Bubble sort is O(n²).

Bubble sort is an in-place sorting algorithm and doesn’t require any auxiliary space so the space complexity of Bubble sort is O(1).

That's all for this topic Bubble Sort Program in Python. If you have any doubt or any suggestions to make please drop a comment. Thanks!

>>>Return to Python Programs Page

Related Topics

You may also like-

Thursday, May 5, 2022

Radix Sort Program in Java

In this post we’ll see how to write Radix sort program in Java. Radix sort is in the league of Counting Sort and Bucket Sort which are O(n) sorting algorithms.

How does Radix sort work

Radix sort works by doing the sorting in passes moving from least significant digit to most significant digit. In each pass you can use any stable sort to sort the numbers on the digit.

If you have an array Arr with the maximum element in array Arr having number of digits as d, then the working of Radix sort is as shown below.

for i = 1 to d
 Use any stable sort (like counting sort)
        to sort Arr on digit d

Following image shows how Radix sort sorts an input array in each pass. Here the maximum number is 655 so number of passes is 3.

Radix Sort Java program

Java program for Radix sort works on the following logic.

Find the maximum number in the input array.
Loop to iterate each digit of the maximum number starting from the least significant digit.
Sort the array on that digit using Counting sort.

public class RadixSort {

  public static void main(String[] args) {
    int[] arr = {80, 406, 21, 655, 55, 4, 8, 91, 87, 6};
    System.out.println("Original Array- " + Arrays.toString(arr));
    radixSort(arr);
    System.out.println("Sorted array after Radix sort- " + Arrays.toString(arr));
  }
    
  private static void radixSort(int[] arr){
    int max = getMaxElement(arr);
    int position = 1;
    while(max/position > 0){
      countingSort(arr, position);
      position *= 10;
    }        
  }
        
  private static int getMaxElement(int[] arr){
    int max = arr[0];
    for(int i = 1; i < arr.length; i++){
      if (arr[i] > max){
        max = arr[i];
      }
    }
    return max;
  }
    
  private static void countingSort(int[] arr, int position){
    int n = arr.length;
    int[] output = new int[n];
    int[] count = new int[n];
      
    //count number of times each element appear
    for(int i = 0; i < arr.length; i++){
      count[(arr[i]/position)%10]++;
    }

    // each element stores (element at current index+element
    // at previous index) to get the actual position of the element
    for(int i = 1; i < n; i++){
      count[i] = count[i] + count[i-1];
    }
  
    // for correct placement of the numbers start from the end
    for(int i = n-1; i >=0; i--){
      output[count[(arr[i]/position)%10] - 1] = arr[i];
      count[(arr[i]/position)%10]--;
    }
    // Copy output array to input to the input for 
    // the next stage of counting sort
    for(int i = 0; i < output.length; i++){
      arr[i] = output[i];
    }
    System.out.println("Counting sort at this stage " + Arrays.toString(arr));
  }
}

Output

Original Array- [80, 406, 21, 655, 55, 4, 8, 91, 87, 6]
Counting sort at this stage [80, 21, 91, 4, 655, 55, 406, 6, 87, 8]
Counting sort at this stage [4, 406, 6, 8, 21, 655, 55, 80, 87, 91]
Counting sort at this stage [4, 6, 8, 21, 55, 80, 87, 91, 406, 655]
Sorted array after Radix sort- [4, 6, 8, 21, 55, 80, 87, 91, 406, 655]

Performance of Radix Sort

If you are using Counting sort for sorting in each pass of Radix sort then time complexity of Radix sort is O(d*(n+k)). Here O(n+k) is the time complexity of counting sort and d is the number of passes over number having d digits.

Auxiliary space requirement is (n+k). Count array takes k space and the output array of the same size as input array is also used while sorting. Thus the space complexity of Radix sort is O(n+k).

That's all for this topic Radix Sort Program in Java. If you have any doubt or any suggestions to make please drop a comment. Thanks!

>>>Return to Java Programs Page

Related Topics

You may also like-

Tuesday, May 3, 2022

Tree Sort in Java Using Binary Search Tree

In this post we’ll see how to write Tree sort program in Java. Tree sort is a sorting algorithm that uses the Binary Search tree data structure for sorting.

Binary Search tree

Binary tree is a tree structure where each node has a maximum of two children. A kind of binary tree used for Tree sorting is known as a Binary Search Tree (BST).

In Binary search tree for each node the node’s left child must have a value less than its parent node and the node’s right child must have a value greater than (or equal) its parent. If we consider the root node of the binary search tree the left subtree must have nodes with values less than the root node and the right subtree must have nodes with values greater than the root node.

How does Tree sort work

To write a Tree sort program steps are as following.

From the input array create a Binary search tree structure.
Traverse the Binary search tree to get the elements in sorted order.
- By doing an in-order traversal, which means starting from the left subtree, then the root node and then visit the right subtree, you can get the elements sorted in ascending order.
- If you traverse in reverse order i.e. first visit the right subtree, then the root node and then the left subtree you can get the elements sorted in descending order.

Tree Sort Java program

To write a Java program for Tree sort you need-

A node class representing each node in the binary search tree.
A method to insert nodes in Binary search tree. Logic for inserting a new node to the Binary search tree goes as given below.
- If new node’s value is less than the current node move to the left.
- If new node’s value is greater than the current node move to the right.
- When current node is null that means leaf node is reached. New node should be inserted in that position.
A method to traverse the tree to get the elements in order.

class Node{
  int value;
  Node left;
  Node right;
  Node(int value){
    this.value = value;
    left = null;
    right = null;        
  }
}

class Tree{
  Node node;
  Tree(int value){
    node = new Node(value);
  }
  public Node insert(Node node, int value){
    if(node == null){
      return new Node(value);
    }
    // Move to the left if passed value is 
    // less than the current node
    if(value < node.value){
      node.left = insert(node.left, value);
    }
    // Move to the right if passed value is 
    // greater than the current node
    else if(value > node.value){
      node.right = insert(node.right, value);
    }
    return node;
  }
    
  // For traversing in order
  public void inOrder(Node node){
    if(node != null){
      inOrder(node.left);
      System.out.print(node.value + " ");
      inOrder(node.right);
    }
  }
    
  public void inOrderDesc(Node node){
    if(node != null){
      inOrderDesc(node.right);
      System.out.print(node.value + " ");
      inOrderDesc(node.left);
    }
  }
}

public class TreeSort {    
  public static void main(String[] args) {
    int[] arr = {50, 30, 70, 15, 7, 62, 22, 35, 87, 22, 31};
    System.out.println("Original array- "+Arrays.toString(arr));
    Tree tree = new Tree(arr[0]);
    for(int num : arr){
        tree.insert(tree.node, num);
    }
    System.out.println("Sorted Array (Ascending)- ");
    tree.inOrder(tree.node);
    System.out.println();
    System.out.println("Sorted Array (Descending)- ");
    tree.inOrderDesc(tree.node);
  }
}

Output

Original array- [50, 30, 70, 15, 7, 62, 22, 35, 87, 22, 31]
Sorted Array (Ascending)- 
7 15 22 30 31 35 50 62 70 87 
Sorted Array (Descending)- 
87 70 62 50 35 31 30 22 15 7

Performance of tree sort

Average case time complexity of tree sort is O(nlogn), as insertion of an element in the Binary search tree takes O(logn) time so for n elements it is O(nlogn).

Space complexity of tree sort is O(n) as we need to create n nodes for n elements.

That's all for this topic Tree Sort in Java Using Binary Search Tree. If you have any doubt or any suggestions to make please drop a comment. Thanks!

>>>Return to Java Programs Page

Related Topics

You may also like-

Saturday, April 23, 2022

Bucket Sort Program in Java

In this post we’ll see how to write Bucket sort program in Java. Bucket sort is one of the O(N) sorting algorithm like Radix sort and Counting sort. Since it runs in linear time (O(N)) so Bucket sort is faster than the comparison based algorithms like Merge Sort or Quick Sort.

Just like Counting sort, Bucket sort also makes some assumption about the input data beforehand like data should be uniformly distributed and should be with in a range.

How does Bucket sort work

Bucket sort works by assigning the input elements to different buckets and then sorting those buckets individually using any sorting technique like insertion sort so the elements in those buckets are sorted. After that merge the buckets to get the sorted output.

For distributing the elements to the buckets uniformly a good hash function is needed. The hash code given by hash function should also be an ordered hash such that if element i is greater than element j then hash(i) should also be greater than hash(j).

Let’s try to clarify working of bucket sort with an example where the elements in input array are with in the range 0..99- {47, 85, 10, 45, 16, 34, 67, 80, 34, 4, 0, 99}

Another array for buckets is needed. Let’s say we want that the elements having hash code 0-9 are put in bucket 0, 10-19 in bucket 1 ..... 90-99 in bucket 9 then we need an array of length 10 for buckets.

Since more than one element may be assigned to the same bucket so a list is needed at each index of the bucket array to store those elements.

With these requirement and the input array as shown above the structure should be as given below.

After sorting individual buckets you will have a structure as shown below.

Now starting from bucket 0 merge all the buckets to get the sorted output.

Bucket sort Java program

Following the steps for bucket sort as explained above you need to create a bucket array and assign a List (preferably linked list) to each array index.

List<Integer>[] buckets = new List[noOfBuckets];
// Associate a list with each index 
// in the bucket array         
for(int i = 0; i < noOfBuckets; i++){
    buckets[i] = new LinkedList<>();
}

Distribute input elements to the buckets as per the calculated hash.
Sort each bucket, for that sort() method of the Collections utility class is used in the program.
Merge buckets, you can use the input array itself as output (sorted array) while merging the buckets.
```
for(List<Integer> bucket : buckets){
  for(int num : bucket){
    intArr[i++] = num;
  }
}
```
Though outer and inner loops are used while merging but in the outer loop you are retrieving the list at each index and then iterating that list in the inner loop so effectively you are linearly traversing all the buckets which should take O(N) time.

Java code

public class BucketSort {
  public static void main(String[] args) {
    int[] intArr = {47, 85, 10, 45, 16, 34, 67, 80, 34, 4, 0, 99};
    //int[] intArr = {21,11,33,70,5,25,65,55};
    System.out.println("Original array- " + Arrays.toString(intArr));
    bucketSort(intArr, 10);
    System.out.println("Sorted array after bucket sort- " + Arrays.toString(intArr));
  }
    
  private static void bucketSort(int[] intArr, int noOfBuckets){
    // Create bucket array
    List<Integer>[] buckets = new List[noOfBuckets];
    // Associate a list with each index 
    // in the bucket array         
    for(int i = 0; i < noOfBuckets; i++){
      buckets[i] = new LinkedList<>();
    }
    // Assign numbers from array to the proper bucket
    // by using hashing function
    for(int num : intArr){
      //System.out.println("hash- " + hash(num));
      buckets[hash(num)].add(num);
    }
    // sort buckets
    for(List<Integer> bucket : buckets){
      Collections.sort(bucket);
    }
    int i = 0;
    // Merge buckets to get sorted array
    for(List<Integer> bucket : buckets){
      for(int num : bucket){
        intArr[i++] = num;
      }
    }
  }
    
  // A very simple hash function
  private static int hash(int num){
    return num/10;
  }
}

Output

Original array- [47, 85, 10, 45, 16, 34, 67, 80, 34, 4, 0, 99]
Sorted array after bucket sort- [0, 4, 10, 16, 34, 34, 45, 47, 67, 80, 85, 99]

Performance of Bucket Sort

Average time complexity of Bucket sort is considered O(n+k) where O(n) is the time spent in distributing elements across the buckets and sorting them and O(k) is the time spent in merging the buckets.

In worst case when most of the elements land in the same bucket time complexity is O(n²).

Space complexity of Bucket sort is O(n+k) as an auxiliary array of size k is needed for buckets. Each index of that bucket array holds reference to a list, total number of nodes in all those lists will be n making the total auxiliary space requirement as (n+k).

That's all for this topic Bucket Sort Program in Java. If you have any doubt or any suggestions to make please drop a comment. Thanks!

>>>Return to Java Programs Page

Related Topics

You may also like-

Monday, April 18, 2022

Counting Sort Program in Java

In this post we’ll see how to write counting sort program in Java. Counting sort is one of the O(N) sorting algorithm like Radix Sort and Bucket Sort. Since it runs in linear time (O(N)) so counting sort is faster than the comparison based algorithms like merge sort and quick sort.

Though counting sort is one of the fastest sorting algorithm but it has certain drawbacks too. One of them is that the range of elements should be known beforehand. Counting sort also needs auxiliary space as it needs to store the frequency of elements.

How does counting sort work

Counting sort works by counting the frequency of each element to create a frequency array or count array. Then these counts are used to compute the index of an element in the sorted array.

Create a count array to store the count of each element. If the range of elements is 0 to k then count array should be of length k+1. For example if max element in the array is 15 then count array should be of length 16.
Iterate through the elements in input array and for each element increment its count in the corresponding index in the count array.
For example if input array is- [0, 4, 2, 6, 5, 4, 8, 9, 8, 6]

Then the count array would be like below-
Modify the count array so that each index stores the sum of element at current index + element at previous index.
Now using this modified count array you need to construct the sorted array. For that you take an element from the input array and go to that index in the modified count array to get a value. That value is the place, of the element picked from the input array, in the sorted array.
In the count array decrement the value by 1 too.
For example if input array and modified count array are as follows-

First element in the input array is 0, so consult the 0th index in the count array which is 1. That means 0 goes at the place 1 (i.e. index 0) in the sorted array. Decrement the value in the count array too. In this step value at index 0 in the count array will be decremented by 1 so that it becomes 0.

Second element in the input array is 4, so consult the 4th index in the count array which is 4. That means 4 goes at the place 4 (i.e. index 3) in the sorted array. With in input array an element may be repeated and those should be grouped together. For that we need to decrement the value in the count array. In this step value at index 4 in the count array will be decremented by 1 so that it becomes 3.

When the next 4 is encountered in the input array value at the 4th index in the count array will be 3. That means next 4 goes at the place 3 (i.e. index 2) in the sorted array.

Counting Sort Java program

public class CountingSort {

  public static void main(String[] args) {
    int[] arr = {0, 4, 2, 6, 5, 4, 8, 9, 8, 6};
    // max element + 1
    int range = 10;
    System.out.println("Original Array- " + Arrays.toString(arr));
    arr = countingSort(arr, range);
    System.out.println("Sorted array after counting sort- " + Arrays.toString(arr));
  }
    
  private static int[] countingSort(int[] arr, int range){
    int[] output = new int[arr.length];
    int[] count = new int[range];
    //count number of times each element appear
    for(int i = 0; i < arr.length; i++){
      count[arr[i]]++;
    }
    System.out.println("Count array- " + Arrays.toString(count));
    // each element stores (sum of element at current index 
    //+ element at previous index)
    for(int i = 1; i < range; i++){
      count[i] = count[i] + count[i-1];
    }
    System.out.println("Modified count- " + Arrays.toString(count));
    for(int i = 0; i < arr.length; i++){
      output[count[arr[i]] - 1] = arr[i];
      count[arr[i]]--;
    }
    return output;
  }
}

Output

Original Array- [0, 4, 2, 6, 5, 4, 8, 9, 8, 6]
Count array- [1, 0, 1, 0, 2, 1, 2, 0, 2, 1]
Modified count- [1, 1, 2, 2, 4, 5, 7, 7, 9, 10]
Sorted array after counting sort- [0, 2, 4, 4, 5, 6, 6, 8, 8, 9]

Performance of Counting Sort

If the number of elements to be sorted is n and the range of elements is 0-k then the time complexity of Counting sort can be calculated as-

Loop to create count array takes O(n) time. Second loop where count array is modified takes O(k) time and creating sorted output array again takes O(n) time. Thus the time complexity with all these combined comes as O(2n+k). Since constants are not taken into consideration so the time complexity of Counting sort is O(n+k).

Auxiliary space requirement is also (n+k). Count array takes k space and the output array n. Thus the space complexity of Counting sort is O(n+k).

That's all for this topic Counting Sort Program in Java. If you have any doubt or any suggestions to make please drop a comment. Thanks!

>>>Return to Java Programs Page

Related Topics

You may also like-

Saturday, April 9, 2022

Quick Sort Program in Java

In this post we’ll see how to write quick sort program in Java. Quick sort is considered the fastest in-memory sorting technique in most of the situations. Just like Merge sort, Quick sort is also a divide and conquer algorithm which works on the idea of partitioning the large list into smaller lists around a chosen value (pivot) so that all the smaller values than the pivot are on the left and all the higher values than the pivot are on the right. Quick sort then recursively sort the list with smaller values and the list with higher values by further partitioning it around pivot.

How does quick sort work

Steps for implementing the quick sort are as follows-

Chose a pivot value (it must be one of the element from the list that is sorted).
Partition the list in such a way that all the elements having value less than the pivot come before the pivot (smaller element list) and all the elements having value higher than the pivot come after the pivot (higher element list). Once this partitioning is done pivot value is at its final position.
Recursively call the above steps separately for the smaller element list and for the higher element list.

You can pick any random value as the pivot while implementing quick sort-

First element in the list as pivot.
Last element in the list as pivot (Quick sort implementation given here uses this approach)
Middle element as pivot.
Median of the items being sorted.

Quick Sort Java program

First let’s see the Java program for quick sort and then we’ll try to understand what is happening with the help of the program code.

public class QuickSort {
  public static void main(String[] args) {
    int[] numberArr = {47, 65, 52, 10, 43, 67, 80, 34, 55, 48};
    QuickSort qs = new QuickSort();
    qs.quickSortRecursive(numberArr, 0, numberArr.length-1);
    System.out.println("Sorted array after quick sort- ");
    for(int num : numberArr){
      System.out.print(num + " ");
    }
  }
    
  private void quickSortRecursive(int[] numberArr, int lower, int upper){
    if(upper - lower <= 0){
      return;
    }else{
      int partition = partition(numberArr, lower, upper);
      // calling method again with smaller values
      quickSortRecursive(numberArr, lower, partition-1);
      // calling method again with higher values
      quickSortRecursive(numberArr, partition+1, upper);
    }
  }
    
  private int partition(int[] numberArr, int lower, int upper){
    int pivot = numberArr[upper];
    int left = lower - 1;
    int right = upper;
    while(true){
      // find an element greater than pivot 
      // starting from the beginning
      while(numberArr[++left] < pivot);
      // find an element smaller than pivot
      // starting from the end
      while(right > 0 && numberArr[--right] > pivot);
      if(left >= right){
        break;
      }else{
        swap(numberArr, left, right);
      }
    }
    swap(numberArr, left, upper);
    return left;
  }
    
  private void swap(int[] numberArr, int i, int j){
    int temp = numberArr[i];
    numberArr[i] = numberArr[j];
    numberArr[j] = temp;
  }
}

Output

Sorted array after quick sort- 
10 34 43 47 48 52 55 65 67 80

Understanding the quick sort program

In the program there is a quickSortRecursive method which is called recursively with the two arrays; one containing the elements smaller than the pivot and another containing the elements greater than the pivot. For partitioning the elements there is a partition method.

Initially when the partitioning starts array is as depicted in the given image.

For the swapping of the elements we’ll start at both ends of the array. From the left move towards right looking for an element greater than pivot value. From the right move towards left looking for an element smaller than pivot.

These while loops are doing it in the code.

while(numberArr[++left] < pivot);


while(right > 0 && numberArr[--right] > pivot);

If you find such numbers before the break condition (left >= right) you swap those elements so that smaller numbers are on one side of the pivot and greater on the other side.

From the array you can see that starting from the left 65 > 48 and from the right 34 < 48 so these numbers are swapped. Continuing from the next index at the left side 52 > 48 and from the right 43 < 48 so these numbers are swapped. At this point your array would look like as given below, with left index at 43 and right at 52-

47 34 43 10 52 67 80 65 55 48

From here continuing from the next index at the left side again 52 > 48 and from the right 10 < 48 but at this point (left >= right) so control comes out of the loop and swapping for the pivot is done.

swap(numberArr, left, upper);

Swap the value at left index with the pivot value which brings pivot at its final position and gives two sub arrays.

Then the same process is repeated with the two sub-arrays.

Performance of quick sort

Average time complexity of quick sort is O(N*logN). In worst case it can be O(N²).

Every recursive call will have its own stack space so space complexity of quick sort is O(N).

That's all for this topic Quick Sort Program in Java. If you have any doubt or any suggestions to make please drop a comment. Thanks!

>>>Return to Java Programs Page

Related Topics

You may also like-

Tuesday, March 15, 2022

Heap Sort Program in Java

In this post we’ll see how to write Heap sort program in Java. Heap sorting is done using the heap data structure so it is important that you know about heap and how to implement a heap data structure before going to heap sort program.

Table of contents

Heap data structure
Types of heap
Heap data structure creation in program
Creating heap from tree
Steps for heap sort
Heap sort Java program
Performance of heap sort

Heap data structure

Heap is a tree based data structure consisting of nodes and edges. Nodes represent the values stored in the data structure and edges (lines) connect the nodes. To get from one node to another you will follow the path along these edges. Following figure shows a conceptual representation of a tree structure.

Heap data structure is represented as a binary tree; binary tree is a tree where each node can have maximum of two children. Head data structure is a complete binary tree meaning it is filled in. Last node may not be full (may not have both children) where as in full binary tree each parent node has both children.

Types of heap

There are two representations of heap structure-

Max heap
Min heap

Max heap- In max heap value of parent node is greater than the values of its child nodes. So root node is always the maximum element.

Min heap- In min heap value of parent node is smaller than the values of its child nodes. So root node is always the smallest element.

Heap data structure creation in program

Heap data structure is usually represented by an array. When you have an array with its elements it is considered as a complete binary tree. Following figure shows the conceptual representation of a complete binary tree along with the array indexes for the array - {3 10 1 14 6 8}

When a tree is represented as an array you can find the parent or children of any node using the following equations.

For a node at index i in the array-

Parent node is – (i-1)/2
Left child node is- 2*i + 1
Right child node is- 2*i+2 (or left child +1)

You will use these equations in your program to traverse to children of a node or to traverse to a parent.

Creating heap from tree

This complete binary tree structure has to be transformed to a heap data structure so that every parent node value is greater than its child node values (in case of max heap). The process is commonly known as “heapify”.

In order to create a heap we’ll have to start from the nodes at the bottom and move upwards comparing if child node is greater than the parent and swapping values if that is the case. For this comparison we don’t need to start from the bottom most leaf nodes (nodes with no children) as these nodes are considered to be correct heaps.

Since last node will be at position (n-1) for an array of length n so it’s parent node should be at index (n-1)/2 as per the equation. That is the index from where process of heapifying the array will start, in each iteration compare the parent node with left child and right child and swap the nodes if child is greater than the parent.

For example if we take the binary tree for the array {3 10 1 14 6 8}

Here last index is 5, which means last node is at that index. Thus the parent node should be at index (5-1)/2 = 2. From that index process starts.

In the next iteration for n=1, 10 is compared with its left and right children. Since (14 > 10) so a swap is required. Same way for n=0 again values will be swapped.

heapify method that is used for creating a heap structure (max heap) written in Java is as follows-

private void heapify(int[] numArr, int index, int i){
  // Getting parent and children indexes
  int rootIndex = i;
  int lc = 2*i + 1;
  int rc = 2*i + 2;
    
  //comparing left child value
  if(lc < index && numArr[lc] > numArr[rootIndex])
    rootIndex = lc;
  //comparing right child value
  if(rc < index && numArr[rc] > numArr[rootIndex])
    rootIndex = rc;
  // if change required then swap values and call method recursively
  if(rootIndex != i){
    swap(numArr, rootIndex, i);
    heapify(numArr, index, rootIndex);
  }
}

Steps for heap sort

Now when you know about heap data structure and how to create a heap from a given array it is easy to understand the heap sort.

In a max heap root element is always the greatest element of the array, that property of the heap is used in heap sort. Steps for heap sort are as follows-

Heapify the array to get a heap structure.
Swap the root element with the last element (Swap index 0 with index (n-1)).
Heapify the array again without taking the last element as last element is already at its proper place. So array used now is from index 0 to index (array length -1). Once heap is created using this array largest element of this array will be the root of the heap. Repeat from step 2.

Heap sort Java program

public class HeapSort {

  public static void main(String[] args) {
    HeapSort hs = new HeapSort();
    int[] numArr = {3,10,1,14,6,8};
    //int[] numArr = {47, 85, 620, 3456, -7, 10, 4500, 106, -345, 1000, 67, 80, 5500, 34, 78, 782, 4, 0, 99, 190};
    //int[] numArr = {0, 21, 5, 1, 0, 2, 10, 15, 7, 5};
    hs.sort(numArr);
    System.out.println("Sorted array- " + Arrays.toString(numArr));
  }
    
  private void sort(int[] numArr){
    int arrLength = numArr.length;
    // create heap
    for(int i = (arrLength-1)/2; i >=0; i--){
      heapify(numArr, arrLength, i);
    }
    System.out.println("heapified array- " + Arrays.toString(numArr));
    // Sorting process
    // in the loop keep reducing the array that is used for creating heap
    for(int i = arrLength-1; i >= 0; i--){
      // Swap root and last nodes
      swap(numArr, i, 0);
      // build heap again
      heapify(numArr, i, 0);
    }
  }
    
  private void heapify(int[] numArr, int index, int i){
    // Getting parent and children indexes
    int rootIndex = i;
    int lc = 2*i + 1;
    int rc = 2*i + 2;
    //comparing left child value
    if(lc < index && numArr[lc] > numArr[rootIndex])
        rootIndex = lc;
    //comparing right child value
    if(rc < index && numArr[rc] > numArr[rootIndex])
        rootIndex = rc;
    // if change required then swap values and call method recursively
    if(rootIndex != i){
      swap(numArr, rootIndex, i);
      heapify(numArr, index, rootIndex);
    }
  }
    
  private void swap(int[] numArr, int index, int li){
    int temp = numArr[li];
    numArr[li] = numArr[index];
    numArr[index] = temp;
  }
}

Output

heapified array- [14, 10, 8, 3, 6, 1]
Sorted array- [1, 3, 6, 8, 10, 14]

Performance of heap sort

The height of a complete binary tree of n nodes is considered as log(n+1). In heap sort while building a heap comparison and swapping may be required at each level. Since heap building process is done for n/2 elements thus the time complexity of heap sort can be calculated as n/2*log(n+1). Thus in Big-O notation time complexity of heap sort is O(N*logN).

Heap sort may be slightly slower than quick sort in some scenarios but worst case scenario for quick sort is O(N²) where as for heap sort time complexity is O(N*logN) for best, average and worst case.

Since same array is used for building heap and for heap sorting so no auxiliary space is required making the space complexity of heap sort as O(1).

That's all for this topic Heap Sort Program in Java. If you have any doubt or any suggestions to make please drop a comment. Thanks!

>>>Return to Java Programs Page

Related Topics

You may also like-

Saturday, January 29, 2022

Merge Sort Program in Java

In this post we’ll see how to write Merge sort program in Java. Merge sort is much more efficient than the simple sort algorithms like bubble sort and insertion sort. One drawback is that it requires an additional array along with the original array that is sorted.

How merge sort works

Merge sort works on the concept of merging two sorted arrays to create another array which is also sorted.

Now the question is how do you get sorted arrays which are merged? Since merge sort is also termed as divide and conquer algorithm so the idea is to divide the input array into two halves then each of these halves are further divided into halves and so on until you get sub-arrays with only one element which is considered a sorted array.

At that point you start merging these sub-arrays, from two single element sub-arrays you create a sorted merged array of two elements. Then two such sorted sub-arrays of two elements are merged to create a sorted array of four elements and so on until you have a sorted array of all the elements.

Since array is recursively divided into two halves so this division process can be written as a recursive method where base case becomes the point when you have sub-arrays with only one element each.

Let’s try to understand with an example where we have an input array as given below.

int[] intArr = {21, 11, 33, 70, 5, 25, 65, 55};

The process of recursive calls to divide the array into halves can be explained using the following image.

At this point merge process starts which merges two sorted arrays to create another sorted array, this merging process can be explained using the following image.

Merge Sort Java program

In the merge sort program there is a method mergeSortRecursive which is called recursively to divide the array.

Merge method merges the two sub-arrays to create a sorted array.

public class MergeSort {
  public static void main(String[] args) {
    int[] intArr = {47, 85, 620, 3456, -7, 10, 4500, 106, -345, 1000, 67, 80, 5500, 34, 78, 782, 4, 0, 99, 190};
    MergeSort ms = new MergeSort();
    ms.mergeSortRecursive(intArr, 0, intArr.length-1);
    System.out.println("Sorted array after merge sort- ");
    for(int num : intArr){
      System.out.print(num + " ");
    }
  }
    
  private void mergeSortRecursive(int[] intArr, int lower, int upper){
    //base case
    if (lower == upper){
      return;
    }else{
      // get mid point for division of array
      int middle = (lower + upper)/2;
      
      mergeSortRecursive(intArr, lower, middle);        
      mergeSortRecursive(intArr, middle+1, upper);
      
      merge(intArr, lower, middle, upper);
    }
  }
    
  private void merge(int[] intArr, int lower, int middle, int upper){
      /** Create two temp arrays pertaining to two halves that 
       are being merged and add elements to them  */
      int subArrayOneLength = middle - lower + 1;
      int subArrayTwoLength = upper - middle;
      int[] temp1 = new int[subArrayOneLength];
      int[] temp2 = new int[subArrayTwoLength];
      for(int i = 0; i < subArrayOneLength; i++){
        temp1[i] = intArr[lower + i];
      }
      for(int j = 0; j < subArrayTwoLength; j++){
        temp2[j] = intArr[middle + 1 + j];
      }           
      int i =0;        
      int j = 0;
      // merging process, merge two temp arrays 
      while((i < subArrayOneLength) && (j < subArrayTwoLength)){
        if(temp1[i] < temp2[j]){
          intArr[lower] = temp1[i++];
        }else{
          intArr[lower] = temp2[j++];
        }
        lower++;
      }
      // If there are more elements
      while(i < subArrayOneLength){
        intArr[lower++] = temp1[i++];
      }
      while(j < subArrayTwoLength){
        intArr[lower++] = temp2[j++];
      }
  }
}

Output

Sorted array after merge sort- 
-345 -7 0 4 10 34 47 67 78 80 85 99 106 190 620 782 1000 3456 4500 5500

Performance of merge sort

In merge sort there is subdivision of arrays and for each sub-division there is merging. Number of levels (subdivisions of array) can be calculated as– (logN + 1)

For example log of 8 base 2 is 3, so log8 + 1 = 4

Which is same as the number of halves for the array having 8 elements– 8 4 2 1.

At each level N elements are merged which makes the time complexity of merge sort as N*(logN + 1). we can discard the 1 so the time complexity of merge sort is O(N*logN).

Merge sort is not an in place sort algorithm as extra space is required. Auxiliary space required is equal to the number of elements in the original array so the space complexity of merge sort is O(N).

That's all for this topic Merge Sort Program in Java. If you have any doubt or any suggestions to make please drop a comment. Thanks!

>>>Return to Java Programs Page

Related Topics

You may also like-

Saturday, January 15, 2022

Shell Sort Program in Java

In this post we’ll see how to write Shell sort program in Java.

Shell sort is based on another sorting algorithm insertion sort and it is developed by Donald L. Shell.

Shell sort – An improvement on insertion sort

In insertion sort the adjacent elements are compared and a swap is done if required (if item on the right is smaller than the item on the left). That way elements are shifted right to move smaller elements to the left.

Consider a scenario where a smaller element is on the far right, lot of shifting has to be done to move this element to its proper place on the left.

In shell sort rather than comparing adjacent elements, elements that are placed some distance from each other are compared and swapped. You start with a gap value and elements at that gap interval are compared. After each iteration gap value is decremented so that the interval is reduced, that is done until the gap value is 1 that is when adjacent elements are compared and shell sort effectively becomes insertion sort in that iteration.

The benefit is that by the last step, when the adjacent elements are compared, elements are almost sorted and no far off shifting of elements is required. For almost sorted elements insertion sort has the complexity of O(N) rather than O(N²).

Shell sort interval sequence calculation

The interval that is used for comparing elements is based on the number of elements. For the calculation of that interval Knuth’s interval sequence is used where the interval sequence is generated using the following formula-

gap = gap*3 + 1

When gap = 1 it gives interval value as 4, for gap =4 interval value as 13 and so on.

For example if you have an array of 20 elements the calculation for the initial interval value is done as follows in the Java program-

while(gap <= arr.length/3){
    gap = (gap * 3) + 1;
}

For decrementing the interval following formula is used-

gap = (gap-1)/3

For example, When gap = 13 then the next interval sequence value will be (13-1)/3 = 4

Shell Sort Java program

public class ShellSort {
  public static void main(String[] args) {
    // Array of 20 elements
    int[] intArr = {47, 85, 620, 3456, 7, 10, 4500, 106, 345, 
          1000, 67, 80, 5500, 34, 78, 782, 4, 0, 99, 190};
    int[] sortedArray = shellSort(intArr);
    System.out.println("Sorted array is- ");
    for(int num : sortedArray){
      System.out.print(num + " ");
    }
  }

  private static int[] shellSort(int[] intArr){
    int gap = 1;
    int temp;
    // initial gap value calculation
    while(gap <= intArr.length/3){
      gap = (gap * 3) + 1;
    }
    while(gap > 0){    
      for(int i = gap; i < intArr.length; i++){
        temp = intArr[i];
        int j;                
        for(j = i; j > gap - 1 && intArr[j-gap] >= temp; j=j-gap){
            intArr[j] = intArr[j - gap];                    
        }
        intArr[j] = temp;
      }
      // next gap value calculation
      gap = (gap - 1)/3;
    }
    return intArr;
  }
}

Output

Sorted array is- 
0 4 7 10 34 47 67 78 80 85 99 106 190 345 620 782 1000 3456 4500 5500

Shell Sort Explained

In the Java program for shell sort, since the array length is 20 so the initial gap value is calculated as 13. With that interval here are some values from the inner and outer loops.

In the first iteration value at index 13 is compared with index 0 and swapped too. Then the outer loop value is incremented by 1 (i = 14) at that time value at index 14 is compared with index 1 and swapped too. Same way iteration will happen until the length of the array is reached ( i = 19).

i -- 13
j-- 13 j-gap= 0
 array after inner loop ---- 
34 85 620 3456 7 10 4500 106 345 1000 67 80 5500 47 78 782 4 0 99 190 
i -- 14
j-- 14 j-gap= 1
 array after inner loop ---- 
34 78 620 3456 7 10 4500 106 345 1000 67 80 5500 47 85 782 4 0 99 190 
...
...
i -- 19
j-- 19 j-gap= 6

That’s the array after the iteration is done with gap value as 13.

34 78 620 4 0 10 190 106 345 1000 67 80 5500 47 85 782 3456 7 99 4500

Then the gap value is reduced as per the formula and the new gap value is 4. With that again the comparison is done.

i -- 4
j-- 4 j-gap= 0
 array after inner loop ---- 
0 78 620 4 34 10 190 106 345 1000 67 80 5500 47 85 782 3456 7 99 4500 

i -- 5
j-- 5 j-gap= 1
 array after inner loop ---- 
0 10 620 4 34 78 190 106 345 1000 67 80 5500 47 85 782 3456 7 99 4500 

..
..

i -- 17
j-- 17 j-gap= 13
j-- 13 j-gap= 9
j-- 9 j-gap= 5
j-- 5 j-gap= 1
 array after inner loop ---- 
0 7 67 4 34 10 85 80 345 47 190 106 3456 78 620 782 5500 1000 99 4500 
i -- 18
j-- 18 j-gap= 14
j-- 14 j-gap= 10
 array after inner loop ---- 
0 7 67 4 34 10 85 80 345 47 99 106 3456 78 190 782 5500 1000 620 4500 

i – 19

That’s the array after the iteration is done with gap value as 4.

0 7 67 4 34 10 85 80 345 47 99 106 3456 78 190 782 5500 1000 620 4500

Then the gap value is reduced again and it becomes 1. With value as 1 the sorting happens as in insertion sort giving the final sorted array.

Time and space complexity of shell sort

There are various estimates for the time complexity of shell sort based on the interval sequence used and the data used for sorting. But generally the time complexity of shell sort is considered O(N^3/2) which means square root of (N)³.

Since shell sort is an in-place comparison sort so no extra space is required thus the space complexity of Shell sort is O(1).

That's all for this topic Shell Sort Program in Java. If you have any doubt or any suggestions to make please drop a comment. Thanks!

>>>Return to Java Programs Page

Related Topics

You may also like-

Thursday, January 13, 2022

Selection Sort Program in Java

In this post we’ll see how to write Selection sort program in Java. Selection sort is considered a step ahead of bubble sort as the number of swaps is lesser though the comparison are still proportional to N².

How selection sort works

In selection sort aim is to bring the lowest element to the 0th index in the first pass. In the next iteration the second lowest to the 1st index and so on.

You start with the element at the 0th index and consider it the lowest. Then compare it with the other elements, if any element is smaller than the first element then that element becomes the lowest for further comparisons in that pass. That way you have the lowest element at the end of the iteration it is then swapped with the element at the 0th index.

Same way in the next iteration you start with the element at the 1st index and consider it the second lowest element. Then compare it with all the elements on its right, in between if any element smaller than this element is found then further comparisons are done using the now smallest element.

For example if you have an array [5, 2, 6, 1] then in the first iteration-

Initially you will start with 5 (element at 0th index) and compare it with elements on its right. Since 2 is smaller than 5 so now 2 is considered the lowest.
Then 2 is compared with 6. Still 2 is the lowest.
Then 2 is compared with 1, since 1 is smaller so it is now the lowest element and the end of the array is also reached. Swap 1 with 5 so after the first iteration array is [1, 2, 6, 5].

In the next iteration you will start with 2 (element at the 1st index) and compare it with elements on its right using the same logic for sorting.

Selection Sort Java program

Logic for writing the selection sort Java program is as follows-

There are two for loops, the outer loop starts from the leftmost element and goes till the one less than the number of elements in the array.

The inner loop starts at the index one more than the current index of the outer loop and goes till the end of the array.

With in the inner loop elements are compared with the element currently pointed by the outer loop to get the lowest element with in that iteration. Once the element is found it is swapped with the element at the current index of the outer loop.

public class SelectionSort {
  public static void main(String[] args) {
    int[] numArray = {47, 85, 620, 3456, 7, 10, 4500, 106, 345, 1000};
    int[] sortedArray = selectionSort(numArray);
    System.out.println("Sorted array is- ");
    for(int num : sortedArray){
      System.out.print(num + " ");
    }
  }
  private static int[] selectionSort(int[] numArray){
    int lowest;
    for(int i = 0; i < numArray.length - 1; i++){
      lowest = i;
      for(int j = i+1; j < numArray.length; j++){
        //if smaller then this is considered the smallest
        if(numArray[j] < numArray[lowest]){
          lowest = j;
        }
      }
      swapElements(i, lowest, numArray);
    }
    return numArray;
  }
    
  private static void swapElements(int index, int lowest, int[] numArray){
    int temp = numArray[index];
    numArray[index] = numArray[lowest];
    numArray[lowest] = temp;
    // Uncomment it to see the element movement in each iteration    
    /*for(int num : numArray){
      System.out.print(num + " ");
    }
    System.out.println("");*/
  }
}

Output

Sorted array is- 
7 10 47 85 106 345 620 1000 3456 4500

Time and space complexity of Selection sort

For selection sort there are two loops that go through the elements that makes it a complexity of N*N i.e. time complexity of Selection sort is O(N²) where total number of comparisons are N*(N-1)/2.

In selection sort the number of swaps are less in comparison to the bubble sort making it faster than the bubble sort.

Selection sort is an in place sorting algorithm so apart from the initial array there is no auxiliary space requirement thus the space complexity of Selection sort is O(1), total space can be considered as O(N).

That's all for this topic Selection Sort Java Program. If you have any doubt or any suggestions to make please drop a comment. Thanks!

>>>Return to Java Programs Page

Related Topics

You may also like-