-
Fig 15-1 Relationship GP Data Structures
-
TABLE 15. 1 General-Purpose Data Storage Structures
----------------------------------------------------------------
Data Structure Search Insertion Deletion Traversal
----------------------------------------------------------------
Array O(N) O(1) O(N) --
Ordered array O(logN) O(N) O(N) O(N)
Linked list O(N) O(1) O(N) --
Ordered linked list O(N) O(N) O(N) O(N)
Binary tree (average) O(logN) O(logN) O(logN) O(N)
Binary tree (worst case) O(N) O(N) O(N) O(N)
Balanced tree (average O(logN) O(logN) O(logN) O(N)
and worst case)
Hash table O(1) O(1) O(1) -
- Special Purpose Data Structure, that don't support searching or traversal
-
Table 15-2 Special-Purpose Data Storage Structures
----------------------------------------------------------
Data Structure Insertion Deletion Comment
----------------------------------------------------------
Stack (array or O(1) O(1) Deletes most recently
linked list) inserted item
Queue (array or O(1) O(1) Deletes least recently
linked list) inserted item
Priority queue O(N) O(1) Deletes highest-priority
(ordered array) item
Priority queue O(logN) O(logN) Deletes highest-priority
(heap) item
- Sorting Algorithms
-
Table 15.3 summarizes the running time for various sorting algorithms.
The column labeled Comparison attempts to estimate the minor speed
differences between algo rithms with the same average Big 0 times.
TABLE 15.3 Comparison of Sorting Algorithms
Sort Average Worst Comparison Extra Memory
Bubble O(N^2) O(N^2) Poor No
Selection O(N^2) O(N^2) Fair No
Insertion O(N^2) O(N^2) Good No
Shellsort O(N^3/2) O(N^3/2) -- No
Quicksort O(N*logN) O(N^2) Good No
Mergesort O(N*logN) O(N*logN) Fair Yes
Heapsort O(N*logN) O(N*logN) Fair No
(There's no entry for Shellsort because there are no other algorithms with the same Big 0 performance.)