Header Ads Widget

Responsive Advertisement

Insertion Sort

Kartik Chandra Mandal February 15, 2016


Insertion sort iterates, consuming one input element each repetition, and grows a sorted output list. At each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there. It repeats until no input elements remain

java

package com.kartik.sorting;
/**
 *
 * @author MandalKC
 *
 */
public class InsertionSort {
 /**
  *
  * @param input
  * @return
  */
    public static int[] doInsertionSort(int[] input){
     System.out.println("Before Insertion Soring --->>");
  printNumbers(input);
  System.out.println("After Insertion Soring start--->>");
        int temp;
        for (int i = 1; i < input.length; i++) {
            for(int j = i ; j > 0 ; j--){
                if(input[j] < input[j-1]){
                    temp = input[j];
                    input[j] = input[j-1];
                    input[j-1] = temp;
                }
            }
            printNumbers(input);
        }
        return input;
    }
    /**
     *
     * @param input
     */
    private static void printNumbers(int[] input) {
  for (int i = 0; i < input.length; i++) {
   System.out.print(input[i] + ", ");
   } System.out.println("\n");
  }
   
    /**
     *
     * @param a
     */
    public static void main(String a[]){
        int[] arr1 = {10,34,2,56,7,67,88,42};
         doInsertionSort(arr1);
       // int[] arr2 = doInsertionSort(arr1);
        /*for(int i:arr2){
            System.out.print(i);
            System.out.print(", ");
        }*/
    }
}

 

The code you've provided is an implementation of the Insertion Sort algorithm in Java. Insertion Sort is a simple and intuitive sorting algorithm, which is efficient for small or nearly sorted datasets.

Explanation of the Code:

  1. Insertion Sort Algorithm:
    • Insertion sort builds the sorted array one item at a time. It takes each element from the unsorted portion of the array and inserts it into its correct position in the sorted portion.
    • The algorithm works similarly to how you might sort playing cards in your hands.
  2. doInsertionSort Method:
    • Parameters: Takes an integer array input as input.
    • Logic:
      • The outer loop iterates through each element in the array starting from the second element (index 1).
      • The inner loop compares the current element with elements in the sorted portion (on the left side of the current element) and swaps them if they are in the wrong order.
      • After each insertion, the current state of the array is printed to the console.
  3. printNumbers Method:
    • A utility method to print the current state of the array to the console.
  4. main Method:
    • Creates an array arr1 and calls the doInsertionSort method to sort the array.
    • The array is printed after each insertion to show the sorting process step by step.

Example Output:

When you run the code, it will print the array before sorting, after each insertion, and the final sorted array.

plaintext

Before Insertion Sorting --->>

10, 34, 2, 56, 7, 67, 88, 42,

 

After Insertion Sorting start--->>

10, 34, 2, 56, 7, 67, 88, 42,

 

10, 2, 34, 56, 7, 67, 88, 42,

 

2, 10, 34, 56, 7, 67, 88, 42,

 

2, 10, 34, 56, 7, 67, 88, 42,

 

2, 7, 10, 34, 56, 67, 88, 42,

 

2, 7, 10, 34, 56, 67, 88, 42,

 

2, 7, 10, 34, 56, 67, 42, 88,

 

2, 7, 10, 34, 56, 42, 67, 88,

 

Explanation of the Output:

  1. Initial Array: The state of the array before sorting starts.
  2. Sorting Steps: After each insertion, the array is printed to show how elements are being moved to their correct positions.
  3. Final Sorted Array: After all elements have been inserted in the correct positions, the array is fully sorted.

Key Points:

  1. Time Complexity: The time complexity of insertion sort is O(n^2) in the worst case, where n is the number of elements in the array. This happens when the array is sorted in reverse order. However, its average and best-case time complexity is O(n), making it efficient for small or nearly sorted datasets.
  2. Space Complexity: The space complexity is O(1), as the sorting is done in-place without requiring additional memory.
  3. Stability: Insertion sort is a stable sorting algorithm, meaning that the relative order of equal elements is preserved.
  4. Adaptive: Insertion sort is adaptive, which means it performs better (almost linear time) for data that is already sorted or nearly sorted.

Potential Enhancements:

  1. Generic Implementation: Modify the implementation to work with generic types instead of just integers.
  2. Optimizations: Although insertion sort is simple, it could be optimized slightly by reducing the number of swaps.
  3. Visualization: Integrate a visual representation of the sorting process to better understand how the algorithm works.

This code provides a clear and straightforward implementation of insertion sort, allowing you to observe each step of the sorting process through printed output in the console.


Insertion Sort
Insertion Sort



 

Tags:

Post a Comment

0 Comments

Post a Comment