SORTING

1.BUBBLE SORT
It is the simplest sorting algorithm that performs repeatedly and swapping the first element to the second element. And make it into a sorting algorithm. it performs swapping if it in a wrong order, for example the list of a student during flag ceremony; the student must be in order according to their hight to make it orderly net and orderly arrange into sorting line.

A.Illustration:
Step-by-step example

Let us take the array of numbers "5 1 4 2 8", and sort the array from lowest number to greatest number using bubble sort algorithm. In each step, elements written in bold are being compared.

First Pass:
( 5 1 4 2 8 ) \to ( 1 5 4 2 8 ) Here, algorithm compares the first two elements, and swaps them.
( 1 5 4 2 8 ) \to ( 1 4 5 2 8 )
( 1 4 5 2 8 ) \to ( 1 4 2 5 8 )
( 1 4 2 5 8 ) \to ( 1 4 2 5 8 ) Now, since these elements are already in order, algorithm does not swap them.
Second Pass:
( 1 4 2 5 8 ) \to ( 1 4 2 5 8 )
( 1 4 2 5 8 ) \to ( 1 2 4 5 8 )
( 1 2 4 5 8 ) \to ( 1 2 4 5 8 )
( 1 2 4 5 8 ) \to ( 1 2 4 5 8 )
Now, the array is already sorted, but our algorithm does not know if it is completed. Algorithm needs one whole pass without any swap to know it is sorted.
Third Pass:
( 1 2 4 5 8 ) \to ( 1 2 4 5 8 )
( 1 2 4 5 8 ) \to ( 1 2 4 5 8 )
( 1 2 4 5 8 ) \to ( 1 2 4 5 8 )
( 1 2 4 5 8 ) \to ( 1 2 4 5 8 )
Finally, the array is sorted, and the algorithm can terminate.
[http://en.wikipedia.org/wiki/Bubble_sort]

2.INSERTION SORT
It is the is a simple sorting algorithm, in which each element from unsorted algorithm will pick one by one and put it into sorted. the new list and the remaining elements can share the array's space, insertion is expensive it required shifting all the following elements over by one.

A. Illustration:

Example

The example below shows the steps necessary to sort 6 elements. White elements are unsorted, grey elements have been sorted and the red element has been inserted in the current step.
833 197 153 634 889 381
833 197 153 634 889 381
833 197 153 634 381 889
833 197 153 381 634 889
833 197 153 381 634 889
833 153 197 381 634 889
153 197 381 634 833
[http://corewar.co.uk/assembly/insertion.htm]

3.SHELL SORT
It is sort by moving out of order elements more than one position at a time. Arranging the data sequence in a two-dimensional array and then sorting the columns of the array using insertion sort is the best implementation of this sorting algorithm. Although this method is inefficient for large data sets, it is one of the fastest algorithms for sorting small numbers of elements. The advantage of this algorithm is that it requires relatively small amounts of memory.

A.Illustration:

For example, consider a list of numbers like [ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ]. If we started with a step-size of 5, we could visualize this as breaking the list of numbers into a table with 5 columns. This would look like this:

13 14 94 33 82
25 59 94 65 23
45 27 73 25 39
10

We then sort each column, which gives us

10 14 73 25 23
13 27 94 33 39
25 59 94 65 82
45

When read back as a single list of numbers, we get [ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ]. Here, the 10 which was all the way at the end, has moved all the way to the beginning. This list is then again sorted using a 3-gap sort, and then 1-gap sort (simple insertion sort).
[http://en.wikipedia.org/wiki/Shell_sort]

4.MERGE SORT
It works by comparing every two elements and swapping them if the first should come after the second then merges each of the resulting lists of two into lists of four, then merges those lists of four, and so on;it is stable,meaning that it preserves the input order of equal elements in the sorted output.

A.Illustration:

QUEUE IMPLEMENTATION

Concept: List of Barangay Councilor Officials

//declaration of a constructor
class Queue{
public int positionnum;
public String firstname;
public String lastname;
public char middlename;
public Queue next;

public Queue (int Pnum, String Fname String Lname char M, )
{

positionnum=Pnum;
firstname=Fname;
lastname=Lname;
middlename=M;
}


//displaying the elements on the queue
public void displayQueue()
{
System.out.print(positionnum +” “ + firstname +” “ +” “middlename+ “ “ +: + lastname)
}
}


/*a separate class which has the methods to be used by the queue implemented in a linked list*/
class QueueList
private Queue first;
private Queue last;
public QueueList()
{
first=null;
last=null;
}


//checking if the queue has elements
public Boolean isEmpty()
{
return (first==null);
}



//inserting an element on the queue
public void Enqueue(int Pnum, String Fname String Lname char M, )

{
Queue newQueue= new Queue (int Pnum, String Fname String Lname char M, )

if( isEmpty())
last = newQueue;
newQueue.next=first;
first=newQueue;
}


//deleting an element on the queue
public void Dequeue (int Pnum)
{
Queue newQueue=new Queue (int Pnum, String Fname String Lname char M, )

int temp=first.entrynum;
if (first.next==null)
last=null;
first=first.next;
return temp



}
}

public class MainClass {
public static void main(String[] args) {
LinkQueue theQueue = new LinkQueue();
theQueue.enqueue(1, “Marjorie”, “Egot”, ‘T’ )

theQueue.enqueue(2, “Chrisdyll”, “Pellejo”, ‘P’)
System.out.println(theQueue);

theQueue.enqueue(3, “Julie”, “Pabio”, ‘L’)
System.out.println(theQueue)



theQueue.dequeue(3);

System.out.println(theQueue);



System.out.println(theQueue);
}
}

QUEUES

QUEUES
is simply a waiting line that grows by adding elements to its end and shrinks by taking elements from its front. Unlike a stack, a queue is a structure in which both ends are used: one for adding new elements and one for removing them.Therefore, the last element has to wait until all elements preceding it on the queue are removed. A queue is an FIFO structure:first in/first out.

Queue operation are similar to stack operations. The following operations are needed to properly manage a queue:

Stack Implementation

public class Stack{
private java.util.ArrayList pool=new java.util.ArrayList();
public Stack(){
}
public Satck(int n){
pool.ensureCapacity(n);
}
public void clear(){
pool.clear();
}
public boolean isEmpty(){
return pool.isEmpty();
}
public Object topEl(){
if(isEmpty())
throw new java.util.EmptyStackExeception();
return pool.lastElement();
}
public Object pop(){
if(isEmpty())
throw new java.util.EmptyStackExeception();
retrun pool.remove(poo.size()-1);
}
public void push (Object El){
pool.add(El);
}
public String toString(){
return pool.toString();
}
}
public class AppStack{
private java.util.LinkedList List=new java.util.LinkedList();
public AppStack(){
}
public void clear(){
list.clear();
}
public boolean isEmpty(){
return list.isEmpty();
}
public Object topEl(){
if(isEmpty())
throw new java.util.EmptyStackExceptio();
return list.getLast();
}
public Object pop(){
if(isEmpty())
throw new java.util.EmptyStackException();
return list.removeLast();
}
public void push(Object El);
list.addLast(El);
}
public String toString(){
return list.toString();
}
}

Double Ended Linked List

A. Concept:
DOuble Ended Linked List has a list with first and last references.

B. Implementation of a double ende linked list;

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);
}
}

[http://www.java2s.com/Tutorial/Java/0140__Collections/DoubleEndedListslistwithfirstandlastreferences.htm]

Doubly Linked List

A.Concept:
Doubly Linked List is the linked list redefined so that the node in list has two reference fields, one to the successor and one to the predecessor.Method for processing doubly linked list are sligthly more comlpicated than singly linked counterparts because there is one more reference field to be maintained. Only two methods are discussed: a method to inserta node at hte end of a doubly linked list and a method to remove a node from the end.
public class DoublyLink
{
public int whie;
public DoublyLink next, prev;
public DoublyLink(int a)
{
this(a, null, null);
}
public DoublyLink(int a, DoublyLInk n, DoublyLink p)
{
whie=a;
next=n;
prev=p;
}
}

public class DoublyLinkList{
private DoublyLink head, tail;
public DoublyLinkList()
{
head=null=null;
}
public boolean isEmpty()
{
return head==null;
}
public void addToTail(int a)
{
if(!isEmpty()) {
tail=new DoublyLink(a, null, tail);
tail.prev.next=tail;
}
else
head=tail=new DoublyLink(a);
}
public int removeFromTail(){
int a=tail.whie;
if(head==tail) //if only node in the list;
head=tail=null;
else{ //if more than one node in the list;
tail=tail.prev;
tail.next=null;
}
return a;
}
System.out.println(" ");
}
}

Stacks

1. What is stacks?

A stack is a data structure that allows data to be inserted (a 'push' operation), and removed (a 'pop' operation). Many stacks also support a read ahead (a 'peek' operation), which reads data without removing it. A stacks is a linear data structures that can be accessed only at one of its ends for storing and retrieving data. Such a stack resembles of a shuttlecock in a tube. A last shuttle put on the top of the tube will be the first out and the first in will be the last out. This structure is called LIFO (last in/first out). There are operation that can change its status and operations that check this status; a stack that is defined in terms of operations follows:

• clear() - clear the stack
• isEmpty() - check to see if the stack is empty
• push(cock) - put the element cock on the top of the stack
• pop() - take the topmost element from the stack
• top(cock) - return the topmost element in the stack without removing it

2. Illustration of a stack.

When we insert data into a stack, it is placed at the head of a queue. This means that when we remove data, it will be in reverse order. Adding 1,2,3,4 will return 4,3,2,1. Stacks aren't the most frequently used data structure, but they are extremely useful for certain tasks.3
2
1
4
3
2
1



Figure 1.1 Stack before push operation, and stack after

4
3
2
1
3
2
1



Figure 1.2 Stack before pop operation, and stack after

Java provides a stack implementation, in the form of java.util.Stack. Stack's are a subclass of java.util.Vector, and share some similarities. A Vector, after all, is a queue, and a Stack is an ordered LIFO queue.[http://www.javacoffeebreak.com/faq/faq0037.html]

3. Reference:

DATA STRUCTURES AND ALGORITHMS IN JAVA
Second Edition
Adam Drozdek