Bubble sort
- is a simple sorting alrorithms . 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.

Run-time complexity Analysis:
This is observing through the first two elements then swap the lesser to greater. 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.

Codes:
procedure bubbleSort( A : list of sortable items ) defined as:doswapped := falsefor each i in 0 to length(A) - 2 inclusive do:if A[ i ] > A[ i + 1 ] thenswap( A[ i ], A[ i + 1 ] )swapped := trueend ifend forwhile swappedend procedure

Application:For example, swapping the height of the participants of the running event.

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

Insertion sort
- is a simple sorting algorithm that is relatively efficient for small lists and mostly-sorted lists, and often is used as part of more sophisticated algorithms. It works by taking elements from the list one by one and inserting them in their correct position into a new sorted list. In arrays, the new list and the remaining elements can share the array's space, but insertion is expensive, requiring shifting all following elements over by one.

Run-time Complexity Analysis:This is efficient and sequential.

Codes:insertionSort(array A)beginfor i := 1 to length[A]-1dobeginvalue := A[i];j := i-1;while j ≥ 0 and A[j] > value dobeginA[j + 1] := A[j];j := j-1;end;A[j+1] := value;end;end;

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

Reference:http://en.wikipedia.org/wiki/Sorting_algorithm#Insertion_sort

Shell sort
- was invented by Donald Shell in 1959. It improves upon bubble sort and insertion sort by moving out of order elements more than one position at a time. One implementation can be described as arranging the data sequence in a two-dimensional array and then sorting the columns of the array using insertion sort. Although this method is inefficient for large data sets, it is one of the fastest algorithms for sorting small numbers of elements (sets with fewer than 1000 or so elements). Another advantage of this algorithm is that it requires relatively small amounts of memory.
Run-time Complexity Analysis:
This is an effective in terms of the efficiency of the sorted list.
Codes:
input: an array a of length ninc ← round(n/2)while inc > 0 do:for i = inc .. n − 1 do:temp ← a[i]j ← iwhile j ≥ inc and a[j − inc] > temp do:a[j] ← a[j − inc]j ← j − inca[j] ← tempinc ← round(inc / 2.2)
Application: Sorting the numbers in a certain row.
Reference:http://en.wikipedia.org/wiki/Sorting_algorithm#Shell_sort

Merge sort
- takes advantage of the ease of merging already sorted lists into a new sorted list. It starts by comparing every two elements (i.e., 1 with 2, then 3 with 4...) and swapping them if the first should come after the second. It then merges each of the resulting lists of two into lists of four, then merges those lists of four, and so on; until at last two lists are merged into the final sorted list. Of the algorithms described here, this is the first that scales well to very large lists, because its worst-case running time is O(n log n).

Run-time Complexity Analysis:
Efficient and effective

Code:
function merge_sort(m)var list left, right, resultif length(m) ≤ 1return m// This calculation is for 1-based arrays.For 0-based, use length(m)/2 - 1.var middle = length(m) / 2for each x in m up to middleadd x to leftfor each x in m after middleadd x to rightleft = merge_sort(left)right = merge_sort(right)result = merge(left, right)return result

Application:
Merging a bundle of something like sticks and other.

Reference:
en.wikipedia.org/wiki/Merge_sort
http://en.wikipedia.org/wiki/Sorting_algorithm#Merge_sort

Heapsort
- is a much more efficient version of selection sort. It also works by determining the largest (or smallest) element of the list, placing that at the end (or beginning) of the list, then continuing with the rest of the list, but accomplishes this task efficiently by using a data structure called aheap, a special type of binary tree. Once the data list has been made into a heap, the root node is guaranteed to be the largest element. When it is removed and placed at the end of the list, the heap is rearranged so the largest element remaining moves to the root. Using the heap, finding the next largest element takes O(log n) time, instead of O(n) for a linear scan as in simple selection sort. This allows Heapsort to run in O(n log n) time.

Run-time Complexity Analysis:
It has the advantage of a worst-case Θ(n log n) runtime. It is an in-place algorithm, but is not a stable sort.
Codes:
function heapSort(a, count) isinput: an unordered array a of length count(first place a in max-heap order)heapify(a, count)end := count - 1while end > 0 do(swap the root(maximum value) of the heap with the last element of the heap)swap(a[end], a[0])(decrease the size of the heap by one so that the previous max value willstay in its proper placement)end := end - 1(put the heap back in max-heap order)siftDown(a, 0, end)function heapify(a,count) is(start is assigned the index in a of the last parent node)start := (count - 2) / 2while start ≥ 0 do(sift down the node at index start to the proper place such that all nodes belowthe start index are in heap order)siftDown(a, start, count-1)start := start - 1(after sifting down the root all nodes/elements are in heap order)function siftDown(a, start, end) isinput: end represents the limit of how far down the heapto sift.root := startwhile root * 2 + 1 ≤ end do (While the root has at least one child)child := root * 2 + 1 (root*2+1 points to the left child)(If the child has a sibling and the child's value is less than its sibling's...)if child + 1 ≤ end and a[child] < a[child + 1] thenchild := child + 1 (... then point to the right child instead)if a[root] < a[child] then (out of max-heap order)swap(a[root], a[child])root := child (repeat to continue sifting down the child now)elsereturn

Application:
Comparing the array of numbers in a sorted list.
Reference:
http://en.wikipedia.org/wiki/Sorting_algorithm#Heapsort

Quicksort
- is a divide and conquer algorithm which relies on a partition operation: to partition an array, we choose an element, called a pivot, move all smaller elements before the pivot, and move all greater elements after it. This can be done efficiently in linear time andin-place We then recursively sort the lesser and greater sublists. Efficient implementations of quicksort (with in-place partitioning) are typically unstable sorts and somewhat complex, but are among the fastest sorting algorithms in practice.
Run-time Complexity Analysis:
this is performed through finding its pivot and sort it.typically unstable and somewhat complex but among the fastest sorting algorithms.
Codes:
function quicksort(array)var list less, greaterif length(array) ≤ 1return arrayselect and remove a pivot value pivot from arrayfor each x in arrayif x ≤ pivot then append x to lesselse append x to greaterreturn concatenate(quicksort(less), pivot, quicksort(greater))
Application:
finding the pivot of a given example and then sort it.
Reference:
http://en.wikipedia.org/wiki/Quicksort

Bucket sort

or bin sort, is a sorting algorithm that works by partitioning an array into a number of bucket . 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. Since bucket sort is not a comparison sort, the Ω(n log n) lower bound is inapplicable. Estimates involve the number of buckets.
Run-time Complexity Analysis:
♥efficient and effective in sorting the list.
Codes:
function bucket-sort(array, n) isbuckets ← new array of n empty listsfor i = 0 to (length(array)-1) doinsert array[i] into buckets[msbits(array[i], k)]for i = 0 to n - 1 donext-sort(buckets[i])return the concatenation of buckets[0], ..., buckets[n-1]
Application:
Given an array, put the array of numbers in a bucket where they must be placed then sort the list.
Reference:commons.wikimedia.org/wiki/File:Bucket_sort_2.png
http://en.wikipedia.org/wiki/Bucket_sort

 My References:

1. bubble sort: http://en.wikipedia.org/wiki/Bubble_sort
2. insertion sort:  http://en.wikipedia.org/wiki/Insertionsort
3. shell sort: http://en.wikipedia.org/wiki/Shell_sort
4. heap sort: http://en.wikipedia.org/wiki/Heap_sort
5. merge sort: http://en.wikipedia.org/wiki/Merge_sort
6. quick sort: http://en.wikipedia.org/wiki/Quick_sort
7. bucket sort: http://en.wikipedia.org/wiki/Bucket_sort

Code Implementation of Queue

/* Programmer’s name:Pauline Vernadeth Magno
Name of Program: Queue implementation
Date Started: March 9, 2009
Date Finished : March 12, 2009
Instructor : Mr. Dony Dongiapon
Course: IT 123: Data Structures
Objective: To be able to make a program that implements a queue data structure in a linked list
*/
Concept: List of Courses Offered in the College

//class constructor
class Queue{
public int coursenum;
public String coursename;
public int unitnum;
public String deptname;
public Queue next;


public Queue (int Cnum, String Cname, int Unum, String Dname; )
{

coursenum=Cnum;
coursename=Cname;
unitnum=Unum;
deptname=Dname;
}


//displaying the elements on the list
public void displayQueue()
{
System.out.print(coursenum +” “ + deptname +” “ +” “+unitnum+ “ “ +: + coursename)
}
}


/*a separate class which contains the ,methods that would be used in implementing the program */
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 Cnum, String Cname, int Unum, String Dname; )

{
Queue newQueue= new Queue (int Cnum, String Cname, int Unum, String Dname )

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


//deleting an element on the queue
public void Dequeue (int Cnum)
{
Queue newQueue=new Queue (int Cnum, String Cname, int Unum, String Dname )

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, “BSIT”, 118, “ICSD” )

theQueue.enqueue(2, “BSN”, 368, “ND”);
System.out.println(theQueue);

theQueue.dequeue(2);

System.out.println(theQueue);



System.out.println(theQueue);
}
}

Concept:

Queue

            A First In First Out Data Structure, it means that the first element added to the queue

will be the first one to be removed. A queue is an example of linear data structure. [Wiki]

Stack Code Implementation

/* Programmer: Pauline Vernadeth Magno
Program name: A Stack Code Implementation
Purpose: To implement a Stack Code.
Instructor: Dony Dongiapon
Subject: IT123 Data Structures*/

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

Doubly Linked List Illustration

Double-ended Illustration

Doubly Linked list

A:Concept/Definition:

••a doubly linked list is not an abstract data type, but only an implementation type. This fact does not prevent doubly linked lists from being extremely useful, however.

As with simply linked lists, we assume that the elements on the list are in the form of pointers, so that we respect uniform reference semantics. There is another application that makes it a "doubly linked list" [TUTORIALS]

••its because it has a pointer or reference to the previous e link, thus it makes it more complicated but at least, you can go back to the previous list, unlike in a Singly linked list.

B:Illustration:

C: Java Code:

//constructor class

class Link {

public int iData;

public Link next;

public Link previous;

public Link(int id) {

iData = id;

}

public String toString() {

return "{" + iData + "} ";

}

}

//a class that has the methods or operation of doubly linked list

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;

}

public String toString() {

String str = "List (first-->last): ";

Link current = first;

while (current != null) {

str += current.toString();

current = current.next;

}

System.out.println("");

System.out.print("List (last-->first): ");

current = last;

while (current != null) {

str += current.toString();

current = current.previous;

}

return str;

}

}

//main class that executes the operation on the doubly linked lists

public class MainClass {

public static void main(String[] args) {

DoublyLinkedList theList = new DoublyLinkedList();

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.deleteLast();

theList.deleteKey(11);

System.out.println(theList);

theList.insertAfter(22, 77);

theList.insertAfter(33, 88);

System.out.println(theList);

}

}

D:References:

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

[TUTORIALS]

Double Ended Lists

A) Definition/Concept:

A double ended list has references to the first and last element of the linked list. It will be easy for the insertion and deletion operations because there is an access to the first and last element of the list..

[JAVA_TUTORIALS]

B) Illustration:

C) Code:

Double-Ended Lists: list with first and last references

//constructor
class Link {
public int iData;

public Link next;

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

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

//methods/operations of a double ended

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

//main class/application of the methods
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);
}
}

References:

[JAVA_TUTORIALS]

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

IT123A0809

Stack

A.Definition/Concept

Stack an abstract data type and data structure based on LIFO or the Last In First Out. It is used extensively at every level of modern computer system. Example of this, a modern PC uses stacks at the architecture level, which are used in the basic design of an operating system for interrupt handling and operating system function calls.[wiki]

B. Illustration

C. References

 [1]  http://en.wikipedia.org/wiki/File:Data_stack.svg
 [2] http://en.wikipedia.org/wiki/Stack_(data_structure)