Sorting algorithm

1.) a.)Description:
Insertion sort is a simple sorting algorithm, a comparison sort in which the sorted array (or list) is built one entry at a time.

b.)Run time complexity analysis:
--This is effecient and sequential.

c.)codes:
insertionSort(array A)
begin
for i := 1 to length[A]-1 do
begin
value := A[i];
j := i-1;
while j ≥ 0 and A[j] > value do
begin
A[j + 1] := A[j];
j := j-1;
end;
A[j+1] := value;
end;
end;

d.)Application: Inserting a tomatoe in a glass.
Reference:http://en.wikipedia.org/wiki/Insertion_sort

2.) a.) Description:
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.

b.)Run time complexity analysis:
-- This is observing through the first two elements then swap the lesser to greater.

c.)codes:

procedure bubbleSort( A : list of sortable items ) defined as:
do
swapped := false
for each i in 0 to length(A) - 2 inclusive do:
if A[ i ] > A[ i + 1 ] then
swap( A[ i ], A[ i + 1 ] )
swapped := true
end if
end for
while swapped
end procedure

d.)Application:

--Swapping the height of the participants of the running event.

3.)Description:
a.)Shell sort-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.


b.)Run time complexity analysis:
--This is an effective in terms of the effeciency of the sorted list.

c.) codes:
input: an array a of length n

inc ← round(n/2)
while inc > 0 do:
for i = inc .. n − 1 do:
temp ← a[i]
j ← i
while j ≥ inc and a[j − inc] > temp do:
a[j] ← a[j − inc]
j ← j − inc
a[j] ← temp
inc ← round(inc / 2.2)

d.)Application:
-- Sorting the numbers in a certain row.
Reference:http://en.wikipedia.org/wiki/Shell_sort


4.)a.) Description:
Heapsort (method) is a comparison-based sorting algorithm, and is part of the selection sort family. Although somewhat slower in practice on most machines than a good implementation of quicksort, it has the advantage of a worst-case Θ(n log n) runtime. Heapsort is an in-place algorithm, but is not a stable sort.

b.)Run time complexity analysis:
--This is a comparison of the first to elements then sort it.

c.)codes:
function heapSort(a, count) is
input: an unordered array a of length count

(first place a in max-heap order)
heapify(a, count)

end := count - 1
while 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 will
stay 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) / 2

while start ≥ 0 do
(sift down the node at index start to the proper place such that all nodes below
the 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) is
input: end represents the limit of how far down the heap
to sift.
root := start

while 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] then
child := 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)
else
return


d.)Application:
--Comparing the array of numbers in a sorted list.


5.)a.)Description:
Quick sort-Significantly faster in practice than other algorithms,because its inner loop can be effeciently implemented in the most real world data, it is possible to make design choiceswhich minimize the probability of requiring quadratic time.

b.)Run time complexity analysis:
---this is performed through finding its pivot and sort it.

c.)codes:
function quicksort(array)
var list less, greater
if length(array) ≤ 1
return array
select and remove a pivot value pivot from array
for each x in array
if x ≤ pivot then append x to less
else append x to greater
return concatenate(quicksort(less), pivot, quicksort(greater))

d.)Application:
---finding the pivot of the sticks and then sort it.

6.)a.)Description:
Merge sort or merge_sort is an O(n log n) comparison-based sorting algorithm. In most implementations it is stable, meaning that it preserves the input order of equal elements in the sorted output. It is an example of the divide and conquer algorithmic paradigm. It was invented by John von Neumann in 1945.


b.) Run time analysis:
-- Effecient and effective

c.)codes:
function merge_sort(m)
var list left, right, result
if length(m) ≤ 1
return m

// This calculation is for 1-based arrays. For 0-based, use length(m)/2 - 1.
var middle = length(m) / 2
for each x in m up to middle
add x to left
for each x in m after middle
add x to right
left = merge_sort(left)
right = merge_sort(right)
result = merge(left, right)
return result

d.) Application:
---- Merging the bundle of sticks

7.) a.) Description: 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.

b.)Run time Analysis:
---effecient and effective in sorting the list.

c.) codes:

function bucket-sort(array, n) is
buckets ← new array of n empty lists
for i = 0 to (length(array)-1) do
insert array[i] into buckets[msbits(array[i], k)]
for i = 0 to n - 1 do
next-sort(buckets[i])
return the concatenation of buckets[0], ..., buckets[n-1]

d.) Application:
---putting an array of numbers in a bucket then sort the list.

implementation of queue

/* Programmer’s name: Jeany Rose Acoja
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);
}
}

1.) Definition: Queues are dynamic collections which have some concept of order. It is the in order of entries in the queue. It emphasizes the FIFO or known as First In, First.


2.)Illustration:











3.)Reference:
http://www.cs.auckland.ac.nz/software/AlgAnim/queues.html

// Implementation of a Stack as a linked list
//purpose: To implement an array of list in a certain Stack


public class LLStack{
private java.util.LinkedList list=nw java.util.LinkedList();
public LLStack(){
}
public void clear(){
list.clear();
}
public boolean isEmpty(){
return list.isEmpty();
}
public Object topEl(){
if(isEmpty())
throw new java.util.EmptyStackException();
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();
}
}

[Data structures and algorithms in Java 2nd Edition by: Adam Drozdek]

//This is the implementation of doubly linked list

public class IntDLLNode{
public int info;
public IntDLLNode next,prev;
public IntDLLNode(int el){
this(el,null,null);
}
public IntDLLNode(int el,IntDLLNode n,IntDLLNode p){
info=el;next=n;prev=p;
}
}

// This is the class of IntDLList

public class IntDLList{
private IntDLLNode head,tail;
public IntDLList(){
head=tail=null;
}
public boolean isEmpty(){
return head==null;
}
public void addToTail(int el){
if(!isEmpty()){
tail=new IntDLLNode(el,null,tail);
tail.prev.next=tail;
}
else head=tail=new IntDLLNode(el);
}
public int removeFromTail(){
int el=tail.info;
if(head==tail)//if only one node in the list;
head=tail=null;
else{ // if more than one node in the list;
tail=tail.prev;
tail.next=null;
}
return el;
}
}
[Data Structures and algorithms in Java 2nd Edition by: Adam Drozdek]

it123

a.) Definition:
DOUBLE -ENDED LINKED LIST-it is a first and last reference. It can be the
arrangement of such qualities in every inputs that are available.

b.) illustration:

Double-ended linked list

c.)code/algorithm:

//Implementation of Double-Ended List

//Creating a new list of a link

public class Link {

private int idata;

private long ddata;
link next;

public Link(int nidata,long nddata){
iData=nidata;
dData=nddata;
}
}

//A class for a FirstLastLink

public class FirstLastLink{
private LinkFirst;
private LinkLast;

public FirstLastLink(){

first=null;
last=null;
}
public boolean isEmpty(){
return(first && last==null);
}
public void insertFirst(int nidata,long nddata){ //method in inserting in the first link
Link newLink=new Link(nidata,nddata);
newLink.next=first;
first=newLink;
}
public void insertLast(int nidata,long nddata){ //method in inserting in the last link
Link newLink=new Link(nidata,nddata);
newLink.next=last;
last=newLink;
}

public Link deleteFirst(int nidata,long nddata){
Link temp=first;
first=first.next;
return temp;
}

public Link deleteLast(int nidata,long nddata){
Link temp2=last;
last=last.next;
return temp2;
}

public void displayList(){

System.out.println(The List(first--last):");
Link current=first;
Link current2=last;
while(current && current2 !=null){
current.displayList();
current.current.next;
current.current2.next;
}
System out.println(" ");
}
}

// Application of the FirstLastApp

public class FirstLastApp{
public static void main(String[]args){

FirstLastList theList=new FirstLastList();

theList.insertFirst(1, 1,000);
theList.insertFirst(2, 2,000);
theList.insertFirst(3, 3,000);

theList.insertLast(4, 4,000);
theList.insertLast(5, 5,000);
theList.insertLast(6, 6,000);


System.out.println(theList);
theList.deleteFirst();
theList.deleteLast();

System.out.println(theList);
}
}
d.) Reference:
[jeany acoja-for the implementation of code]

IT123A0809

A.) DEFINITION-Stack (data structure)- a stack is an abstract data type and data structure based on the principle of Last In First Out (LIFO). For example, in the real world situation,a compilation of books. It emphasizes the order or sequence method of objects before it goes to another one.
And according to Adam Drozdek that "stack is a linear data structure that can be accessed only at one of its ends for storing and retrieving data".[from Java Structures and algorithms in java]


B.) Illustration:











C.)REFERENCES:
http://en.wikipedia.org/wiki/Stack_(data_structure)
http://en.wikipedia.org/wiki/File:Data_stack.svg