Static data structure

Introduction to Array

Arrays are the collections of similar items, called elements. Every datum element is made accessible by an index number assigned during its input. The indices of the array start from zero at the first element and increase by one at the succeeding element, and so on.

[0] [1] [2] [3] [4]

Above is a simple array that combined five pieces of information of similar nature. The integers here can be retrieved in such fashion:

A[0] = 52;

A[1] = 12;

.

.

.

Since the array is assembled in an orderly manner. Advance looping can be performed using for- or while- loop. Following are the example of the common use of array in a for-loop, array from top of the page still remains effective in this example.

function printArray()

/* output the content of the array unto the screen */

declare P integer

for P is 0 unto 4 do

output A[P]

enddo

endfunction printArray

This algorithm will result in the output of all the data elements onto the screen.

Array allows for a more efficient approach to the iterative tasks in programming, and greatly improves the flexibility of the algorithm. With these properties, extensive applications of array are steadily developed. In this study, we will study three uses of the array – quicksort, hash table, and queue.

Quicksort

Quicksort is a sorting algorithm that employs the thinking of divide and conquers. It is performed in two phases, partition phase and the sort phase. In the first phase the quicksort divides the array into two partitions, and recursively perform again on the smaller partition. This process will repeat itself until it reaches the smallest segment and no more partitioning can be performed.

The partition is done with respect to a pivot cell. Every cell will be compared to the value in this cell, those that are bigger form a high partition, and smaller ones form a low partition. At every stages of partition, the same process is repeated on a smaller group of cell. This process is demonstrated in the tracing below:

5	3	6	7	4
4	3	5	7	6
3	4	5	7	6
3	4	5	6	7

Legend
	Sorted
	High Partition
	Low Partition

This trace is enforced by this algorithm:

quicksort( dateType *a, int low, int high )

{

int pivot;

/* Termination condition! */

if ( high > low )

{

pivot = partition( a, low, high );

quicksort( a, low, pivot-1 );

quicksort( a, pivot+1, high );

}

Hash Table

Hash table is used particularly for the purpose of fast inputting. It is an array within which every element’s index is directly determined by its content. The hash function will designate an address to each input value, and that address is determined by applying a formula to the input value itself. Commonly, the formula will be one that involves modulo arithmetic. If two different values were to work out to be the name address, the clash handling will be in effect. A common clash handling will be linear probing. If the clash occurs, the new value will be placed within the next available slot found in the array.

The following example demonstrates how the hash table is constructed from the entry of these values: 6, 34, 12, 39, 40, 78, 43, and 99. The hash function is key = value % 8.

Index of A	Value
0	40
1	99
2	34
3	78
4	12
5	43
6	6
7	39

Notice even though the hash function returns 3 of value of 43, the value is not found in A[3]. Since A[3] is taken by previous input, the value will search for the next free slot, which is A[5]. This process is linear probing, used to solve the clashes in this case.

Stack

Stack is an abstract twist of either array or array list. It is data structure whose access is regulated. It works on the principle of last in first out (LIFO). Regardless of whether the structure is static or dynamic, the insertion can only be performed to the back (or top of a pile) of the list by the function PUSH, and it is also from the back of the array/list that an item is deleted and withdrew, as the POP function has done.

Tracing Algorithm of Stack

Element	[0]	[1]	[2]	[3]
Stack	(top)

“Top” is a defined variable. To add a record, or to push, it is defined as follows:

 procedure PUSH (DATA STACKTYPE)
 if TOP < UPPER then 
 TOP <-- TOP + 1
 STACK[TOP] <-- DATA
 else
 output "ERROR - Stack full"
 endPUSH
 

When a value is “pushed” unto a stack, it is added to the top of the pile. To better illustrate this, below is how a push affect an array.

Push the value 12 unto the array through

 TOP <-- TOP + 1
 STACK[TOP] <-- DATA

Element	[0]	[1]	[2]	[3]
Stack	12	(top)

The push is a procedure of insertion, whereas the pop is one of removal and retrieval. The effect of a POP function on a stack array is seen here:

Notice that the “top” is returned to its previous position while the value in that space is returned.

 DATA <-- STACK[TOP]
 TOP <-- TOP - 1

Element	[0]	[1]	[2]	[3]
Stack	12	(top)

 
The similarly structured POP algorithm performs exactly the opposite of push, which removes the item from the top. 
 
 function POP is STACKTYPE
  if TOP < LOWER then 
 output "ERROR - Stack Empty"
 else
 DATA <-- STACK[TOP]
 TOP <-- TOP - 1
 return DATA
 endPOP
 

Queue

Unlike stack, queue is a first-in-first-out structure, which means that the first entry of data gets the first exit. Despite the difference, queue shares the similarities structurally and likeness in the implementation. In queue, every data insertion and extraction is conducted with respect to a “rear” value.

Tracing Algorithm of Queue

This concept is demonstrated in the diagrams below:

15 (rear)

To enqueue an element, or in other words, to add an element, the algorithm contains such:

 
rear ß rear + 1
Q(rear) ß item

15

23 (rear)

The rear moves back one spot as the new value takes rear’s place.
 
The full text of the enqueue algorithm is included as below: 
 
 procedure ENQUEUE( DATA QTYPE)
 
 if ISFULL then
 output "ERROR - the queue is full"
 else
 Q[REAR] <-- DATA // put the item in the queue
 REAR = REAR mod N // advance pointer with a wrap if neccessary
  endprocedure ENQUEUE