Shell Sort

Shell sort is a sorting algorithm that is a generalization of insertion sort, with two observations:
insertion sort is efficient if the input is "almost sorted", and insertion sort is typically inefficient because it moves values just one position at a time.Shellsort is one of the oldest sorting algorithms, named after its inventor D.L. Shell (1959) [She 59]. It is fast, easy to understand and easy to implement. However, its complexity analysis is a little more 

Reference:http://en.wikipedia.org/wiki/Shell_sort

http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/shell/shellen.htm

Insertion Sort

Insertion sort is a simple sorting algorithm, a comparison sort in which the sorted array (or list) is built one entry at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort. However, insertion sort provides several advantages:
simple implementation
efficient for (quite) small data sets
efficient for data sets that are already substantially sorted: the time complexity is O(n + d), where d is the number of inversions
more efficient in practice than most other simple quadratic (i.e., O(n2)) algorithms such as selection sort or bubble sort: the average running time is n2/4, and the running time is linear in the best case
stable (i.e., does not change the relative order of elements with equal keys)
in-place (i.e., only requires a constant amount O(1) of additional memory space)
online (i.e., can sort a list as it receives it)

Most humans when sorting—ordering a deck of cards, for example—use a method that is similar to insertion sort.

http://en.wikipedia.org/wiki/Heapsort

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 cousin of radix sort in the most to least significant digit flavour. Bucket sort is a generalization of pigeonhole sort. Since bucket sort is not a comparison sort, the Ω(n log n) lower bound is inapplicable. The computational complexity estimates involve the number of buckets.

Bucket sort works as follows:
Set up an array of initially empty "buckets."
Scatter: Go over the original array, putting each object in its bucket.
Sort each non-empty bucket.
Gather: Visit the buckets in order and put all elements back into the original array.

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.[1]

The most common variant of bucket sort operates on a list of n numeric inputs between zero and some maximum value M and divides the value range into n buckets each of size M/n. If each bucket is sorted using insertion sort, the sort can be shown to run in expected linear time (where the average is taken over all possible inputs).[2] However, the performance of this sort degrades with clustering; if many values occur close together, they will all fall into a single bucket and be sorted slowly.

Another variant of bucket sort known as histogram sort adds an initial pass that counts the number of elements that will fall into each bucket using a count array. Using this information, the array values can be arranged into a sequence of buckets in-place by a sequence of exchanges, so that there is no space overhead for bucket storage.

Implementation:

Reference:http://en.wikipedia.org/wiki/Bucket_sort

Quick Sort

Quicksort is a well-known sorting algorithm developed by C. A. R. Hoare that, on average, makes Θ(nlogn) (big O notation) comparisons to sort n items. However, in the worst case, it makes Θ(n2) comparisons. Typically, quicksort is significantly faster in practice than other Θ(nlogn) algorithms, because its inner loop can be efficiently implemented on most architectures, and in most real-world data, it is possible to make design choices which minimize the probability of requiring quadratic time.Quicksort is a comparison sort and, in efficient implementations, is not a stable sort.

Analysis:

From the initial description it's not obvious that quicksort takes Θ(nlogn) time on average. It's not hard to see that the partition operation, which simply loops over the elements of the array once, uses Θ(n) time. In versions that perform concatenation, this operation is also Θ(n).

In the best case, each time we perform a partition we divide the list into two nearly equal pieces. This means each recursive call processes a list of half the size. Consequently, we can make only logn nested calls before we reach a list of size 1. This means that the depth of the call tree is Θ(logn). But no two calls at the same level of the call tree process the same part of the original list; thus, each level of calls needs only Θ(n) time all together (each call has some constant overhead, but since there are only Θ(n) calls at each level, this is subsumed in the Θ(n) factor). The result is that the algorithm uses only Θ(nlogn) time.

An alternate approach is to set up a recurrence relation for the T(n) factor, the time needed to sort a list of size n. Because a single quicksort call involves Θ(n) factor work plus two recursive calls on lists of size n / 2 in the best case, the relation would be:


The master theorem tells us that T(n) = Θ(nlogn).

In fact, it's not necessary to divide the list this precisely; even if each pivot splits the elements with 99% on one side and 1% on the other (or any other fixed fraction), the call depth is still limited to 100logn, so the total running time is still Θ(nlogn).

In the worst case, however, the two sublists have size 1 and n − 1 (for example, if the array consists of the same element by value), and the call tree becomes a linear chain of n nested calls. The ith call does Θ(n − i) work, and . The recurrence relation is:
T(n) = Θ(n) + T(0) + T(n − 1) = O(n) + T(n − 1)

This is the same relation as for insertion sort and selection sort, and it solves to T(n) = Θ(n2). Given knowledge of which comparisons are performed by the sort, there are adaptive algorithms that are effective at generating worst-case input for quicksort on-the-fly, regardless of the pivot selection strategy.[4]

Sample code:

Bubble Sort

definition:

Bubble sort -is a simple sorting algorithm. It works by repeatedly stepping through the list to be sorted, comparing two items at a time and swapping them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted. The algorithm gets its name from the way smaller elements "bubble" to the top of the list. Because it only uses comparisons to operate on elements, it is a comparison sort.Bubble sort is a simple and well-known sorting algorithm. It is used in practice once in a blue moon and its main application is to make an introduction to the sorting algorithms. Bubble sort belongs to O(n2) sorting algorithms, which makes it quite inefficient for sorting large data volumes. Bubble sort is stable and adaptive.

Analysis:

Performance

Bubble sort has worst-case and average complexity both О(n²), where n is the number of items being sorted. There exist many sorting algorithms with the substantially better worst-case or average complexity of O(n log n). Even other О(n²) sorting algorithms, such as insertion sort, tend to have better performance than bubble sort. Therefore bubble sort is not a practical sorting algorithm when n is large.

[edit]
Rabbits and turtles

The positions of the elements in bubble sort will play a large part in determining its performance. Large elements at the beginning of the list do not pose a problem, as they are quickly swapped. Small elements towards the end, however, move to the beginning extremely slowly. This has led to these types of elements being named rabbits and turtles, respectively.

Various efforts have been made to eliminate turtles to improve upon the speed of bubble sort. Cocktail sort does pretty well, but it still retains O(n2) worst-case complexity. Comb sort compares elements large gaps apart and can move turtles extremely quickly, before proceeding to smaller and smaller gaps to smooth out the list. Its average speed is comparable to faster algorithms like Quicksort.

Sample code:

public void bubbleSort(int[] arr) { 

  boolean swapped = true; 

  int j = 0; 

  int tmp; 

  while (swapped) { 

  swapped = false; 

  j++; 

  for (int i = 0; i < arr.length - j; i++) {  

  if (arr[i] > arr[i + 1]) {  

  tmp = arr[i]; 

  arr[i] = arr[i + 1]; 

  arr[i + 1] = tmp; 

  swapped = true; 

  } 

  }  

  } 

}

Reference: http://en.wikipedia.org/wiki/Bubble_sort

                http://simpleprogrammingtutorials.com/tutorials/sorts/bubble-sort.php

Queue Implementation

class Link {
public int iData;
public Link next;
public Link(int id) {
iData = id;
}

public String toString() {
return "{" + iData + "} ";
}
}

class LinkList {
private Link first;

public LinkList() {
first = null;
}

public boolean isEmpty() {
return (first == null);
}

public void insertFirst(int dd) {
Link newLink = new Link(dd);
newLink.next = first;
first = newLink;
}

public int deleteFirst() {
Link temp = first;
first = first.next;
return temp.iData;
}

public String toString() {
String str = "";
Link current = first;
while (current != null) {
str += current.toString();
current = current.next;
}
return str;
}
}

class FirstLastList {
private Link first;

private Link last;

public FirstLastList() {
first = null;
last = null;
}

public boolean isEmpty() {
return first == null;
}

public void insertFirst(int dd) {
Link newLink = new Link(dd);
if (isEmpty())
last = newLink;
newLink.next = first;
first = newLink;
}

public void insertLast(int dd) {
Link newLink = new Link(dd);

if (isEmpty())
first = newLink;
else
last.next = newLink;
last = newLink;
}

public int deleteFirst() {
int temp = first.iData;
if (first.next == null)
last = null;
first = first.next;
return temp;
}

public String toString() {
String str = "";
Link current = first;
while (current != null) {
str += current.toString();
current = current.next;
}
return str;
}
}

class LinkQueue {
private FirstLastList theList;

public LinkQueue() {
theList = new FirstLastList();
}

public boolean isEmpty() {
return theList.isEmpty();
}

public void insert(int j) {
theList.insertLast(j);
}

public double remove() {
return theList.deleteFirst();
}

public String toString() {
return theList.toString();
}
}

public class MainClass {
public static void main(String[] args) {
LinkQueue theQueue = new LinkQueue();
theQueue.insert(20);
theQueue.insert(40);
System.out.println(theQueue);

theQueue.insert(60);
theQueue.insert(80);

System.out.println(theQueue);

theQueue.remove();
theQueue.remove();

System.out.println(theQueue);
}
}


Reference:http:www.java2s.com/Tutorial/Java/0140_Collections/AQueueImplementedbyaLinkedList.html





Doubly Linked List implementation

class Link {
public int iData; //data item
public Link next; //next link in the list
public Link previous; //previous link in the list

public Link(int id) {
iData = id;
}

//display the elements in the list

public void displayList(){
return "{" + iData + "} ";
}
}

/*another class which contains the methods for the program*/

class DoublyLinkedList {
private Link first;
private Link last;

public DoublyLinkedList() {
first = null;
last = null;
}

public boolean isEmpty() {
return first == null;
}

public void insertFirst(int dd) {
Link newLink = new Link(dd);
if (isEmpty()){
last = newLink;
}else{
first.previous = newLink;
}
newLink.next = first;
first = newLink;
}

public void insertLast(int dd) {
Link newLink = new Link(dd);
if (isEmpty()){
first = newLink;
}else {
last.next = newLink;
newLink.previous = last;
}
last = newLink;
}

public Link deleteFirst() {
Link temp = first;
if (first.next == null){
last = null;
}else{
first.next.previous = null;
}
first = first.next;
return temp;
}

public Link deleteLast() {
Link temp = last;
if (first.next == null){
first = null;
}else{
last.previous.next = null;
}
last = last.previous;
return temp;
}

public boolean insertAfter(int key, int dd) {
Link current = first;
while (current.iData != key) {
current = current.next;
if (current == null){
return false;
}
}
Link newLink = new Link(dd);

if (current == last) {
newLink.next = null;
last = newLink;
} else {
newLink.next = current.next;

current.next.previous = newLink;
}
newLink.previous = current;
current.next = newLink;
return true;
}

public Link deleteKey(int key) {
Link current = first;
while (current.iData != key) {
current = current.next;
if (current == null)
return null;
}
if (current == first){
first = current.next;
}else{
current.previous.next = current.next;
}

if (current == last){
last = current.previous;
}else{
current.next.previous = current.previous;
}
return current;
}

}

[TUTORIAL_DOUBLY]

http://dept-info.labri.u-bordeaux.fr/~strandh/Teaching/MTP/Common/Strandh-Tutorial/double-list.html

[WIKI]

http://en.wikipedia.org/wiki/Linked_list

Stack implementation

//a class which declares the variables and the constructors
class Link{
public int iData=0;


public Link(int iData, )
{
iData=id;

}

public void displayLink()
{
System.out.println(iData+":" );
}
}

//the class which contains the methods or the operations on the stack
class StackList{
private Link first;

public StackList(){
first=null;

}

public boolean isEmpty() {
return (first == null);
}

public void insertFirst( int id) {
Link newLink = new Link( id);
newLink.next = first;
first = newLink;
}

public Link deleteFirst()
{
Link temp=first;
return temp;
}

public Link pick()
Link temp=first;
return temp;
}

public void displayList
{
System.out.print("Elements on the stack: ");
Link temp=first;
while(temp!=null)
{
temp.displayList();
}

System.out.println(" ");
}
}

//the main class which applies the methods on the stack
class StackListApp
{
public static void main (String[]args)
{
StackList theList=new StackList();

theList.insertFirst(12);
theList.insertFirst(25);
theList.insertFirst(91);

//when deleting
//just erase the comment if you want to run the method of deletion
theList.deleteFirst();

//when displaying the element
theList.displayList();
}
}

Double-ended List Implementation

class Link {
public int iData;

public Link next;

public Link(int id) {
iData = id;
}

public String toString() {
return "{" + iData + "} ";
}
}

class FirstLastList {
private Link first;
private Link last;

public FirstLastList() {
first = null;
last = null;
}

public boolean isEmpty() {
return first == null;
}

public void insertFirst(int dd) {
Link newLink = new Link(dd);
if (isEmpty())
last = newLink;
newLink.next = first;
first = newLink;
}

public void insertLast(int dd) {
Link newLink = new Link(dd);

if (isEmpty())
first = newLink;
else
last.next = newLink;
last = newLink;
}

public int deleteFirst() {
int temp = first.iData;
if (first.next == null)
last = null;
first = first.next;
return temp;
}

public String toString() {
String str = "";
Link current = first;
while (current != null) {
str += current.toString();
current = current.next;
}
return str;
}
}

public class MainClass {
public static void main(String[] args) {
FirstLastList theList = new FirstLastList();

theList.insertFirst(22);
theList.insertFirst(44);
theList.insertFirst(66);

theList.insertLast(11);
theList.insertLast(33);
theList.insertLast(55);

System.out.println(theList);

theList.deleteFirst();
theList.deleteFirst();

System.out.println(theList);
}
}


Reference:http://www.java2s.com/Tutorial/Java/0140_Collections/DoubleEndedListslistwithfirstandlastreference.html