SURVEY OF PERFORMANCE OF DATA STRUCTURE

Amirah Fisal Alshammari, Reem Abdullah Almijmaj, Maram Saleh Alqueflie ,Yassmine Abdulaziz AlnasserAbstract – This paper aims to presents the different types of data structure and algorithms like arrays, lists, trees and also give their performance analysis in worst case. An analysis is being carried out on sorting algorithms and searching techniques on time complexity. There are many different types of algorithms and techniques for performing different tasks and as well as the same tasks, each one has its own advantages and disadvantages depending on the type of data structure. What the analysis shows that neither data structure totally dominates the other.

Index Terms—arrays, lists, trees, sorting, searching, time complexity, big o, stack, queue, data structure implementation, complexity measure.

INTRODUCTION

Data structure is a way of organizing data in a computer. Knowing and understanding how to structure data is very important. Therefore, algorithms can maintain, use, and retrieve through data quickly, because choosing the wrong data structure may end up in slow or unresponsive code. Therefore, we need to understand the nature of the problem in detail to choose the appropriate data structure for better performance. After reading this paper you will be able to use the right data structure depends on its time complexity.

previous work

An era of technical knowledge is being increasing rapidly for the analysis and comparative of different types algorithms used for searching any type of complex or large data’s given for the lists of items or data’s. Focuses on expansion of different searching techniques such as binary or linear searches related to analysis and comparisons that are made for the given lists of items or data’s so as to find out which searching technique is more efficient in resulting determination of time 1.

Searching refers to a process of inspecting whether the required item or data for the given lists is present or not which can be done using the key value. Some of the different types of techniques are sequential search, binary search, linear search, tree search and so on. Based upon these searching techniques, a single record one at a time can be fetched and also recovered from the storages that are available either internally or externally within a minor amount of time for the user.

The binary and linear searches are the two techniques considered in a given list of items or data’s for searching essentials 1. In case of binary search instead of checking each and every item one by one can be sorted in order and saves time. Whereas in case of linear search increases the time for searching a particular item or data.

Sorting algorithm assists in depth knowing about the definitions of each and every algorithm, work procedures, time and space complexities and so on. In general, is used to compare the difference between the swapping of records, requirement of memory space and estimation made between worst, average and best positions 2.

This specifies that different types of sorting algorithms enclose its own method for solving the worst, average and best positions based upon the inputs along with the space used and gives an idea that more than one algorithm can be used for solving numerous problems 4. Finally, concludes that when used the similar set of inputs which are been sorted for these algorithms, study shows that the gnome sort calculates the time very rapidly for the given set of inputs when compared along with selection and bubble sorts. Whenever for the given inputs in case if necessary the exchange of inputs can be done using bubble and gnome sorts.

Modern technology has evolved advanced facts for the expansion of required information relating to different types of techniques and algorithms. These techniques and algorithms when used and selected together without making a proper option leads to various problems while processing the data. Hence, in this survey endeavors 3 in opting for proper techniques and algorithms based upon their time and space complexity. By using different techniques such as bubble sort, selection sort and insertion sort the time and space complexity are carried out and analysis is performed to check for knowing which among these three techniques provides the majority efficiency used, while sorting the data for the given lists of elements.

The method for dealing with these quantities of items or data’s processes sorting of elements that are present in the lists then the searching mechanism takes place for execution of dates. Sorting here refers in filtering of elements for the given lists such as sorting of contact numbers given in telephone directory, sorting of aid har card numbers in the given data set and so on. For performing a lengthy sorting for the given sequence, a variety of functioning process are required and can come to know which is the suitable algorithm essential for calculating time and space firmness for the given bubble, insertion and selection sorts 3.

IMPLEMENTATION

We have searched about data structures algorithms and how each one can work. we chose two types from each data structure, and we applied the same input size and data to all data structure algorithms. We have written a program in C and C++ languages to measure their complexity. Then we added a counter to the program to count the number of comparisons, sifting swapping and insertion, then we ran the programs with different inputs with different inputs sizes as the following:

n=5{7,8,3,1,6), n=10 {7,8,3,1,6,9,10,15,13,16},

n=15{7,8,3,1,6,9,10,15,13,16,17,19,20,21,22},

n=20{7,8,3,1,6,9,10,13,15,16,17,19,20,21,22,29,28,25,33,30}.

After searching several times for different elements within different types of data structures. We realized that searching for the element that represent the worst case would give us the maximum number of comparisons, which explain the extent of the disparity between the algorithms. We considered the number of comparisons each time to measure the complexity, and make us able to decide any algorithm are more efficiently, based on its complexity. And get the result of this counter each time and save it in the table, then we draw the curve by using the Excel program.

The data structure which we have chosen:

Array

Sorting Algorithm

Insertion sort

Bubble sort

Searching

Linear search

Binary search

Lists

Stack

Queue

Tree

Binary search tree BST

AVL tree

PERFORMANCE RESULT AND DISCUSSION

Arrays

Sorting Algorithm

Insertion sort

Bubble sort

Table1: number of comparisons of insertion and bubble sort

Fig1: curve of insertion and bubble sort comparisons.

Fig2: curve of insertion and bubble sort swap.

We implement insertion and bubble sort algorithms in worst case, which the time complexity of the both is O(n2). Based on the table.1 and figures(Fig1,Fig2), insertion sort is its simplicity and it is also good performance for smallest array, but the disadvantage is that it is not useful for large elements array. As for the bubble sort is that it is easily implemented, the elements are swapped without additional temporary storage, so space requirement is minimum. All of insertion sort and bubble sort has a same number of swaps for the different input size.

Searching

Linear search

Binary search

Table2: number of comparisons of linear and binary search.

Fig3: curve of linear and binary search comparisons.

From the table.2 that showing how the maximum number of comparisons increases for binary search and linear search, we note that the worst case number of comparisons in binary search is just 4 for an array of 10 elements, versus 10 for linear search! furthermore, if the list were doubled in size to 20, the maximum number of comparisons for binary search would only increase by 1 to 5, whereas for linear search it would double from 10 to 20. Based on these results, we can assume that the time complexity of binary search is less than linear search, therefore if we have sorted array and we need better complexity then we should use binary search algorithm. The time complexity of the linear search is O(n), while the time complexity of the binary search is O(log2 n).

Lists

Stack and Queue

Stack is simpler and faster than queue, where queue is comparatively complex. We implement Stack and Queue algorithm witch based of LIFO for stack, and FIFO for queue. And then measure time complexity of the both.

Table3: time complexity of insertion and deletion in stack and queue.

Fig4: curve of the time complexity in stack and queue.

Time complexity of insertion and deletion operation in stack and queue algorithms is O(1). Constant time in essence, it means that it takes the same amount of time to look up a value in a collection wherever we have a small number of items in the collection or very many (within the constraints of hardware).

Tree

Binary search tree BST

AVL tree

Table4: number of comparisons in insert operation.

Fig5: curve of the number of insertion.

Table5: number of comparisons in search operation.

Fig6: curve of the number of comparisons.

Here in above figures(Fig5)(Fig6), we notice that the number of comparisons as well as the number of insertions increases for BST in the worst case, and in AVL decreases, that’s means the time complexity of binary search tree is greater than AVL tree. The time complexity of BST is O(n), while the time complexity of AVL is O(log(n)).

CONCLUSION

This paper covers the performance of many types of data structures and their performance analysis in worst case. It compared and explained these types by implementing algorithms and draw a curve for each one. After reading this the user can be able to find out the appropriate and effective data structure depends on the requirements.

REFERENCES

Ayush Pathak, “Analysis and Comparative Study of Searching Techniques”, International Journal of Engineering Sciences & Research Technology, March, 2015.

D.R. Aremu et.al, “A Comparative Study of Sorting Algorithms”, African Journal of Computing & ICT, Vol 6. No. 5, December 2013 .

Makinde O.E. et.al, “Performance Evaluation of Sorting Techniques” ,ARPN Journal of Systems and Software, VOL. 3, NO. 5, August 2013.

Jehad Hammad, “A Comparative Study between Various Sorting Algorithms”, International Journal of Computer Science and Network Security, VOL.15 No.3, March 2015.