Skip to main content

Posts

Showing posts with the label insertion sort

Scala Implementation of Insertion Sort

Introduction Insertion sort is the best sorting algorithm for small-sized list of elements as compared to selection sort and  bubble sort . This sorting algorithm always maintains a sorted sublist within an iteration i.e. it finds the correct position of a single element at a time and inserts it in its correct position within the currently sorted sublist. Worst Complexity     : O(n*n) Best Complexity        : O(n) Average Complexity : O(n*n) Implementation package main.scala object InsertionSort {   val array = Array(0, 5, 2, 6, 3, 1)   def main(args: Array[String]) {     print("Unsorted List ")     println(array.toList)     print("Asceding sorted List ")     insertionSortAscending;     println(array.toList)     insertionSortDescending     print("Desceding sorted List ")     println(array.toList)   }   def insertionSortAscending { //first element is considered as sorted sublist     for (outer <- 1 until array.length) {

Java code of Insertion sort

Introduction Insertion sort is the best sorting algorithm for small-sized list of elements as compared to selection sort and bubble sort . This sorting algorithm always maintains a sorted sublist within an iteration i.e. it finds the correct position of a single element at a time and inserts it in its correct position within the currently sorted sublist. Worst Complexity    : O(n*n) Best Complexity        : O(n) Average Complexity : O(n*n) Imperative style using Java 7 public class InsertionSortExample { private static int array[] = {0,5,2,6,3,1,-9}; public static void main(String[] args) { insertionSortAscending(); System.out.println("Ascending Sorted List"); for(int value : array) { System.out.print(value + " "); } insertionSortDescending(); System.out.println("\nDescending Sorted List"); for(int value : array) { System.out.print(value + " "); } } private static void insertionSortAscending() {