Data Structures

List out the areas in which data structures are applied extensively?

1. Compiler Design,
2. Operating System,
3. Database Management System,
4. Statistical analysis package,
5. Numerical Analysis,
6. Graphics,
7. Artificial Intelligence,
8. Simulation

What are the major data structures used in the following areas : RDBMS, Network data model and Hierarchical data model.

1. RDBMS = Array (i.e. Array of structures)
2. Network data model = Graph
3. Hierarchical data model = Trees

4.   What is the difference between Linked List and Linear Array?

S. No. Array Linked List 1. Insertions and deletions are difficult. Insertions and deletions can be done easily. 2. It needs movements of elements for insertion and deletion. It does not need movement of nodes for insertion and deletion. 3. In it space is wasted. In it space is not wasted. 4. It is more expensive. It is less expensive. 5. It requires less space as only information is stored. It requires more space as pointers are also stored along with information. 6. Its size is fixed. Its size is not fixed. 7. It can not be extended or reduced according to requirements. It can be extended or reduced according to requirements. 8. Same amount of time is required to access each element. Different amount of time is required to access each element. 9. Elements are stored in consecutive memory locations. Elements may or may not be stored in consecutive memory locations. 10. If have to go to a particular element then we can reach there directly. If we have to go to a particular node then we have to go through all those nodes that come before that node.

Static Data Structures
As same as the word static suggests, static data structures are designed to store static “set of data”. However, static “set of data”, doesn’t mean that we can not change the assigned values of elements. It is the memory size allocated to “data”, which is static. So that, it is possible to change content of a static structure but without increasing the memory space allocated to it.
Dynamic Data Structures
Dynamic data structures are designed to facilitate change of data structures in the runtime. It is possible to change the assigned values of elements, as it was with static structures. Also, in dynamic structures the initially allocated memory size is not a problem. It is possible to add new elements, remove existing elements or do any kind of operation on data set without considering about the memory space allocated initially.
Static Data Structures vs. Dynamic Data Structures
Static data structure is given a fixed area of memory which it can operate within. It is not possible to expand this fixed size in the run time. So that, locations of each element is fixed and known by the program. Dynamic data structure also has an area where it can operate. However, this size of the area is flexible, not fixed as it was with static data structures. It is possible to expand or contract the area as required, by adding or removing elements from data structure.
From here onwards an example of a static array and a dynamic linked list, will be considered to discuss differences.

Some of the sorting algorithm names are as follows:

1:Buble sort.

2:Selection sort.

3:Insertion sort.

4:Merge sort.

5:Heap sort.

6:Bucket sort.

Bubble Sort:

The algorithm works by comparing each item in the list with the item next to it, and swapping them if required. In other words, the largest element has bubbled to the top of the array. The algorithm repeats this process until it makes a pass all the way through the list without swapping any items.

voidbubbleSort(intar[])

{

for (int i = (ar.length - 1); i >= 0; i--)

   {

for (int j = 1; j ≤ i; j++)

      {

if (ar[j-1] >ar[j])

         {

int temp = ar[j-1];

ar[j-1] = ar[j];

ar[j] = temp;

   } } } }

Example. Here is one step of the algorithm. The largest element - 7 - is bubbled to the top:

7, 5, 2, 4, 3, 9
5, 7, 2, 4, 3, 9
5, 2, 7, 4, 3, 9
5, 2, 4, 7, 3, 9
5, 2, 4, 3, 7, 9
5, 2, 4, 3, 7, 9

Selection Sort:

1. We have two group of items:

n  sorted group, and

n  unsorted group

2. Initially, all items are in the unsorted group. The sorted group is empty.

n  We assume that items in the unsorted group unsorted.

n  We have to keep items in the sorted group sorted.

3. Select the “best” (eg. smallest) item from the unsorted group, then put the “best” item at the end of the sorted group.

4.      Repeat the process until the unsorted group becomes empty.

voidselectionSort(int[] ar){

for (int i = 0; i ‹ ar.length-1; i++)

   {

int min = i;

for (int j = i+1; j ‹ ar.length; j++)

if (ar[j] ‹ ar[min]) min = j;

int temp = ar[i];

ar[i] = ar[min];

ar[min] = temp;

} }

Example.

29, 64, 73, 34, 20,
20, 64, 73, 34, 29,
20, 29, 73, 34, 64
20, 29, 34, 73, 64
20, 29, 34, 64, 73

Insertion Sort :

1. We have two group of items:

n  sorted group, and

n  unsorted group

2. Initially, all items in the unsorted group and the sorted group is empty.

n  We assume that items in the unsorted group unsorted.

n  We have to keep items in the sorted group sorted.

3. Pick any item from, then insert the item at the right position in the sorted group to maintain sorted property.
4. Repeat the process until the unsorted group becomes empty.

voidinsertionSort(int[] ar)

{

for (int i=1; i ‹ ar.length; i++)

   {

int index = ar[i]; int j = i;

while (j > 0 &&ar[j-1] > index)

      {

ar[j] = ar[j-1];

j--;

      }

ar[j] = index;

} }

Example

29, 20, 73, 34, 64
29, 20, 73, 34, 64
20, 29, 73, 34, 64
20, 29, 73, 34, 64
20, 29, 34, 73, 64
20, 29, 34, 64, 73

Merge Sort:

o  Mergesort  (divide-and-conquer)

n  Divide array into two halves.

n  Recursively sort each half.

Merge two halves to make sorted whole.

n  Keep track of smallest element in each sorted half.

n  Insert smallest of two elements into auxiliary array.

n  Repeat until done.

Heap Sort:

n  In a heap sort, we create a heap data structure. A heap is a data structure that stores data in a tree such that the smallest (or largest) element is always the root node. (Heaps, also known as priority queues, were discussed in more detail in Data Structures.) To perform a heap sort, all data from a list is inserted into a heap, and then the root element is repeatedly removed and stored back into the list. Since the root element is always the smallest element, the result is a sorted list

Heap h = new Heap();

for (int i = 0; i <data.Length; i++)

h.Add(data[i]);

int[] result = new int[data.Length];

for (int i = 0; i <data.Length; i++)

data[i] = h.RemoveLowest();

n  The runtime of a heap sort has an upper bound of O(n * log n). Additionally, its requirement for storage space is only that of storing the heap; this size is linear in proportion to the size of the list. Heap sort has the disadvantage of not being stable, and is somewhat more complicated to understand beyond just the basic implementation.

n  Bucket Sort

Suppose we need to sort an array of positive integers {3,11,2,9,1,5}. A bucket sort works as follows: create an array of size 11. Then, go through the input array and place integer 3 into a second array at index 3, integer 11 at index 11 and so on. We will end up with a sorted list in the second array.

Suppose we are sorting a large number of local phone numbers, for example, all residential phone numbers in the 412 area code region (about 1 million) We sort the numbers without use of comparisons in the following way. Create an a bit array of size 10⁷. It takes about 1Mb. Set all bits to 0. For each phone number turn-on the bit indexed by that phone number. Finally, walk through the array and for each bit 1 record its index, which is a phone number.

10:49