DATA STRUCTURE AND ALGORITHMS
Data Structure
Computer Science is the study of data, its representation and transformation by Computer. For every data object, we consider the class of operations to be performed and then the way to represent the object so that these operations may be efficiently carried out. We require two techniques for this:
– Devise alternative forms of data representation
– Analyses the algorithm which operates on the structure.
These are several terms involved above which we need to know carefully before we proceed. These include data structure, data type and data representation.
A data type is a term which refers to the kinds of data that variables may hold. With every programming language there is a set of built-in data types. This means that the language allows variables to name data of that type and provides a set of operations which meaningfully manipulates these variables. Some data types are easy to provide because they are built-in into the computer’s machine language instruction set, such as integer, character etc. Other data types require considerably more efficient to implement. In some languages, these are features which allow one to construct combinations of the built-in types ( like structures in ‘C’). However, it is necessary to have such mechanism to create the new complex data types which are not provided by the programming language. The new type also must be meaningful for manipulations. Such meaningful data types are referred as abstract data type.
ABSTRACT DATA TYPE:
An abstract data type can be assumed as a mathematical model with a collection of operations defined on that model i.e. an ADT is a new data type derived or created from basic or built in data type based on a particular logical or mathematical model.
For Example:
Set of integers consisting of different numbers may be an ADT. A set is a combination of more than one integer, but the operations on set is a generalized operation of different integers such as union, intersection, product, and difference. Above ADT or set encapsulates different mathematical operations and generalizes operations on ADT.
Basic Properties of ADT are: –
(i) Encapsulation and
(ii) Generalization
(i) Encapsulation and
(ii) Generalization
Let us consider the following example:
Struct student
{
int rno;
char name[21],branch[11]
int marks;.
};
The above structure can be used to collect or retrieve the information of a student. The structure can be called as ADT if all the operations on student can be performed using the structure.
DATA STRUCTURE:
An implementation of abstract data type is data structure i.e. a mathematical or logical model of a particular organization of data is called data structure.
Thus, a data structure is the portion of memory allotted for a model, in which the required data can be arranged in a proper fashion.
TYPES:-
A data structure can be broadly classified into
(i) Primitive data structure
(ii) Non-pr
imitive data structure
(i) Primitive data structure
(ii) Non-pr
imitive data structure
(i) Primitive data structure
The data structures, typically those data structure that are directly operated upon by machine level instructions i.e. the fundamental data types such as int, float, double in case of ‘c’ are known as primitive data structures.
(ii) Non-primitive data structure
The data structures, which are not primitive are called non-primitive data structures.
There are two types of-primitive data structures.
(a) Linear Data Structures:-
A list, which shows the relationship of adjacency between elements, is said to be linear data structure. The most, simplest linear data structure is a 1-D array, but because of its deficiency, list is frequently used for different kinds of data.
(b) Non-linear data structure:–
A list, which doesn’t show the relationship of adjacency between elements, is said to be non-linear data structure.
Linear Data Structure:
A list is an ordered list, which consists of different data items connected by means of a link or pointer. This type of list is also called a linked list. A linked list may be a single list or double linked list.
∙ Single linked list: – A single linked list is used to traverse among the nodes in one direction.
∙ Double linked list: – A double linked list is used to traverse among the nodes in both the directions.
A linked list is normally used to represent any data used in word-processing applications, also applied in different DBMS packages.
A list has two subsets. They are: –
∙ Stack: – It is also called as last-in-first-out (LIFO) system. It is a linear list in which insertion and deletion take place only at one end. It is used to evaluate different expressions.
∙ Queue: – It is also called as first-in-first-out (FIFO) system. It is a linear list in which insertion takes place at once end and deletion takes place at other end. It is generally used to schedule a job in operating systems and networks.
Non-linear data structure:-
The frequently used non-linear data structures are
(a) Trees : – It maintains hierarchical relationship between various elements
(b) Graphs : – It maintains random relationship or point-to-point relationship between various elements.
OPERATION ON DATA STRUCTURES: –
The four major operations performed on data structures are:
(i) Insertion : – Insertion means adding new details or new node into the data structure.
(ii) Deletion : – Deletion means removing a node from the data structure.
(iii) Traversal : – Traversing means accessing each node exactly once so that the nodes of a data structure can be processed. Traversing is also called as visiting.
(iv) Searching : – Searching means finding the location of node for a given key value.
Apart from the four operations mentioned above, there are two more operations occasionally performed on data structures. They are:
(a) Sorting : – Sorting means arranging the data in a particular order.
(b) Merging : – Merging means joining two lists.
REPRESENTATION OF DATA STRUCTURES:-
Any data structure can be represented in two ways. They are: –
(i Sequential representation
( Linked representation
(i) Sequential representation: – A sequential representation maintains the data in continuous memory locations which takes less time to retrieve the data but leads to time complexity during insertion and deletion operations. Because of sequential nature, the elements of the list must be freed, when we want to insert a new element or new data at a particular position of the list. To acquire free space in the list, one must shift the data of the list towards the right side from the position where the data has to be inserted. Thus, the time taken by CPU to shift the data will be much higher than the insertion operation and will lead to complexity in the
algorithm. Similarly, while deleting an item from the list, one must shift the data items towards the left side of the list, which may waste CPU time.
algorithm. Similarly, while deleting an item from the list, one must shift the data items towards the left side of the list, which may waste CPU time.
Drawback of Sequential representation: –
The major drawback of sequential representation is taking much time for insertion and deletion operations unnecessarily and increasing the complexity of algorithm.
(ii) Linked Representation: – Linked representation maintains the list by means of a link between the adjacent elements which need not be stored in continuous memory locations. During insertion and deletion operations, links will be created or removed between which takes less time when compared to the corresponding operations of sequential representation.
Because of the advantages mentioned above, generally, linked representation is preferred for any data structure.
Algorithm Analysis:
An algorithm is a finite set of instructions that, if followed, accomplishes a particular task. In addition, all algorithms must satisfy the following criteria.
1. Input
2. Output
3. Definiteness
4. Finiteness
5. Effectiveness
The criteria 1 & 2 require that an algorithm produces one or more outputs & have zero or more input. According to criteria 3, each operation must be definite such that it must be perfectly clear what should be done. According to the 4th criteria algorithm should terminate after a finite no. of operations. According to 5th criteria, every instruction must be very basic so that it can be carried out by a person using only pencil & paper.
There may be many algorithms devised for an application and we must analyses and validate the algorithms to judge the suitable one.
To judge an algorithm the most important factors is to have a direct relationship to the performance of the algorithm. These have to do with their computing time & storage requirements ( referred as Time complexity & Space complexity).
Space Complexity:
The space complexity of an algorithm is the amount of memory it needs to run.
Time Complexity:
The time taken by a program is the sum of the compiled time & the run time. The time complexity of an algorithm is given by the number of steps taken by the algorithm to compute the function it was written for.
[NOTE: example on how to calculate computing time will be given later]
STORAGE STRUCTURE FOR ARRAYS
Array is set of homogenous data items represented in contiguous memory locations using a common name and sequence of indices starting from 0. Array is a simplest data structure that makes use of computed address to locate its elements. An array size is fixed and therefore requires a fixed number of memory locations.
Suppose A is an array of n elements and the starting address is given then the location and element I will be
LOC(Ai) = Base address of A + (i – 1) * W
Where W is the width of each element.
A multidimensional array can be represented by an equivalent one-dimensional array. A two dimensional array consisting of number of rows and columns is a combination of more than 1 one-dimensional array. A 2 dimensional array is referred in two different ways. Considering row as major order or column as major order any array may be used to refer the elements.
If we consider the row as major order then the elements are referred row by row whose addressing function may be
LOC(Arc) = Base address of A + [(r-1) * N + (c-1)] * W
Where r and c are subscripts. N is number of columns per row. W is the width of each element.
If we consider the column as major order then the elements are referred column by column.
Sparse Matrices
Matrices with relatively high proportion of zero or null entries are called sparse matrices.
When matrices are sparse, then much space and computing time could e saved if the non-zero entries were stored explicitly i.e. ignoring the zero entries the processing time and space can be minimized in sparse matrices.
In the above matrix we have 6 rows and 7 columns. There are 5 nonzero entries out of 42 entries. It requires an alternate form to represent the matrix without considering the null entries.
The alternate data structure that we consider to represent a sparse matrix is a triplet. The triplet is a two dimensional array having t+1 rows and 3 columns. Where, t is total number of nonzero entries.
The first row of the triplet contains number of rows, columns and nonzero entries available in the matrix in its 1st, 2nd and 3rd column respectively. Second row onwards it contains the row subscript, column subscript and the value of the nonzero entry in its 1st, 2nd and 3rd column respectively.
Let us represent the above matrix in the following triplet of 6 rows and 3 columns
6 | 7 | 5 |
1 | 4 | 24 |
2 | 6 | 5 |
4 | 5 | 9 |
5 | 5 | 18 |
6 | 5 | 8 |
The above triplet contains only non-zero details by reducing the space for null entries.
[Follow the algorithms taught in class]
Stacks
A stack is a linear data structure in which an element may be inserted or deleted only at one end called the top end of the stack i.e. the elements are removed from a stack in the reverse order of that in which they were inserted into the stack.
A stack follows the principle of last-in-first-out (LIFO) system. According to the stack terminology, PUSH and POP are two terms used for insert and delete operations.
Representation of Stacks
A stack may be represented by means of a one way list or a linear array. Unless, otherwise stated, each of the stacks will be maintained by a linear array STACK, A variable TOP contains the location of the top element of the stack. A variable N gives the maximum number elements that can be held by the stack. The condition where TOP is NULL, indicate that the stack is empty. The condition where TOP is N, will indicate that the stack is full.
[Follow the push and pop algorithms discussed in class]
Application of Stacks
There are two important applications of stacks.
a) Recursion
b) Arithmetic Expression
Recursion
Recursion is and important facility in many programming languages. There are many problems whose algorithmic description is best described in a recursive manner.
A function is called recursive if the function definition refers to itself or does refers to another function which in turn refers back to the same function. In-order for the definition not to be circular, it must have the following properties:
(i) There must be certain arguments called base values, for which the function does not refer to itself.
(ii) Each time the function does refer to itself, the argument of the function must be closer to a base value.
A recursive function with those two properties is said to be well defined.
Let us consider the factorial of a number and its algorithm described recursively:
We know that N! = N * (N-1)!
(N-1)! = N-1 * (N-2)! and so on up to 1.
FACT(N)
1. if N=1
return 1
2. else
return N * FACT(N-1)
3. end
Let N be 5.
Then according to the definition FACT(5) will call FACT(4), FACT(4) will call FACT(3), FACT(3) will call FACT(2), FACT(2) will call FACT(1). Then the execution will return back by finishing the execution of FACT(1), then FACT(2) and so on up to FACT(5) as described below.
1) 5! = 5 * 4!
2) 4! = 4 * 3!
3) 3! = 3 * 2!
4) 2! = 2 * 1!
5) 1! = 1
6) 2! = 2 * 1 = 2
7) 3! = 3 * 2 = 6
8) 4! = 4 * 6 = 24
9) 5! = 5 * 24 = 120
From above example it is clear that every sub function contain parameters and local variables. The parameters are the arguments which receive values from objects in the calling program and which transmit values back to the calling program. The sub-function must also keep track of the return address in the calling program. This return address is essential since control must be transferred back to its proper place in the calling program. After completion of the sub-function when the control is transferred back to its calling program, the local values and returning address is no longer needed. Suppose our sub-program is a recursive one, when it call itself, then current values must be saved, since they will be used again when the program is reactivated.
Thus, in recursive process a data structure is required to handle the data of ongoing called function and the function which is called at last must be processed first. i.e the data accessed last must be processed fist i.e Last in first out principle. So, a stack may be suitable data structure that follows LIFO to implement recursion.
Arithmetic Expression
This section deals with the mechanical evaluation or compilation of infix expression. The stack is find to be more efficient to evaluate an infix arithmetical expression by first converting to a suffix or postfixes expression and then evaluating the suffix expression. This appro
ach will eliminate the repeated scanning of an infix expressions in order to obtain its value.
ach will eliminate the repeated scanning of an infix expressions in order to obtain its value.
A normal arithmetic expression is normally called as infix expression. E.g A+B
A Polish mathematician found a way to represent the same expression called polish notation or prefix expression by keeping operators as prefix. E.g +AB
We use the reverse way of the above expression for our evaluation. The representation is called Reverse Polish Notation (RPN) or postfixes expression. E.g. AB+
The arithmetic expression evaluation is performed in two phases, they are
? Conversion of infix to postfixes expression
? Evaluation of postfixes expression
[Follow the algorithms and examples discussed in class]
Queue
Queue is a linear data structure in which insertion can take place at only one end called rear end and deletion can take place at other end called top end. The front and rear are two terms used to represent the two ends of the list when it is implemented as queue. Queue is also called First In First Out (FIFO) system since the first element in queue will be the first element out of the queue.
Like stacks, queues may be represented in various ways, usually by means of one way list or linear arrays. Generally, they are maintained in linear array QUEUE. Two pointers FRONT and REAR are used to represent front and last element respectively. N may be the size of the linear array. The condition when FRONT is NULL indicate that the queue is empty. The condition when REAR is N indicated overflow.
[Follow the algorithms for insert and delete discussed in class]
Circular Queue
The linear arrangement of the queue always considers the elements in forward direction. In the above two algorithms, we had seen that, the pointers front and rear are always incremented as and when we delete or insert element respectively. Suppose in a queue of 10 elements front points to 4th element and rear points to 8th element as follows.
Later, when we try to insert some elements, then according to the logic when REAR is N then it encounters an overflow situation. But there are some elements are left blank at the beginning part of the array. To utilize those left over spaces more efficiently, a circular fashion is implemented in queue representation. The circular fashion of queue reassigns the rear pointer with 1 if it reaches N and beginning elements are free and the process is continued for deletion also. Such queues are called Circular Queue.
[Follow the CQINSERT and C DELETE algorithm]
Types of QUEUE
There are two types of Queue
? Priority Queue
? Double Ended Queue
Priority Queue
A priority queue is a collection of elements such that each element has been assigned a priority value such that the order in which elements are deleted and processed comes from the following rules
1. An element of higher priority is processed before any element of lower priority.
2. Two elements with the same priority are processed according to the order in which they were added to the queue.
There are various ways of maintaining a priority queue in memory. One is using one way list. The sequential representation is never preferred for priority queue. We use linked Queue for priority Queue.
Double Ended Queue
A Double Ended Queue is in short called as Dequeue (pronounced as Deck or dequeue). A dequeue is a linear queue in which insertion and deletion can take place at either ends but not in the middle.
There are two types of Dequeue.
1. Input restricted Dequeue
2. Output restricted Dequeue
A Dequeue which allows insertion at only at one end of the list but allows deletion at both the ends of the list is called Input restricted Dequeue.
A Dequeue which allows deletion at only at one end of the list but allows insertion at both the ends of the list is called Output restricted Dequeue.
Garbage Collection and Compaction
Garbage collection is the process of collecting all unused nodes and returning them to available space. This process is carried out in two phases:
In first phase, known as marking phase, all nodes in use are marked.
In second phase, all unmarked nodes are returned to the available space list.
The second phase is trivial when all nodes are of a fixed size. In this case, the second phase requires only the examination of each node to see whether or not it has been marked. In this situation it is only the first or marking phase that is of any interest in designing algorithm. When variable size nodes are in use, it is desirable to compact memory so that all free nodes form a contiguous block of memory. In this case, the second phase if referred to as memory compaction. Compaction of disk space to reduce avera
ge retrieval time is desirable even for fixed size.
ge retrieval time is desirable even for fixed size.
Linked List (One way List)
We understood that the sequential representation of the ordered list is expensive while inserting or deleting arbitrary elements stored at fixed distance in a fixed memory.
The linked representation reduces the expense because the elements are not stored at fixed distance and they are represented randomly and the operations such as insertion and deletion are required change in link rather than movement of data.
A linked list is a linked representation of the ordered list. It is a linear collection of data elements termed as nodes whose linear order is given by means of link or pointer. Every node consist of two parts. The first part is called INFO, contains information of the data and second part is called LINK, contains the address of the next node in the list. A variable called START, always points to the first node of the list and the link part of the last node always contains null value. A null value in the START variable denotes that the list is empty.
INFO LINK
Along with the linked list in the memory, a special list is maintained which consists of list of unused memory cells or unused nodes. This list is called list of available space or availability list or list of free storage or free storage list or free pool. A variable AVAIL is used to store the starting address of the availability list.
Sometimes, during insertion, there may not be available space for inserting a data into a data structure, then the situation is called OVERFLOW. Programmers generally handle the situation by checking whether AVAIL is NULL or not.
The situation where one wants to delete data from a data structure that is empty is called UNDERFLOW. The situation is encountered when START is NULL.
Header Linked List :
A header linked list is a linked list, which always contains a special node called the header node at the beginning of the list. The header node contains the overall information of the list, which is frequently required for many operations and useful while looking for such information. There are two kinds of header lists.
a) A grounded header list is a header list where the last node contains the null pointer.
b) A circular header list is a header list where the last node points back to the header node.
Circular Linked List :
A linked list is called circular if the last node contains the address of first node or header list. The advantage of circular linked list is it requires minimum time to traverse the nodes which are already traversed, with out moving to starting node.
Linked Stack :
The problems with array-based stacks are that the size must be determined at compile time. Instead, let’s use a linked list, with the stack pointer pointing to the top element, let fresh be the new node. To push a new element on the stack, we must do:
fresh->next = top;
top = fresh;
To pop an item from a linked stack, we just have to reverse the operation.
p = top;
top = top->next;
Linked Queues
Queues in arrays were ugly because we need wrap around for circular queues. Linked lists make it easier. We need two pointers to represent our queue – one to the rear for enqueue operations, and one to the front for dequeue operations.
Note that because both operations move forward through the list, no back pointers are necessary!
Application of Linked List:
1) Polynomial Manipulation:
A polynomial has multiple terms with same information such as coefficient and powers. Each term of a polynomial is treated as a node of a list and normally a linked list used to represent a polynomial. The implementation of polynomial addition is the only operation that is discussed many place. Multiplication of polynomials can be obtained by performing repeated additions.
Each polynomial is stored in decreasing order of by term according to the criteria of that polynomial. i.e. The term whose powers are more are stored at first node and the least power term is stored at last. This ordering of polynomials makes the addition of polynomials easy. In fact two polynomials can be added or multiplied by scanning each of their terms only once.
[Follow the algorithms discussed in class]
2) Linked Dictionary:
An important part of any compiler is the construction and maintenance of a dictionary containing names and their associated values. Such dictionary is also called Symbol Table. There may be several symbols corresponding to variable names, labels, literals, etc.
The constraints, which must be considered in the design of the symbol tables, are processing time and memory space. There are many phases associated with the construction of symbol tables. The main phases are building and referencing.
It is very easy to construct a very fast symbol table system, provided that a large section of memory is available. In such case a unique address is assigned to each name. The most straightforward method of accessing a symbol table is linear search technique. This method involves arranging the symbols sequentially in memory via an array or by using a simple linked list. An insertion can be easily handled by adding new element to the end of the list. When it is desired to access a particular symbol, the table is searched sequentially from its beginning until it is found. It will take n/2 comparisons to find a particular symbol. The insertion mechanism is fast but the referencing is extremely slow. The referencing will be fast if we use binary search technique. To implement a binary search on symbol table a tree representation is used.
Double Linked List (Two way List)
Since the single linked list contains only one single pointer that points to the next of the linked list, there is only one way traversal. So, the reverse direction is not possible, in the single linked list.
For bi-directional movement, a two-way list or double liked list is considered. IT is a linear collection of data elements, called nodes. Where each node is divided into three parts: INFO, PRIOR, and NEXT. The INFO part contains the information of the node and PRIOR and NEXT are the pointers refers to predecessor node and successor node address respectively. The list also has two pointers: START and LAST. START points to the first node of the list where as LAST points to last node of the list. The PRIOR part of the first node and NEXT part of the last node contains always null value.
Difference between single linked list and double linked list :
The Single linked list has only one advantage, that it can traverse a list in one direction. That means one cannot get the address of its predecessor node. i.e. When we look for any previous information of the list during operations then one has to traverse again from the start node of the one way list. Which uses an extra pointer and additional searching time. But in case double linked list we can have the address of the next as well as previous node. So, while we look for previous node address, we can obtain through prior part of the two-way list which need not require extra pointer or takes less time than that of the single linked list. So apart from the bi-directional movement facility, the two-way list also saves the time and space during traversal operation.
TREES
A tree is a nonlinear data structure and is generally defined as a nonempty finite set of elements, called nodes such that:
1. T contains a distinguished node called root of the tree.
2. The remaining elements of tree form an ordered collection of zero or more disjoint subsets called sub tree.
BINARY TREE:
A binary tree is defined as a finite set of elements, called nodes, such that:
1) Tree is empty (called the null tree or empty tree) or
2) Tree contains a distinguished node called root node, and the remaining nodes form an ordered pair of disjoint binary trees
In the above tree R is the root node and T1 and T2 are called sub-trees. T1 and T2 are left and right successor of R. The node R is called parent node and T1 and T2 are called children. All lower level nodes are called descendants and upper level nodes are called ancestors of their descendants. The line drawn between parent and child is called an edge or arc where as the line(s) between and ancestor and descendant is called path. A node without any children is called a terminal or leaf node and all others are called non-terminal or non-leaf node. A path ending with a leaf is called a branch.
Each node in a binary tree is assigned a level number, as follows. The root node is assigned the level number 0, and every other node is assigned a level number, which are 1 more than the level number of its parent. The nodes of same level number are said to belong to same generation. Nodes of same parent are called siblings.
The depth or height of a tree is the maximum level number of the tree or maximum number of nodes in a branch of a tree.
Two trees are said to be similar if they have the same structure and are said to be copies if they are similar and if they have same contents at corresponding nodes.
Complete Binary Tree:
A binary tree is said to be complete if all its level except possibly the last, have maximum number of possible nodes, and if all the nodes at the last level appear as far left as possible.
Full binary tree:
A binary tree said to be full if all its level have maximum number of possible node.
Extended Binary Tree (Strictly Binary Tree or 2-tree):
A binary tree is said to be Extended binary tree if each node has either 0 or 2 children. In this case the leaf nodes are called external nodes and the node with two children are called internal nodes.
Skewed Tree:
A tree is called Skew if all the nodes of a tree are attached to one side only. i.e A left skew will not have any right children in its each node and right skew will not have any left child in its each node.
Binary Search Trees:
A tree is called binary search tree if each node of the tree has following properties.
The value at a node is greater than every value in the left sub-tree and is less than every value in the right sub-tree.
Heap:
A binary tree is also called a heap and there are two types of heap. The are Max Heap and Min Heap. A heap is called maximum heap if value of a node is greater than or equal to each of its descendant node. A heap is called minimum heap if value of a node is less than or equal to each of its descendant node.
Representation of Binary Search Tree:
Sequential Representation:
The sequential representation of tree stores data in an array as per the following rules:
1. The root node is stored in 1st position.
2. Every left and right child of a parent node at location k will be stored in (2*K)th position and (2*K+1)th position respectively.
The following example shows the representation of binary tree in an array.
Suppose an array is representing a tree then its tree representation will be drawn using the same rule and an example is shown bellow.
Linked Representation of Tree:
The Linked representations of tree, maintains three parallel arrays. An INFO array contains the data of each node, LEFT array contains the location of left child and RIGHT array contains location of right child. A ROOT pointer points to the root node of the tree.
Header Nodes:
When a binary tree is maintained in memory by means of a linked representation. Sometimes an extra, special node, called a header node, is added to the beginning of the tree. When this extra node is used, the tree pointer variable, which is called HEAD, will point to the header node, and the left pointer of the header node will point to the root. Generally, the header node of any tree contains the general or overall information of the tree, which is required frequently in the operation of the tree. For example, number of employees present in employee tree, number nodes present in a tree, cumulative values of all the nodes etc. so that while accessing such information the nodes of the tree need not be traversed.
Threads and Threaded Binary Tree:
Approximately half of the entries in the pointer fields Left and right of any binary tree contains null elements. Replacing the null entries by some other type of information may more efficiently use this space. Specifically, we will replace certain null entries by special pointers, which point to nodes higher in the tree. These special pointers are called threads and the tree is called threaded binary tree.
There are many ways to thread a binary tree, but each threading will correspond to a particular traversal of tree. Unless otherwise stated, threading will correspond to in-order traversal.
There are two types of threading:
? One way threading
? Two way threading
In one way threading, either left pointer or right pointer will be used for threading. When left pointer used to point the predecessor node of the tree according to in-order traversal, then the threading is called left-in threading. When a right pointer is used to point the successor node according to in-order traversal, then the threading is called right-in threading.
In two way threading both left and right pointers are used to point predecessor and successor nodes of the tree according to in-order traversal.
Height Balanced Tree(AVL Tree):
Adelson-Velskii and Land in 1962 introduced a binary tree structure that is balanced with respect to heights of the su
b-trees. As a result of the balanced nature of this type of tree, dynamic retrievals can be performed in less time. At the same time an identifier may be inserted and deleted in that tree in less time.
b-trees. As a result of the balanced nature of this type of tree, dynamic retrievals can be performed in less time. At the same time an identifier may be inserted and deleted in that tree in less time.
Definition: A empty tree is called height balanced. If the tree is nonempty binary tree T with TL and TR as its left and right sub-trees, then tree is called height balanced off
a) hL – hR is –1, or 0 , or1 where hL andhR are heights of left sub-tree TL and right sub-trees TR respectively.
b) TL and TR are height balanced.
Generally, while inserting or deleting an identifier in tree we balance the tree. Balancing of a tree is carried out using essentially two kind of rotation left rotation and r
ight rotation. When a tree at a node has Balance Factor less –1 then the tree at that node is considered to be right heavy. To balance the right heavy tree the tree at that node rotated towards left. Similarly, if the tree is at a node is heaving Balance Factor more than 1 will be considered as left heavy. To balance the left heavy tree, the tree is rotated towards right at that node.
ight rotation. When a tree at a node has Balance Factor less –1 then the tree at that node is considered to be right heavy. To balance the right heavy tree the tree at that node rotated towards left. Similarly, if the tree is at a node is heaving Balance Factor more than 1 will be considered as left heavy. To balance the left heavy tree, the tree is rotated towards right at that node.
Application of Binary Tree:
1.Symbol Table Construction:
The notion of symbol table arises frequently in computer science while building compilers, loaders, linkers, assemblers etc. A symbol table is a set of name-value pairs. Associated with each name in the table is an attribute, a collection of attributes, or some directions about what further processing is needed. One of the criteria that a symbol table routine must meet is that the table searching must be performed efficiently. This requirement originates in the compilation phase while handling many lexemes and tokens of the program. The three required operation of the symbol table are:
a) Insertion of new entry
b) Deletion of existing entry
c) Looking up information of an existing entry.
Each of above operation requires searching.
Generally, a tree is used to construct a symbol table because
a) if the symbol table entries as encountered are uniformly distributed according to lexicographic order, then table searching becomes approximately equivalent to a binary search, as long as the tree is maintained in lexicographic order.
b) A binary tree is easily maintained in lexicographic order.
2)Manipulation of the Arithmetic Expressions:
We observed that the formulas in Reverse polish notation are very useful in the compilation process. There is a close relationship between binary trees and formulas in prefix or suffix notations. Let us write the infix formula as a binary tree where a node has an operator as a value and where the left and right sub-trees are the left and right operands of that operator. The leaves of the tree are the variables and constants of the expression. We represent the expression in binary tree due to similarities of infix to in order and postfixes to positor traversal of tree. The tree used for expression is called parse tree.
[Follow the conversion process taught in class room]
Graphs
A Graph is a nonlinear data structure, which is having point to point relationship among the nodes. Each node of the graph is called as a vertex and link or line drawn between them is called and edge.
Mathematically, A graph ‘G’ consists of two sets V and ‘E’ such that G={V,G}
Where V is finite nonempty set of vertices or nodes. V(G) represents set of vertices.
And E is a set of edges. E(G) represents set of Edges.
According to above example, V(G) = {1,2,3,4,5,6}
E(G)={(1,2),(2,1),(1,4),(4,1), ………}
Suppose edge e={u,v}, then the nodes u and v are called end points of the edge e. The node u is called source node and node v is called destination node, the nodes u and v are called adjacent nodes. The line drawn between to adjacent nodes is called an edge.
If an edge is having direction, then the source node is called adjacent to the destination and destination node is adjacent from source.
Path: A path is a sequence of consecutive edges between a source and a destination through different nodes. A path, said to be closed if source is equal to destination. The path is said to be simple if all nodes are distinct.
Cycle: A cycle is closed path with length 3 or more. A cycle of length k is called a k-cycle.
Loop : If an edge is having identical end points, then the edge is called a loop.
Degree/order: A degree of a node is the number of edges containing that node. The number edges pointing towards the node are called in-degree/in-order. The number edges pointing away from the node are called out-degree/out-order.
A graph in which the edges are having direction is called directed graph or digraph, otherwise the graph is called undirected graph.
Isolated node: If degree of a node is zero i.e. if the node is not having any edges, then the node is called isolated node.
Complete Graph : A graph is called complete if all the nodes of the graph are adjacent to each other. A complete graph with n nodes will have n*(n
-1)/2 edges.
-1)/2 edges.
Weighted Graph : A graph is said to be weighted if each edge in the graph is assigned a non-negative numerical value called the weight or cost of the edge. If an edge does not have any weight then the weight is considered as 1.
Multigraph : If a graph has two parallel path to an edge or multiple edges along with a loop is said to be multigraph.
Representation of Graph:
A graph may be represented in two ways. They are
Sequential Representation and Linked Representation.
Sequential Representation:
The graph is represented in sequential memory suing two matrices. They are
Adjacency Matrix and Path Matrix
Adjacency Matrix:
Suppose G is a graph with n nodes and the nodes of G are being ordered and are called v1,v2,v3,…..,vn then the adjacency matrix A=(aij) of the graph G is defined as
The adjacency matrix with 1’s and 0’s is also called bit matrix.
Path Matrix or Reach-ability Matrix :
Suppose G is a graph with n nodes and the nodes of G are being ordered and are called v1,v2,v3,…..,vn then the Path matrix P=(pij) of the graph G is defined as
Adjacency matrix A is a path of length 1. Similarly, A2, A3, A4, ….., An are the path matrix of length 2,3,4,…..,n respectively. Then before calculating path matrix the matrix Bn will be calculated to find P.
Where Bn = A2 + A3 + A4 + ….. + An
All non-zero elements of Bn are replaced with 1 to form path matrix P.
Linked Representation:
The Matrix representation of graph does not keeps track of the information related to the nodes. Hence a linked representation is used to represent a graph called adjacency structure. The adjacency structure of the graph maintains two lists called node list and edge list.
Node List: Each node in the node list will correspond to a node in the graph and will have three field. They are the information of the node called INFO, Pointer to the next node of the list called NEXT, a pointer to the edge list called ADJ.
Edge List: Each element of the edge list will correspond to an edge of the graph and will gave two fields. They are DEST contains the address of the destination node and LINK contains the address of the next node of the edge list.
[Follow the algorithm taught in class for node and edge insertion and deletion]
Graph Traversal:
Traversing a graph means visiting all the vertices in a graph exactly one. It is of two types:
Breadth First Traversal and Depth First Traversal.
Breadth First Traversal:
The traversal starts at a node v, after marking the node the traversal visits all incident edges to node v after marking the nodes and then moving to an adjacent node and repeating the process. The traversal continues until all unmarked nodes in the graph have been visited.
A queue is maintained in the technique to maintain the list of incident edges and marked nodes. It is more appropriate for a digraph.
Depth First Traversal:
A DEPTH FIRST SEARCH OF AN ARBITRARY GRAPH CAN BE USED TO PERFORM A TRAVERSAL OF A GENERAL GRAPH. THE TECHNIQUE PICKS UP A NODE AND MARKS IT. AN UNMARKED ADJACENT NODE TO PREVIOUS NODE IS THEN SELECTED AND MARKED, BECOMES THE NEW START NODE, POSSIBLY LEAVING THE PREVIOUS NODE WITH UNEXPLORED EDGES FOR THE PRESENT. THE TRAVERSAL CONTINUED RECURSIVELY, UNTIL ALL UNMARKED NODES OF THE CURRENT PATH ARE VISITED. THE PROCESS IS CONTINUED FOR ALL THE PATHS OF THE GRAPH.
HASHING
Hashing is a searching technique which is key to address transformation technique. The normal linear and binary search technique, searches for a key via sequence of comparisons. Hashing differs from this in that the address or location of an identifier X, is obtained by computing some arithmetic function, f of X, f(x) gives the address of X in the table. This address will be referred to as the hash or home address of X. Depending on the address yielded by the function the data are stored in sequential memory location, called hash table.
Hash Table:
The memory available to maintain the symbol table is assumed to be sequential. This memory is referred to as the hash table HT. The hash table is partitioned into b buckets, HT(0), HT(1), …,HT(b –1). Each bucket is divided into S slots and each slot is capable of holding a records. Thus, a bucket is said to consist of s slots, each slot being large enough to hold 1 record. Usually s =1 and each bucket can hold exactly 1 record. A hashing function, f(x), is used perform an identifier transformation on X. f(x) maps the set possible identifier on to the integers 0 through b –1.
The ratio n/T is the identifier density, while n /(s*b) is the loading density or loading factor.
Where n is the number of identifiers ,
b is number of buckets,
T is total number of possible identifiers
s is number of slots.
HASHING FUNCTION-
A hashing function, f ,transforms an identifier X into a bucket address in the hash table .As mentioned earlier the desired properties of such a function are that it be easily computable and that it minimize the number of collisions.
Since many programs use several identifiers with the same first letter, we would like the function to depend upon all the characters in the identifiers in addition, we would like the hash function to be such that it does not result in a biased use of the hash table for random inputs.
Several kinds of uniform hash functions are in use.
1 . Division 2. Mid-square 3 .Folding 4. Digit Analysis
Only division method is used frequently and is most preferred one.
Division Method:
This is the most common method used for hash function. The function is used to find a number may be prime or it is number of buckets. Then the number will be used to divide the key by it. The remainder is the hash address for that key. For example let us consider a hash table of 10 buckets and try to find the address of following values.
34, 56, 89, 432, 87, 651
the home address of 34 will be 34%10 = 4
The home address of 56 will be 56%10 = 6
And so on for others as mentioned in the table
Some times two different keys may yield same hash address. The there will be collision between the keys. There are few techniques for resolving the collision.
Collision Resolution Technique:
When there is a collision, then a random rehashing function is used to resolve the collision. The efficiency of collision resolution procedure is measured by the average number of probes(key comparisons) needed to find the location of the record with the
given key.
given key.
Normally the collision is resolved by dividing the each bucket into multiple slots. So, that the keys of same address can be kept in different slots of same bucket. There are two different ways to resolve the collision.
Open Addressing and Chaining.
The open addressing is uses a sequential representation for hash table like two dimensional or three dimensional array. The chaining concept uses a linked representation for each bucket and each bucket is linked with linked list maintaining the slots of that bucket.
Permutations
The permutation problem is as follows: Given a list of items, list all the possible orderings of those items.
We typically list permutations of letters. For example, here are all the permutations of CAT:
CAT
CTA
ACT
ATC
TAC
TCA
There are several different permutation algorithms, but since recursion an emphasis of the course, a recursive algorithm to solve this problem will be presented. (Feel free to come up with an iterative algorithm on your own.)
The idea is as follows:
In order to list all the permutations of CAT, we can split our work into three groups of permutations:
1) Permutations that start with C.
2) Permutations that start with A.
3) Permutations that start with T.
The other nice thing to note is that when we list all permutations that start with C, they are nothing put strings that are formed by attaching C to the front of ALL permutations of “AT”. This is nothing but another permutation problem!!!
Number of recursive calls
Often times, when recursion is taught, a rule of thumb given is, “recursive functions don’t have loops.” Unfortunately, this rule of thumb is exactly that; it’s not always true. An exception to it is the permutation algorithm.
The problem is that the number of recursive calls is variable. In the example on the previous page, 3 recursive calls were needed. But what if we were permuting the letters in the word, “COMPUTER”? Then 8 recursive calls (1 for each possible starting letter) would be needed.
In essence, we see the need for a loop in the algorithm:
for (each possible starting letter)
list all permutations that start with that letter
What is the terminating condition?
Permuting either 0 or 1 element. In the code that will be presented in this lecture, the terminating condition will be when 0 elements are being permuted. (This can be done in exactly one way.)
Use of an extra parameter
As we have seen, recursive functions often take in an extra parameter as compared to their iterative counterparts. For the permutation algorithm, this is also the case. In the recursive characterization of the problem, we have to specify one more piece of information in order for the chain of recursive calls to work. Here is what our function prototype, per-conditions and post-conditions will look like:
// Pre-condition: str is a valid C String, and k is non-negative
// and less than or equal to the length of str.
// Post-condition: All of the permutations of str with the first k
// characters fixed in their original positions
// are printed. Namely, if n is the length of str,
// then (n-k)! permutations are printed.
void Recursive Permute(char str[], int k);
Utilizing this characterization, the terminating condition is when k is equal to the length of the string str, since this means that all the letters in str are fixed. If this is the case, we just want to print out that one permutation.
Otherwise, we want a for loop that tries
each character in index k. It’ll look like this:
each character in index k. It’ll look like this:
for (j=k; j
Exchange Characters(str, k, j);
Recursive Permute(str, k+1);
Exchange Characters(str, j, k);
}
where Exchange Characters swaps the two characters in str with the given indexes passed in as the last two parameters. The whole function is included on the next page.
void Recursive Permute(char str[], int k) {
int j;
// Base-case: All fixed, so print str.
if (k == strlen(str))
printf(“%sn”, str);
else {
// Try each letter in spot j.
for (j=k; j
// Place next letter in spot k.
Exchange Characters(str, k, j);
// Print all with spot k fixed.
Recursive Permute(str, k+1);
// Put the old char back.
Exchange Characters(str, j, k);
}
}
}
Iterative Permutation Algorithm – B
ackground
ackground
Another algorithm that cycles through permutations goes through each of them in lexicographical ordering. Roughly speaking, lexicographical ordering is the same as alphabetical ordering. To determine which of two permutations should appear first in a lexicographical ordering, start comparing individual items from the left until you hit a difference. The permutation that should come first is the one with the item that comes earlier when comparing the two different items from the two different permutations.
For example, when comparing permutations of ACT, we find that CAT comes before CTA, because A comes before C. For a numerical example, the permutation 4,6,2,8,3,7,5,1 comes before 4,6,2,8,5,1,3,7, since 3 is smaller than 5 at the spot of the first discrepancy.
Given this definition for comparing two permutations of a set of items, a complete natural ordering is imposed on all the permutations on the list. For example, for the letters A, C, and T, the natural ordering of the permutations, using this definition is as follows:
ACT
ATC
CAT
CTA
TAC
TCA
Similarly, the ordering of the permutations of 1, 2, 3 and 4 are as follows:
1234 2134 3124 4123
1243 2143 3142 4132
1324 2314 3214 4213
1342 2341 3241 4231
1423 2413 3412 4312
1432 2431 3421 4321
In order to come up with an algorithm that iterates through all of the permutations of a set of items in this order, we need to have a successor function. Namely, we need a function that advances an array storing one permutation to the following permutation.
Once we write this successor function, we simply need to start with the first permutation (in this case, 1234 or ACT), and call the successor function the correct number of times. Since there are n! (read, “n factorial”) orderings
of n items, we must call the successor function n!-1 times.
of n items, we must call the successor function n!-1 times.
Note: We can derive the total number of permutations of n distinct objects as follows:
For the first object, we have n choices.
For the second object, we have n-1 choices (all but what we chose for the first object.)
For the third object, we have n-2 choices, etc.
Since each of these choices is independent of the rest, to calculate the number of different permutations, we simply need to multiply each of these numbers:
n x (n-1) x (n-2) x … x 1
This product is so common in mathematics, that it has a special name (factorial) and symbol (!). Symbolically, we have:
n x (n-1) x (n-2) x … x 1 = n!
Next Permutation Function
Let’s examine an example of finding the next permutation of
4,6,2,8,3,7,5,1
and utilize it to come up with a general algorithm.
We know that the fewer items we change on the right the better. The reason is that if we change the 4 to a 5, for example, then we are definitely missing other permutations that might start with 4 that come after the current one. In essence, our goal is to maximize the number of items, starting from the right, that stay fixed.
A real quick inspection will reveal that we can keep 4, 6, 2, and 8 fixed.
The reason is that 3, 7, 5, and 1 can be rearranged to form a “higher” permutation.
BUT, notice that 3 CAN NOT be fixed because it is IMPOSSIBLE to rearrange
7, 5, 1
to create a higher permutation. (This is the highest one since all the values are in descending order.)
Thus, the key to our successor algorithm is to determine the fir
st item, from the left, that has to be changed.
st item, from the left, that has to be changed.
Simply put, all of the items after this item have to be arranged in descending order.
So, here is step #1 of the algorithm:
Scan from the right side of the permutation, going backwards, continue scanning until you find the first pair of values in ascending order. The first value in this pair is the item that will be switched out.
Thus, if our input was 4,6,2,8,3,7,5,1,
We note that (5,1) is descending.
We note that (7,5) is descending.
But, we find that (3,7) is ascending.
Now that we’ve identified this value, our key is to determine WHICH value to switch into its place.
First, we know that all the values to its left will stay fixed, so we are NOT switching with any of these values. (In our example, that means we won’t switch 3 with 4, 6, 2 or 8.)
With this analysis, we have determined the following about the next permutation of 4,6,2,8,3,7,5,1:
1) The values, 4, 6, 2, and 8 will be fixed.
2) The value 3 must be changed.
3) It must be changed to 1, 5, or 7
Next, we know we must switch it with a higher value, otherwise our permutation won’t be a higher one. This reduces our list of possible values in our example to 7 and 5. (More generally, these are all the items that appear AFTER our designated item and are larger than it.)
Now, of the possibilities left, we MUST switch it with the lowest value left (5,7 in our example). The reason for this is that any permutation that starts with 5 precedes any permutation that starts with 7. In general, we want the lowest permutation possible of the ones left, and we can achieve this by minimizing our next choice.
Thus, we know that our permutation must start:
4, 6, 2, 8, 5
In doing so, we have exchanged the 3 for the 5, so our array currently looks like this:
4, 6, 2, 8, 5, 7, 3, 1
Now, we can state step #2 of the algorithm:
Determine the smallest value larger than the value to be exchanged in the permutation that comes AFTER the value to be exchanged, and swap these two values.
In our example, 3 was the value that needed to be exchanged and 5 was the smallest value listed after 3 that was also larger than 3.
Now, that we have made that change, we would like to “minimize” the rest of the permutation. For any permutation, we can minimize it by listing the items in ascending order. Currently, however, our items are listed in descending order:
4, 6, 2, 8, 5, 7, 3, 1
In a nutshell, we must simply take all the values that come after our original swapped location in the array, and reverse these values to obtain:
4, 6, 2, 8, 5, 1, 3, 7.
This is the next permutation.
Now, let’s look at the steps of the algorithm all together:
Iterative Permutation Algorithm
1. Scan from the right side of the permutation, going backwards, continue scanning until you find the first pair of values in ascending order. The first value in this pair is the item that will be switched out.
2. Scan to the right of the item identified in step 1, looking for the smallest item that is greater than the item identified in step 1. Swap these two items.
3. Reverse the part of the permutation that starts from the original location first identified in the array and ends at the end of the array.
A function that implements this algorithm is located on the next page.
void next Perm(int perm[], int length) {
// Find the spot that needs to change.
int i = length-1;
while (i>0 && perm[i] < perm[i-1]) i--;
i–; // Advance to swap location.
// So last perm doesn’t cause a problem.
if (i == -1) return;
// Find the spot with which to swap.
int j=length-1;
while (j>i && perm[j]
// Swap it.
int temp = perm[i];
perm[i] = perm[j];
perm[j] = temp;
// reverse from index i+1 to length-1.
int k,m;
for (k=i+1,m=length-1; kSORT ALGORITHMS
SELECTIO
');} temp = perm[k];
perm[k] = perm[m];
perm[m] = temp;
}
}
SORT ALGORITHMS
DEFINITION
INTERNAL VS EXTERNAL
SORT BEHAVIOR
SORT DATA STRUCTURES
STRAIGHT SORTS
EXOTIC SORTS
DEFINITION
The process of sorting, or creating a linear ordering of a list of objects, is one of the most fundamental of all operations.
∙ The objects to be sorted are assumed to be records, one field of which is the sort key.
∙ The sort problem is to arrange the objects so that the keys form a monotonic (non-decreasing or non-increasing) sequence.
∙ The objects to be sorted are assumed to be records, one field of which is the sort key.
∙ The sort problem is to arrange the objects so that the keys form a monotonic (non-decreasing or non-increasing) sequence.
INTERNAL SORTS
An internal sort is one in which the list to be sorted resides in the “internal” memory of the system. In an external sort the data resides on a peripheral device, such as a disk.
We will only deal with internal sorts.
SORT BEHAVIOR
€€€€ ∙ A sorting technique is said to have natural behavior if it executes faster when the list of objects is already partially or fully ordered.
∙ It is said to exhibit stable behavior if objects with equal keys are not swapped during the sorting process.
∙ It is said to exhibit stable behavior if objects with equal keys are not swapped during the sorting process.
Many sort algorithms exploit these behaviors in order to increase performance.
SORT DATA STRUCTURES
Our default data structure will be an array of integers. However, the only absolute requirement for the data structure is that it be capable of ordering.
Some of the more exotic sorts require an array but the basic sorts will all work with a linked list.
WHICH SORTS?
The sorts of primary interest are:
∙ Shell sort (257)
∙ Heap sort (260)
∙ Quick sort (269)
We will first review the “generic” versions of these sorts first.
∙ The insertion sort (254)
∙ The selection sort
∙ The exchange sort
STRAIGHT SORTS
∙ Straight-forward (or generic) implementations of the basic sort algorithms.
∙ They typically require a time which is on the order of O(n2).
∙ They are well-suited for demonstrating the algorithms.
∙ They require little code and generally are often faster for small values of n.
INSERTION SORT
The insertion sort works by starting at one end of the list “inserting” each element, p, in its proper place of the first p+1 elements.
INSERTION SORT ALGORITHM
for i := 2 to array_size do
begin
temp := a [i];
a [0] := temp
j := i – 1;
while temp < a [j] do
begin
a [j + 1] := a [j];
j := j – 1;
end
a [j + 1] := temp
end
INSERTION SORT BEHAVIOR
SELECTION SORT
In the selection sort we “select” the largest (or smallest) element of the unsorted data on each pass.
SELECTION SORT ALGORITHM
for i := 1 to array_size – 1 do
begin
temp := a [i];
k := i
for j := i + 1 to array_size do
if a [j] < temp then
begin
k := j
temp := a [j]
end
a [k] := a [i];
a [i] := temp
end
SELECTION SORT BEHAVIOR
EXCHANGE SORT
The exchange sort swaps overlapping pairs so that the largest (smallest) item is at the end of the list each pass.
EXCHANGE SORT ALGORITHM
for i := 2 to array_size do
begin
for j := array_size down to i do
if a [j – 1] > a [j] then
begin
temp := a [j – 1];
a [j] := temp
end
end
EXCHANGE SORT OPERATION
This sort is sometimes called the “bubble sort” because the largest (smallest) items seem to “bubble” up from the bottom as the sort proceeds.
EXCHANGE SORT BEHAVIOR
MODIFIED EXCHANGE SORT
The exchange sort seems to go blindly on, making comparisons even when the data is already ordered, suggesting the following modification:
i := 1;
while (i<= max_item_count) and (swap_flag) do
begin
swap_flag := False;
i := i + 1;
for j := max_item_count down to i do
if a [j-1 > a [j] then
begin
swap_flag := True;
temp := a [j-1];
a [j-1] := a [j];
a [j := temp
end
end
THE EXOTIC SORTS
The exotic sorts are refinements of the straight sorts. We shall discuss the following:
∙ insertion sort  shell sort
∙ selection sort  heap sort
∙ exchange sort  quick sort
These sorts all attempt to reduce either the number of comparisons or moves or both by making assumptions about the ordering of the data.
SHELL SORT
The shell sort (named after D. L. Shell) is a refinement of the insertion sort. It is also known as sorting by “diminishing increment”. The basis of the shell sort is that it is quicker to make several passes over the array, sorting a subset each time.
2I-SORT TECHNIQUE
€€€€ ∙ For the first pass all items which are n (n must be a power of 2) positions apart are grouped and sorted separately.
∙ For the next pass the items n/2 positions apart are sorted until the last pass sorts adjacent items.
∙ For the next pass the items n/2 positions apart are sorted until the last pass sorts adjacent items.
SELECTIO
N OF THE INCREMENTS
The Shell sort works for any selection of increments. What is not obvious is that it works better if the increments are not chosen as powers of 2. A number of studies have proposed schemes for choosing the increments. Those given in the following example are by Knuth.
The shell sort is not readily analyzed (many claim it isn’t that easy to understand either!) so we will have to depend upon measured performance.
SHELL SORT
h : array [Increment Range] of Integer;
begin
h[1] := 9; h[2] := 5; h[3] := 3; h[4] := 1;
for pass := 1 to Num Passes do
BEGIN
k := h[pass]; s := – k;
for i := k + 1 to Dictionary Size do
begin
temp := dictionary [i]; j := i – k;
if s = 0 then
s := – k;
s := s + 1;
dictionary [s] := temp;
while temp < dictionary [j] do
begin
dictionary [j+k] := dictionary [j]; j := j – k
end
dictionary [j+k] := temp;
end
END
HEAP SORT
∙ A refinement of the selection sort.
∙ Sorting by straight selection is based on the repeated selection of the least key among n items, then among the remaining n-1 items, etc.
∙ Finding the least key among n items requires n-1 comparisons,
∙ The selection sort can be improved by retaining from each scan more information than just the identification of the least item.
USE OF THE HEAP
The heap sort works by first arranging the data into a heap.
A heap is a tree such that the root is greater than or equal to the largest of its children.
Since the largest element is the root, it is removed and placed in the sorted list. Then, the remaining tree is readjusted to be a heap. This process continues until all items have been processed.
HEAP OPERATION
∙ Assuming the data stored in an array, the parent of node i is stored at i/2; the left child of node i is stored at 2i; and the right child is stored at index 2i + 1. The array is initially all heap area.
∙ After each pass, the heap area shrinks by one and the sorted area grows by one.
HEAP SORT PERFORMANCE
For large n, Heap sort is very efficient. The larger n becomes, the better Heapsort performs since it takes O(n logn) in both the worst and best case. Generally, Heapsort seems to “like” initial sequences in which the items are more less sorted in inverse order, and therefore it displays unnatural behavior.
QUICK SORT
∙ A refinement of the exchange sort.
∙ Based upon the fact that exchanges are best performed over large distances.
∙ Consider the case where the data is reverse ordered. In this case we can sort n items in n/2 exchanges by first exchanging the left and rightmost items and then working in from both sides. While this is only possible where the ordering of the data is known, it points out the possibilities.
PARTITIONING
∙ Pick an item at random (obviously using some scheme) and call it x.
∙ Scan the array from the left until an item ai > x is found then scan from the right until an item aj < x is found.
∙ Now exchange the two items and continue this process until the two scans meet somewhere in the middle of the array, resulting in an array which is partitioned into a left part with keys less than x and a right part with keys greater than x.
PARTITIONING
The partitioning process may be stated as follows:
BEGIN
i := 1; j := n;
< select an item x >
repeat
while a [i] < x do
i := i + 1;
while a [j] > x do
j := j – 1;
if i <= j then
begin
temp := a [i]; a [i] := a [j]; a [j] := temp;
i := i + 1; j := j – 1;
end
until i > j;
end
COMPLETION OF THE SORT
Now we complete the task of sorting the array by applying the same process to both partitions until every partition consists of only one item. This suggests the use of recursion although a stack can be used.
QUICK SORT ALGORITHM
begin
i := l; j := r; temp1 := a [(l+r) / 2];
repeat
while a [i] < temp1 do
i := i + 1;
while temp1 < a [j] do
j := j – 1;
if i <= j then
BEGIN
temp2 := a [i]; a [i] := a [j]; a [j] := temp2;
i := i + 1; j := j – 1
end
until i > j;
if l < j then
Quick Sort (l, j);
if i < r then
Quick Sort (i, r)
end
COLLECTING SORTS METRICS DATA
Since most of the sort metrics are dependent on the data being sorted, it is useful to be able to collect this data real-time. An example (a straight insertion) of a sort program with measurement probes inserted is shown below. Since the statements used to collect the data consume processing time, this version of the sort does not return an accurate value of CPU time.
DATA COLLECTION EXAMPLE
for i := 2 to array_size do
begin
temp := dictionary [i];
moves := moves + 1; dictionary [0] := temp;
moves := moves + 1; j := i – 1;
while temp < dictionary [j] do
begin
compares := compares + 1;
dictionary [j+1] := dictionary [j];
moves := moves + 1;
j := j – 1;
end
dictionary [j + 1] := temp;
moves := moves + 1;
end
PERFORMANCE – GENERIC SORTS
Size | Insertion | Selection | Exchange | Bubble |
5,000 | 60 | 170 | 410 | 410 |
5,000 | 160 | 200 | 360 | 381 |
5,000 | 0 | 191 | 190 | 0 |
10,000 | 370 | 791 | 1,750 | 1,780 |
10,000 | 0 | 801 | 781 | 0 |
10,000 | 871 | 891 | 1,520 | 1,640 |
20,000 | 1,750 | 3,260 | 7,040 | 6,990 |
20,000 | 0 | 3,270 | 3,150 | 0 |
20,000 | 4,030 | 3,730 | 6,340 | 68 |
40,000 | 7,550 | 13,400 | 28,810 | 28,150 |
40,000 | 0 | 1,402 | 12,930 | 0 |
40,000 | 16,620 | 15,020 | 25,300 | 26,600 |
100,000 | 47,280 | 181,790 | 175,630 | |
100,000 | 0 | 82,610 | 87,770 | 0 |
100,000 | 94,120 | 90,230 | 162,930 | 187,570 |
s ⇒ sorted data, r ⇒ reverse sorted data
PERFORMANCE – HEAP AND QUICK SORTS
ecadmin
subscriber
