/******************************************************************************

ID: 3791957 • Letter: #

Question

/******************************************************************************
* Compilation: javac Insertion.java
* Execution: java Insertion < input.txt
* Dependencies: StdOut.java StdIn.java
* Data files: http://algs4.cs.princeton.edu/21sort/tiny.txt
* http://algs4.cs.princeton.edu/21sort/words3.txt
*
* Sorts a sequence of strings from standard input using insertion sort.
*
* % more tiny.txt
* S O R T E X A M P L E
*
* % java Insertion < tiny.txt
* A E E L M O P R S T X [ one string per line ]
*
* % more words3.txt
* bed bug dad yes zoo ... all bad yet
*
* % java Insertion < words3.txt
* all bad bed bug dad ... yes yet zoo [ one string per line ]
*
******************************************************************************/

import java.util.Comparator;

/**
* The {@code Insertion} class provides static methods for sorting an
* array using insertion sort.
* 
* This implementation makes ~ 1/2 n^2 compares and exchanges in
* the worst case, so it is not suitable for sorting large arbitrary arrays.
* More precisely, the number of exchanges is exactly equal to the number
* of inversions. So, for example, it sorts a partially-sorted array
* in linear time.
* 
* The sorting algorithm is stable and uses O(1) extra memory.
* 
* See <a href="http://algs4.cs.princeton.edu/21elementary/InsertionPedantic.java.html">InsertionPedantic.java</a>
* for a version that eliminates the compiler warning.
* 
* For additional documentation, see <a href="http://algs4.cs.princeton.edu/21elementary">Section 2.1</a> of
* Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.
*
* @author Robert Sedgewick
* @author Kevin Wayne
*/
public class Insertion {

// This class should not be instantiated.
private Insertion() { }

/**
* Rearranges the array in ascending order, using the natural order.
* @param a the array to be sorted
*/
public static void sort(Comparable[] a) {
int n = a.length;
for (int i = 0; i < n; i++) {
for (int j = i; j > 0 && less(a[j], a[j-1]); j--) {
exch(a, j, j-1);
}
assert isSorted(a, 0, i);
}
assert isSorted(a);
}

/**
* Rearranges the subarray a[lo..hi] in ascending order, using the natural order.
* @param a the array to be sorted
* @param lo left endpoint
* @param hi right endpoint
*/
public static void sort(Comparable[] a, int lo, int hi) {
for (int i = lo; i <= hi; i++) {
for (int j = i; j > lo && less(a[j], a[j-1]); j--) {
exch(a, j, j-1);
}
}
assert isSorted(a, lo, hi);
}

/**
* Rearranges the array in ascending order, using a comparator.
* @param a the array
* @param comparator the comparator specifying the order
*/
public static void sort(Object[] a, Comparator comparator) {
int n = a.length;
for (int i = 0; i < n; i++) {
for (int j = i; j > 0 && less(a[j], a[j-1], comparator); j--) {
exch(a, j, j-1);
}
assert isSorted(a, 0, i, comparator);
}
assert isSorted(a, comparator);
}

/**
* Rearranges the subarray a[lo..hi] in ascending order, using a comparator.
* @param a the array
* @param lo left endpoint
* @param hi right endpoint
* @param comparator the comparator specifying the order
*/
public static void sort(Object[] a, int lo, int hi, Comparator comparator) {
for (int i = lo; i <= hi; i++) {
for (int j = i; j > lo && less(a[j], a[j-1], comparator); j--) {
exch(a, j, j-1);
}
}
assert isSorted(a, lo, hi, comparator);
}

// return a permutation that gives the elements in a[] in ascending order
// do not change the original array a[]
/**
* Returns a permutation that gives the elements in the array in ascending order.
* @param a the array
* @return a permutation {@code p[]} such that {@code a[p[0]]}, {@code a[p[1]]},
* ..., {@code a[p[n-1]]} are in ascending order
*/
public static int[] indexSort(Comparable[] a) {
int n = a.length;
int[] index = new int[n];
for (int i = 0; i < n; i++)
index[i] = i;

for (int i = 0; i < n; i++)
for (int j = i; j > 0 && less(a[index[j]], a[index[j-1]]); j--)
exch(index, j, j-1);

return index;
}

/***************************************************************************
* Helper sorting functions.
***************************************************************************/

// is v < w ?
private static boolean less(Comparable v, Comparable w) {
return v.compareTo(w) < 0;
}

// is v < w ?
private static boolean less(Object v, Object w, Comparator comparator) {
return comparator.compare(v, w) < 0;
}

// exchange a[i] and a[j]
private static void exch(Object[] a, int i, int j) {
Object swap = a[i];
a[i] = a[j];
a[j] = swap;
}

// exchange a[i] and a[j] (for indirect sort)
private static void exch(int[] a, int i, int j) {
int swap = a[i];
a[i] = a[j];
a[j] = swap;
}

/***************************************************************************
* Check if array is sorted - useful for debugging.
***************************************************************************/
private static boolean isSorted(Comparable[] a) {
return isSorted(a, 0, a.length - 1);
}

// is the array sorted from a[lo] to a[hi]
private static boolean isSorted(Comparable[] a, int lo, int hi) {
for (int i = lo+1; i <= hi; i++)
if (less(a[i], a[i-1])) return false;
return true;
}

private static boolean isSorted(Object[] a, Comparator comparator) {
return isSorted(a, 0, a.length - 1, comparator);
}

// is the array sorted from a[lo] to a[hi]
private static boolean isSorted(Object[] a, int lo, int hi, Comparator comparator) {
for (int i = lo + 1; i <= hi; i++)
if (less(a[i], a[i-1], comparator)) return false;
return true;
}

// print array to standard output
private static void show(Comparable[] a) {
for (int i = 0; i < a.length; i++) {
System.out.println(a[i]);
}
}

}

Then this is the Test:

public class TestInsertionSort {

   /**
   * @param args
   */
   public static void main(String[] args) {
       String[] names = initializeNamesArray();

       System.out.println("Displaying names array before sorting...");
       display(names);

       System.out.println("Being sorting...");
       Insertion.sort(names);
       System.out.println("End sorting...");

       System.out.println("Displaying names array after sorting...");
       display(names);
   }

   private static String[] initializeNamesArray() {
       String array[] = {"Joe", "Bill", "Ann", "Omar", "Sydney", "Ellen", "Mark", "Marshall", "Earl", "Vicky"};

       return array;
   }

private static void display(String[] names) {
for (String name : names) {
System.out.println(name);
}
}

}

Explanation / Answer

Sorts a sequence of strings from standard input using an optimized version of insertion sort String is immutable, you cannot really sort it. However, we can obtain the underlying char array and sort that and then create a new String from it. Below is the sample example for the same : public class StringSort { public static String insertionSort(String s) { return new String(insertionSort(s.toCharArray())); } private static String insertionSort(char[] array) { int len = array.length; for (int i = len - 1; i > 0; i--) { if (array[i]

Navigate

/******************************************************************************

/*******************************************************************************

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.

/******************************************************************************

Question

Explanation / Answer

Related Questions

Navigate