Sort an array of strings so that all the anagrams are next to each other

Write a method to sort an array of strings so that all the anagrams are next to each other.
The basic idea is to implement a normal sorting algorithm where you override the compareTo method to compare the “signature” of each string. In this case, the signature is the alphabetically sorted string.

public class AnagramComparator implements Comparator<String> {
 public String sortChars(String s) {
 char[] content = s.toCharArray();
 Arrays.sort(content);
 return new String(content);
 }

 public int compare(String s1, String s2) {
 return sortChars(s1).compareTo(sortChars(s2));
 }
 }

Now, just sort the arrays, using this compareTo method instead of the usual one.
Arrays.sort(array, new AnagramComparator());

Shell sort

Refer : http://education.cdacmumbai.in/education/pgdst/dsalfac/notes/ShellSort.pdf


Shellsort works by comparing elements that are distant rather than adjacent elements in an array or list where adjacent elements are compared.

Shellsort makes multiple passes through a list and sorts a number of equally sized sets using the insertion sort.

Shellsort improves on the efficiency of insertion sort by quickly shifting values to their destination.

Shellsort is also known as diminishing increment sort.

The distance between comparisons decreases as the sorting algorithm runs until the last phase in which adjacent elements are compared

After each phase and some increment   hk, for every i, we have a[ i ] ≤ a [ i + hk ] all elements spaced hk apart are sorted.

The file is said to be hk – sorted.

Advantages :

Advantage of Shellsort is that its only efficient for medium size lists. For bigger lists, the algorithm is not the best choice. Fastest of all O(N^2) sorting algorithms.

5 times faster than the bubble sort and a little over twice as fast as the insertion sort, its closest competitor.

Disadvantages :

Disadvantage of Shellsort is that it is a complex algorithm and its not nearly as efficient as the merge, heap, and quick sorts.

The shell sort is still significantly slower than the merge, heap, and quick sorts, but its relatively simple algorithm makes it a good choice for sorting lists of less than 5000 items unless speed important. It's also an excellent choice for repetitive sorting of smaller lists.

Best Case: The best case in the shell sort is when the array is already sorted in the right order. The number of comparisons is less.

Bucket Sort

Bucket sort, or bin sort, is a sorting algorithm that works by partitioning an array into a number of buckets. Each bucket is then sorted individually, either using a different sorting algorithm, or by recursively applying the bucket sorting algorithm. It is a distribution sort, and is a cousin of radix sort in the most to least significant digit flavour

Bucket sort works as follows:

1. Set up an array of initially empty "buckets."
2. Scatter: Go over the original array, putting each object in its bucket.
3. Sort each non-empty bucket.
4. Gather: Visit the buckets in order and put all elements back into the original array.

Optimizations         

A common optimization is to put the elements back in the original array first, then run insertion sort over the complete array; because insertion sort's runtime is based on how far each element is from its final position, the number of comparisons remains relatively small, and the memory hierarchy is better exploited by storing the list contiguously in memory.

Comparision with other sorting techniques:

1.Bucket sort can be seen as a generalization of counting sort; in fact, if each bucket has size 1 then bucket sort degenerates to counting sort.

2.Bucket sort with two buckets is effectively a version of quicksort where the pivot value is always selected to be the middle value of the value range. While this choice is effective for uniformly distributed inputs, other means of choosing the pivot in quicksort such as randomly selected pivots make it more resistant to clustering in the input distribution.

3.The n-way mergesort algorithm also begins by distributing the list into n sublists and sorting each one; however, the sublists created by mergesort have overlapping value ranges and so cannot be recombined by simple concatenation as in bucket sort. Instead, they must be interleaved by a merge algorithm. However, this added expense is counterbalanced by the simpler scatter phase and the ability to ensure that each sublist is the same size, providing a good worst-case time bound.

4.Top-down radix sort can be seen as a special case of bucket sort where both the range of values and the number of buckets is constrained to be a power of two. Consequently, each bucket's size is also a power of two, and the procedure can be applied recursively. This approach can accelerate the scatter phase, since we only need to examine a prefix of the bit representation of each element to determine its bucket.

Java code :

import java.util.ArrayList;
import java.util.Arrays;


public class BucketSort {


public static void main(String args[]) {


Double[] array = { 9.0, 8.0, 7.0, 6.0, 5.0, 4.0, 3.0, 2.0, 1.0 };


ArrayList<Double> masterlist = new ArrayList<Double>(Arrays
.asList(array));


// all of the doubles will be 0.0 <= x < 100.0
double rangeOfBucket = 100.0 / masterlist.size();


// creating a new ArrayList of n buckets
ArrayList[] buckets = new ArrayList[masterlist.size()];
buckets = fillBuckets(buckets);


double d;
for (int i = 0; i < masterlist.size(); i++) {
d = (Double) masterlist.get(i);
// this mess discovers the appropriate bucket and dumps d in it
buckets[(int) (d / rangeOfBucket)].add(d);
}


masterlist = new ArrayList<Double>();


for (int m = 0; m < buckets.length; m++) {
buckets[m] = insertionSort(buckets[m]); // sort the bucket
for (int n = 0; n < buckets[m].size(); n++) {
masterlist.add((Double) buckets[m].get(n));// reading the
// numbers back into
// the original list
// in order
}
}


System.out.println(masterlist.toString());


}


/**
* Modified version of InsertionSort found at
* http://www.samspublishing.com/articles/article.asp?p=31526&seqNum=4&rl=1
* 
* @param a
*            The ArrayList to be sorted
* @return A sorted ArrayList
*/
public static ArrayList insertionSort(ArrayList a) {


int in, out;


for (out = 1; out < a.size(); out++) {
double temp = (Double) a.get(out); // remove marked item


in = out; // start shifts at out


// until one is smaller,
while (in > 0 && (Double) a.get(in - 1) >= temp) {
a.set(in, a.get(in - 1));// shift item right
in--; // go left one position
}


a.set(in, temp); // insert marked item
}


return a;
}


/**
* Helper method to fill an array of ArrayLists with _unique_ ArrayLists,
* something that Arrays.fill() does not do.
* 
* @param b
*            The array of ArrayLists to be filled
* @return The original array filled with empty ArrayLists
*/
private static ArrayList[] fillBuckets(ArrayList[] b) {
for (int i = 0; i < b.length; i++) {
b[i] = new ArrayList();
}
return b;
}


}

Quick Sort

Algorithm :
QUICK SORT (A,p,r)
1 if p < r
2 then q<-- PARTITION(A,p,r)
3 QUICK SORT(A,p,q)
4 QUICK SORT(A,q + 1,r)
Notice that we only examine elements by comparing them to other elements. This makes quicksort a comparison sort. Divide and Conquer Algorithms that solve (conquer) problems by dividing them into smaller sub-problems until the problem is so small that it is trivially solved. in place In place sorting algorithms don't require additional temporary space to store elements as they sort; they use the space originally occupied by the elements. Analysis : The best-case behavior of the quicksort algorithm occurs when in each recursion step the partitioning produces two parts of equal length. In order to sort n elements, in this case the running time is in Θ(n log(n)). This is because the recursion depth is log(n) and on each level there are n elements to be treated (Figure 2 a). The worst case occurs when in each recursion step an unbalanced partitioning is produced, namely that one part consists of only one element and the other part consists of the rest of the elements (Figure 2 c). Then the recursion depth is n-1 and quicksort runs in time Θ(n2). The choice of the comparison element x determines which partition is achieved. Suppose that the first element of the sequence is chosen as comparison element. This would lead to the worst case behavior of the algorithm when the sequence is initially sorted. Therefore, it is better to choose the element in the middle of the sequence as comparison element. Even better would it be to take the n/2-th greatest element of the sequence (the median). Then the optimal partition is achieved. Actually, it is possible to compute the median in linear time [AHU 74]. This variant of quicksort would run in time O(n log(n)) even in the worst case. However, the beauty of quicksort lies in its simplicity. And it turns out that even in its simple form quicksort runs in O(n log(n)) on the average. Moreover, the constant hidden in the O-notation is small. Therefore, we trade this for the (rare) worst case behavior of Θ(n2).

Java Code :

void quicksort(int[] a, int low, int high) {

   if (low > high)
 return;

  int i = low;
  int j = high;
  int h;
  // comparision element
  int x = a[(low + high) / 2];
  // partition
  do {
   while (a[i] < x)
    i++;
   while (a[j] > x)
    j--;
   if (i <= j) {
    h = a[i];
    a[i] = a[j];
    a[j] = h;
    i++;
    j--;
   }
  } while (i <= j);
   quicksort(a, low, j);
   quicksort(a, i, high);
 }

Selection Sort

Refer for animated applets :http://www.cse.iitk.ac.in/users/dsrkg/cs210/applets/sortingII/heapSort/heapSort.html

Algorithm :
for i = 1:n,
k = i
for j = i+1:n, if a[j] < a[k], k = j
→ invariant: a[k] smallest of a[i..n]
swap a[i,k]
→ invariant: a[1..i] in final position
end

java code :

void selectionSort(int[] a) {
int length = a.length;
for (int i = 0; i < length - 1; i++) {
int minPos = i;
for (int j = i + 1; j < length; j++) {
if (a[j] < a[minPos]) {
minPos = j;
}
}
// swapping min element position with i th position
int temp = a[minPos];
a[minPos] = a[i];
a[i] = temp;
}
}

Properties :
Not stable
O(1) extra space
Θ(n2) comparisons
Θ(n) swaps
Not adaptive


Selecting the lowest element requires scanning all n elements (this takes n − 1 comparisons) and then swapping it into the first position. Finding the next lowest element requires scanning the remaining n − 1 elements and so on, for (n − 1) + (n − 2) + ... + 2 + 1 = n(n − 1) / 2 ∈ Θ(n2) comparisons (see arithmetic progression). Each of these scans requires one swap for n − 1 elements (the final element is already in place).


Among simple average-case Θ(n2) algorithms, selection sort almost always outperforms bubble sort and gnome sort, but is generally outperformed by insertion sort. Insertion sort is very similar in that after the kth iteration, the first k elements in the array are in sorted order. Insertion sort's advantage is that it only scans as many elements as it needs in order to place the k + 1st element, while selection sort must scan all remaining elements to find the k + 1st element.

While selection sort is preferable to insertion sort in terms of number of writes (Θ(n) swaps versus Ο(n2) swaps), it almost always far exceeds (and never beats) the number of writes that cycle sort makes, as cycle sort is theoretically optimal in the number of writes. This can be important if writes are significantly more expensive than reads, such as with EEPROM or Flash memory, where every write lessens the lifespan of the memory.

Insertion Sort

java code :

void insertionSort(int[] a) {
        for (int i = 1; i < a.length; i++) {
            int key = a[i];
            int pos = i - 1;
            while (pos >= 0 && a[pos] > key) {
                a[pos + 1] = a[pos];
                pos--;
            }
            a[pos + 1] = key;
        }
    }

The best case input is an array that is already sorted. In this case insertion sort has a linear running time (i.e., Θ(n)). During each iteration, the first remaining element of the input is only compared with the right-most element of the sorted subsection of the array.
The worst case input is an array sorted in reverse order. In this case every iteration of the inner loop will scan and shift the entire sorted subsection of the array before inserting the next element. For this case insertion sort has a quadratic running time (i.e., O(n2)).
The average case is also quadratic, which makes insertion sort impractical for sorting large arrays. However, insertion sort is one of the fastest algorithms for sorting very small arrays, even faster than quick sort; indeed, good quick sort implementations use insertion sort for arrays smaller than a certain threshold, also when arising as subproblems; the exact threshold must be determined experimentally and depends on the machine, but is commonly around ten.

It is possible to find the inserting position of element ai faster, namely by binary search. However, moving the elements to the right in order to make room for the element to be inserted takes linear time anyway.

Bubble sort

Algorithm

Compare each pair of adjacent elements from the beginning of an array and, if they are in reversed order, swap them.
If at least one swap has been done, repeat step 1.
You can imagine that on every step big bubbles float to the surface and stay there. At the step, when no bubble moves, sorting stops. Let us see an example of sorting an array to make the idea of bubble sort clearer.

java code :

public static void bubbleSort(int[] data)
{
int length = data.length;
for (int k = 0; k < length - 1; k++)
{
boolean isSorted = true;

for (int i = 1; i < length - k; i++)
{
if (data[i] < data[i - 1])
{
int tempVariable = data[i];
data[i] = data[i - 1];
data[i - 1] = tempVariable;

isSorted = false;

}
}

if (isSorted)
break;
}
}


Properties :
Stable
O(1) extra space
O(n2) comparisons and swaps
Adaptive: O(n) when nearly sorted