Tag: java sorting program

In this tutorial, we will learn how to implement Shell Sort in java. First, we will start by understanding the Shell Sort algorithm.

• Sorting Algorithms in Java

Shell Sort Algorithm

Shell sort is an in-place comparison-based sorting algorithm and variation of Insertion sort. It is a better version of Insertion sort in comparison-based. It can compare the elements far apart whereas Insertion compares adjacent elements.

In shell sort, we make the array h-sorted for a large value of h. We keep reducing the value of h until it becomes 1. An array is said to be h-sorted if all sublists of every h’th element are sorted.

Time Complexity of Shell Sort:

• Best case:  0(nlogn)
• Average case:  0(n(logn)^2)
• Worst case:  0(n(logn)^2)

Before we begin, you need to have an idea of the following:

• Methods in java
• for loop in java
• while loop in java

---

Implementation of Shell sort in java

import java.util.Arrays;

public class ShellSortJava
{
  public static void main(String[] args)
  {
    int[] arr = { 23, 12, 89, 145, 10, 8, 333, 1, 70, 67 };

    System.out.println("Array Before Sorting : ");
    System.out.println(Arrays.toString(arr));

    System.out.println("Array After Shell Sorting : ");
    arr = shellsort(arr);
    System.out.println(Arrays.toString(arr));
  }

  private static int[] shellsort(int[] array)
  {
    int h = 1;
    while (h <= array.length / 3)
    {
      h = 3 *h + 1;	//h<=length/3
    }

    while (h > 0)
    {
      // similar to insertion
      for (int i = 0; i < array.length; i++)
      {
        int temp = array[i];
        int j;

        for (j = i; j > h - 1 && array[j - h] >= temp; j = j - h)
        {
          array[j] = array[j - h];
        }

        array[j] = temp;
      }

      h = (h - 1) / 3;
    }

    return array;
  }
}

The output of shell Sort Algorithm in java:

---

In this tutorial, we will learn how to implement Bubble Sort in java. First, we will start by understanding the Bubble Sort algorithm.

• Sorting Algorithms in Java

Bubble Sort Algorithm

Bubble sorting is the simplest sorting algorithm that works by comparing two adjacent elements in an array and swapping them if found in the wrong order.

Bubble sort compares the first element with the next one and if found in the wrong order then that compared element in an array are swapped. This algorithm traverse through the entire element in an array.

Time Complexity of Bubble Sort:

• Best case:  O(n)
• Average case:  O(n^2)
• Worst case:  O(n^2)

Bubble Sort in Java program:

We will see the two examples on Bubble sorting in java, one defining the elements in the program and another by taking user input.

Before we begin, you need to have an idea on following:

• for loop in java
• if Statement in java

---

1. Defining the elements in a program.

public class BubbleSortExample
{
  static void bubbleSort(int[] arr)
  {
    int n = arr.length;
    int temp = 0;
    for (int i = 0; i < n; i++)
    {
      for (int j = 1; j < (n - i); j++)
      {
        if (arr[j - 1] > arr[j])
        {
          //swap elements  
          temp = arr[j - 1];
          arr[j - 1] = arr[j];
          arr[j] = temp;
        }
      }
    }
  }

  public static void main(String[] args)
  {
    //Defining array elements
    int arr[] = { 4, 76, 34, 2, 132, 16, 1 };

    System.out.println("Order of elements before Bubble Sort");
    for (int i = 0; i < arr.length; i++)
    {
      System.out.print(arr[i] + " ");
    }

    System.out.println();

   //sorting array 
    bubbleSort(arr);

    System.out.println("Order of elements after Bubble Sort");
    for (int i = 0; i < arr.length; i++)
    {
      System.out.print(arr[i] + " ");
    }
  }
}

The Output of Bubble Sort in Java.

---

2. By User-Input.

import java.util.Scanner;

public class BubbleSortExample
{
  static void bubbleSort(int[] arr)
  {
    int n = arr.length;
    int temp = 0;
    for (int i = 0; i < n; i++)
    {
      for (int j = 1; j < (n - i); j++)
      {
        if (arr[j - 1] > arr[j])
        {
          //swap elements  
          temp = arr[j - 1];
          arr[j - 1] = arr[j];
          arr[j] = temp;
        }
      }
    }
  }

  public static void main(String[] args)
  {
    int n, c;
    Scanner in = new Scanner(System.in);

    System.out.println("Enter the no. of elements to be sorted");
    n = in .nextInt();

    int arr[] = new int[n];
    System.out.println("Enter " + n + " integers");
    for (c = 0; c < n; c++)
      arr[c] = in .nextInt();

    System.out.println("Order of elements before Bubble Sort");
    for (int i = 0; i < arr.length; i++)
    {
      System.out.print(arr[i] + " ");
    }

    System.out.println();

   //sorting array 
    bubbleSort(arr);

    System.out.println("Order of elements after Bubble Sort");
    for (int i = 0; i < arr.length; i++)
    {
      System.out.print(arr[i] + " ");
    }
  }
}

The Output of the Bubble sorting algorithm in java.

---

In this tutorial, we will learn how to implement Merge Sort in java. First, we will start by understanding the Merge Sort algorithm.

• Sorting Algorithms in Java

Merge Sort Algorithm

Merge Sort is another sorting algorithm that follows a Divide and Conquer algorithm approach to sort the elements in an array in ascending or descending order.

It divides the array into two halves and sorts them separately. Again the two halves are divided into separate two halves and the process keeps on going until the elements are totally separated. After that, the elements are combined together in the same steps as they were separated but while combining the elements are sorted in each steps.

When the combining step is completed we will get a fully sorted array.

Before we begin, you need to have an idea on following:

• Methods in java
• if statement in java
• while loop in java

Time Complexity of Merge Sort:

• Best case:  0(n log n)
• Average case:  0(n log n)
• Worst case:  0(n log n)

---

Implementation of Merge sort in java

import java.util.Arrays;

public class Main
{
  public static void main(String[] args)
  {
    int[] inputArr = { 45, 87, 11, 5, 80, 9, 02, 560, 33, 99, 1 };
    System.out.println("Array before sorting: ");
    System.out.println(Arrays.toString(inputArr));

    mergesort(inputArr);

    System.out.println("Array after merge sorting: ");
    System.out.println(Arrays.toString(inputArr));
  }

  public static void mergesort(int[] inputArr)
  {
    mergesort(inputArr, 0, inputArr.length - 1);
  }

  private static void mergesort(int[] inputArr, int start, int end)
  {
    int mid = (start + end) / 2;
    if (start < end)
    {
      mergesort(inputArr, start, mid);
      mergesort(inputArr, mid + 1, end);
    }

    int i = 0, first = start, last = mid + 1;
    int[] tmp = new int[end - start + 1];
    while (first <= mid && last <= end)
    {
      tmp[i++] = inputArr[first] < inputArr[last] ? inputArr[first++] : inputArr[last++];
    }
    while (first <= mid)
    {
      tmp[i++] = inputArr[first++];
    }
    while (last <= end)
    {
      tmp[i++] = inputArr[last++];
    }
    i = 0;
    while (start <= end)
    {
      inputArr[start++] = tmp[i++];
    }
  }
}

The output of Merge Sort Algorithm in java:

---

In this post, we will learn how to implement Quick Sort in java. First, we will start by understanding the Quick Sort algorithm.

• Sorting Algorithms in Java

Quick Sort Algorithm

Quicksort algorithm is a way of rearranging the elements in an array in ascending or descending order. Quicksort is another Divide and Conquer algorithm.

It takes two empty arrays to hold elements, the first is less than the pivot value and the second element greater than the pivot value, and then sort the element around it or inside it. It involves Swapping and partitioning a section of the array.

Time Complexity of Quick Sort:

• Best case:  0(n log n)
• Average case:  0(n log n)
• Worst case:  0(n^2)

---

Implementation of Quick sort in java

import java.util.Arrays;

public class QuickSort
{
  private static int array[];

  public static void Qsort(int[] arr)
  {
    if (arr == null || arr.length == 0)
    {
      return;
    }

    array = arr;

    quickSort(0, array.length - 1);
  }

  private static void quickSort(int left, int right)
  {
    int i = left;
    int j = right;

    // finding pivot number
    int pivot = array[left + (right - left) / 2];

    while (i <= j)
    {
      //Find element greater than pivot
      while (array[i] < pivot)
      {
        i++;
      }

      while (array[j] > pivot)
      {
        j--;
      }

      if (i <= j)
      {
        exchange(i, j);
        i++;
        j--;
      }
    }

    // recursssive
    if (left < j)
      quickSort(left, j);
    if (i < right)
      quickSort(i, right);
  }

  private static void exchange(int i, int j)
  {
    int temp = array[i];
    array[i] = array[j];
    array[j] = temp;
  }

  public static void main(String a[])
  {
    int[] arr = { 56, 33, 90, 2, 22, 4, 1, 8, 16, 9, 20 };

    System.out.println("Array Before Sorting : ");
    System.out.println(Arrays.toString(arr));

    Qsort(arr);

    System.out.println("Array After Sorting : ");
    System.out.println(Arrays.toString(array));

  }
}

The output of Quicksort algorithm in java:

---

In this tutorial, we will learn how to implement Insertion Sort in java. First, we will start by understanding the Insertion Sort algorithm.

• Sorting Algorithms in Java

Insertion Sort Algorithm

Insertion sort is a simple sorting algorithm that sorts the elements in an array by comparing the values at index with all its prior elements. This process takes more time so it is only used for small data set.

This sorting takes the first index element and compares it to its largest value in an array and it moves the element to its right location.

Before we begin, you need to have an idea of the following:

• Methods in java
• for loop in java
• while loop in java

Time Complexity of Heap Sort:

• Best case:  0(n)
• Average case:  0(n^2)
• Worst case:  0(n^2)

---

Implementation of Insertion Sort in java

public class InsertionSortJava
{
  public static void insertionSort(int array[])
  {
    int n = array.length;
    for (int j = 1; j < n; j++)
    {
      int key = array[j];
      int i = j - 1;
      while ((i > -1) && (array[i] > key))
      {
        array[i + 1] = array[i];
        i--;
      }

      array[i + 1] = key;
    }
  }

  public static void main(String a[])
  {
    int[] arr = { 5, 11, 32, 1, 45, 6, 2 };
    System.out.println("Array before sorting: ");
    for (int i = 0; i < arr.length; i++)
    {
      System.out.print(arr[i] + " ");
    }

    System.out.println();

    insertionSort(arr);	//sorting array using insertion sort    

    System.out.println("Array after Insertion Sorting: ");
    for (int i = 0; i < arr.length; i++)
    {
      System.out.print(arr[i] + " ");
    }
  }
}

The output of Insertion sort algorithm in java:

---

In this tutorial, we will learn how to implement Heap Sort in java. First, we will start by understanding the Heap Sort algorithm.

• Sorting Algorithms in Java

Heap Sort Algorithm

Heap is a tree in heap sorting that possesses some specific properties whose value should be greater than or equal to that of the children node.

Heapsort is a comparison-based sorting algorithm and is also considered as the improved Selection sort. It is based on a Binary Heap data structure so to understand we must know two types of data structure:
Arrays and trees

What is Binary heap?

Complete Binary tree:
A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.

Binary Heap:
A binary heap is a complete binary tree where the parent node is greater than its two children node.

Representation of Binary tree:
Considering the height of a tree be “h“, then:

• Index of left child = 2*(index of its parent)+1
• Index of right child = 2*(index of its parent)+2

Types of heaps:

• Min heap
• Max heap

Min heap and max heap are the binary heaps that represent the ordering of an array.

• Min heap: In this binary heap, the value of the parent node is always greater than its child node.
• Max heap: In this binary heap, the value of the parent node is always less than its child node.

A heap sorting algorithm for increasing order:

• First, create a max Heap from the input array.
• Replace the root element (which has the largest element) with the last element in the array. Then heapify the root of the tree.
• Now repeat the steps until all elements are sorted in an array.

A heap sorting algorithm for decreasing order.

• First, create a min Heap from the input array.
• Replace the root element (which has the smallest element) with the last element in the array. Then heapify the root of the tree.
• Now repeat the steps until all elements are sorted in an array.

Before we begin, you need to have an idea of the following:

• Methods in java
• for loop in java
• if Statement in java

Time Complexity of Heap Sort:

• Best case:  0(nlogn)
• Average case:  0(nlogn)
• Worst case:  0(nlogn)

---

Java Program to implement heap sort

import java.util.Arrays;

public class HeapSortAlgo
{
  public void sort(int arrA[])
  {
    int size = arrA.length;

    // create heap
    for (int i = size / 2 - 1; i >= 0; i--)
      heapify(arrA, size, i);

    //Replacement of element
    for (int i = size - 1; i >= 0; i--)
    {
      //arrA[0] being max element
      int x = arrA[0];
      arrA[0] = arrA[i];
      arrA[i] = x;

      // call max
      heapify(arrA, i, 0);
    }
  }

  void heapify(int arrA[], int heapSize, int i)
  {
    // Initializing
    int largest = i;
    //Indexes
    int leftChild = 2 *i + 1;
    int rightChild = 2 *i + 2;

    // If left child is larger than root
    if (leftChild < heapSize && arrA[leftChild] > arrA[largest])
      largest = leftChild;

    //if right child is larger than root
    if (rightChild < heapSize && arrA[rightChild] > arrA[largest])
      largest = rightChild;

    // If root is not largest
    if (largest != i)
    {
      int swap = arrA[i];
      arrA[i] = arrA[largest];
      arrA[largest] = swap;

      // Recursive call
      heapify(arrA, heapSize, largest);
    }
  }

  public static void main(String args[])
  {
    int arrA[] = { 6, 23, 9, 15, 4, 1, 11 };

    System.out.println("Array before sorting: " + Arrays.toString(arrA));
    HeapSortAlgo heapSort = new HeapSortAlgo();
    heapSort.sort(arrA);

    System.out.println("Array after heap sort: " + Arrays.toString(arrA));
  }
}

The output of Heap sorting in Java:

---

In this post, we will learn how to implement Selection Sort in java. First, we will start by understanding the Selection sort algorithm.

• Sorting Algorithms in Java

Selection Sort Algorithm

The selection sort is a simple sorting algorithm which is an in-place comparison-based algorithm. It has two parts where the left end has a sorted part and the right end has an unsorted part.

In the beginning, the left end is empty and the right end has all the elements then the smallest element from the right end is brought to the left end and swapped with the leftmost element. This process continues until the element from the right end is brought to the left by swapping.

Although, it may cause a problem with the large inputs.

Before we begin, you need to have an idea of the following:

• Methods in java
• for loop in java

Time Complexity of Selection Sort:

• Best case:  0(n^2)
• Average case:  0(n^2)
• Worst case:  0(n^2)

---

Implementation of selection sort in java

import java.util.Arrays;

public class Main
{
  public static int[] selectionSort(int[] arr)
  {
    for (int i = 0; i < arr.length - 1; i++)
    {
      int index = i;

      for (int j = i + 1; j < arr.length; j++)
      {
        if (arr[j] < arr[index])
          index = j;
      }

      int smallerNumber = arr[index];
      arr[index] = arr[i];
      arr[i] = smallerNumber;
    }

    return arr;
  }

  public static void main(String a[])
  {
    int[] arr = { 25, 5, 12, 60, 2, 1 };
    System.out.println("Array Before Sorting: ");
    System.out.println(Arrays.toString(arr));

    arr = selectionSort(arr);

    System.out.println("Array After Sorting: ");
    System.out.println(Arrays.toString(arr));
  }
}

The output of the Selection sort algorithm in java:

---

In this post, we will learn how to implement Counting Sort in java. First, we will start by understanding the Counting Sort algorithm.

• Sorting Algorithms in Java

Counting Sort Algorithm

Counting Sort Algorithm is an integer-based algorithm, non-comparison, and linear sorting algorithm. The counting sort algorithm sorts the elements in an array in a specific range. It is based on keys between the specific range.

Counting sort calculates the number of occurrences of objects and stores their key values. Then by adding the previous key elements, a new array is formed.

Before we begin, you need to have an idea on following:

• Methods in java
• for loop in java
• while loop in java

Time Complexity of Counting Sort:

• Best case:  0(n+k)
• Average case:  0(n+k)
• Worst case:  0(n+k)

---

Implementation of Counting Sort in java

import java.util.Arrays;

public class CountingSortJava
{
  public static void main(String[] args)
  {
    int[] arr = { 5, 34, 3, 2, 34, 3, 5, 2, 5, 34, 6, 2 };
    int k = 34;

    System.out.println("Array before sorting");
    System.out.println(Arrays.toString(arr));

    countingSortFn(arr, k);

    System.out.println("Array after Counting sorting: ");
    System.out.println(Arrays.toString(arr));

  }

  public static void countingSortFn(int[] input, int k)
  {
   	// creating buckets 
    int counter[] = new int[k + 1];

   	// filling buckets 
    for (int i: input)
    {
      counter[i]++;
    }

   	// sorting 
    int ndx = 0;
    for (int i = 0; i < counter.length; i++)
    {
      while (0 < counter[i])
      {
        input[ndx++] = i;
        counter[i]--;
      }
    }
  }
}

The output of Counting sort algorithm in java:

---