Sorting and Searching

Sorting and Searching

Q-1 Define the following terms.

a)   Data: data means raw facts. It is a single value or group of values.

Examples of single value: employee-number

Example of group of value: Name which is divided into three sub data value first-name, middle-name, last-name.

b)  Information: Process on data gives some result that result is known as information.

c)   Data structure: A data structure is an arrangement of data, either in the computer’s memory or on the disk storage. Examples include arrays, linked list, queues, stacks, binary trees.

d)  Primitive data type: fundamental data types, which are available on most of  the computer as inbuilt data types. Example int, float, char

e)   Non-primitive data type: user define data types, where user can select the number of memory spaces needed to store particular data. Example array, stack, queue, tree, graph.

f)    Linear data structure: data are stored sequentially using memory location to remember data store sequentially not memory location. Example array, stack, queue and link list.

g)  Non-linear data structure: in non linear data structure data is not stored sequentially.

Example: tree, graph.

2) What are different types of problem that can solve with the knowledge of data structure?

Ø Data structure are widely applied in areas such as compiler design, operating system, statistical analysis package, DBMS, numerical analysis, simulation, artificial intelligence and graphics.

Ø The major data structures used in the network data model are graphs. In the same way hierarchical data model uses trees and RDBMS uses arrays.

 

3)  What is an array? How an array is represented in memory?

An Array is a fixed-size sequence collection of elements of the same data type. There are three types of arrays.

1)  one-dimensional array

2)  two-dimensional array

3)  multidimensional array

Example: int number[5];

Computer reserve five storage location as shown below.

Number[0]

Number[1]

Number[2]

Number[3]

Number[4]

Example: int number[2][2];

      Number[0][0]

      Number[0][1]

      Number[1][0]

      Number[1][1]

   

    4)  Explain row major and column major representation of two dimensional arrays?

Arrays may be represented in Row-major form or Column-major form.  In Row-major form, all the elements of the first row are printed, then the elements of the second row and so on upto the last row.  In Column-major form, all the elements of the first column are printed, then the elements of the second column and so on upto the last column.  The ‘C’ program to input an array of order m x n and print the array contents in row major and column major.

The difference between row-major and column-major order is simply that the order of the dimensions is reversed

 

Would be stored as follows in the two orders:

Column-major order e.g. Fortran Address Value 0 11 1 21 2 12 3 22 4 13 5 23

Row-major order e.g. C Address Value 0 11 1 12 2 13 3 21 4 22 5 23

 

    5)  Explain the different operations of an array.

There are a number of operations that can be performed on arrays. These operations include

1)  Traverse

2)  Insertion

3)  Deletion

4)  Searching

5)  Merging

6)  Sorting

1)  Traverse: traversing the array elements means accessing each and every element of the array for a specific purpose.

2)  Insertion: inserting an element in the array means adding a new data element in an already existing array. Here we can insert the elements by three different ways

a.   Insert at end

b.   Insert at first

c.   Insert in the middle

3)  Deletion: deleting an element from an array means removing a data element from an already exiting array. Here we can delete the elements by three different ways

a.   Delete at end

b.   Delete at first

c.   Delete in the middle

4)  Searching: searching means to find whether a particular value is present in the array or not. If the value is present in the array then searching process gives the location of the value in the array.

5)  Merging: merging two arrays in a third array means first copying the contents of the first arrays into the third array and then copying the contents of the second array into the third array.

6)  Sorting: sorting means arranging the elements of an array so that they are placed in some relevant order which may either be ascending or descending.

 

     6)  What is sparse matrix? Explain the precedence involved in representing sparse matrix.

Sparse matrix is a matrix that has many elements with a value zero. In order to efficiently utilize the memory, specialized algorithms and data structures that take advantage of the sparse structure should be used.

Basically there are two types of sparse matrix 1) Triangular matrix 2) Tri-diagonal matrix

There are two type of triangular matrix.

1)  Lower triangular matrix: all elements above the main diagonal have a value zero.

 

1     0     0    0   0  

5     3     0    0   0

2     7    -1    0   0

3     1     4    2   0

-9    2    -8   1    7

 

2)  Upper triangular matrix: all elements below the main diagonal have a value zero.

1    2    3    4    5

0    3    6    7    8

0    0   -1    9    1

0    0    0    9    3

0    0    0    0    7

 

Tri-diagonal matrix: Element with a non zero value can appear only on the diagonal or immediately above or below the diagonal. This type of matrix is also called a tri-diagonal matrix.  

 

4     1     0     0      0      0     

5     1     2     0      0      0     

0     9     3     1      0      0     

0     0     4     2      2      0    

0     0     0     5      1      9

0     0     0     0      8      7     

 

    7)  What are the advantages and disadvantages of an array?

Advantages:
1. It is used to represent multiple data items of same type by using only single name.
2. It can be used to implement other data structures like linked lists, stacks, queues, trees, graphs etc.
3. 2D arrays are used to represent matrices.

Disadvantages:
1. We must know in advance that how many elements are to be stored in array.
2. Array is static structure. It means that array is of fixed size. The memory which is allocated to array can not be increased or reduced.
3. Since array is of fixed size, if we allocate more memory than requirement then the memory space will be wasted. And if we allocate less memory than requirement, then it will create problem.
4. The elements of array are stored in consecutive memory locations. So insertions and deletions are very difficult and time consuming.

    8)  What is sorting and searching?  Mention different types of sorting and searching.

Sorting: Sorting means arranging the elements of an array so that they are placed in some relevant order which may either be ascending or descending.

Searching: Searching means to find whether a particular value is present in the array or not. If the value is present in the array then searching process gives the location of the value in the array.

 There are two types sorting a) internal sorting b) external sorting

a)   Internal sorting: This deals with sorting the data stored in the computer`s memory.

b) External sorting: This deals with sorting the data stored in files.

In internal sorting there are eight types of sorting.

a)   Bubble sort

b)  Insertion sort

c)   Selection sort

d)  Merge sort

e)   Quick sort

f)    Radix sort

g)  Heap sort

h)  Shell sort

There are two types of searching.

a)   Linear search or sequential search

b)  Binary search

    9)  Compare bubble and insertion sort for time complexity.

Ø The best case input is an array that is already sorted. In this case insertion sort has a linear running time (i.e., O(n)). Although bubble sort is one of the simplest sorting algorithms to understand and implement, its linear running time O(n²) .Means insertion sort are usually considerably more efficient.

Ø The simplest worst case input is an array sorted in reverse order. This gives insertion sort a quadratic running time (i.e., O(n²)).

Ø The average case is also quadratic, which makes insertion sort impractical for sorting large arrays. Where bubble sort efficiency decreases dramatically on lists of more than a small number of elements.

 

     10)                 Explain following terms a) best case b) worst case. C) average case

a)   Best case: The cases occur when sorting techniques have minimum number of comparison occurs.

b)  Worst case: The cases occur when sorting techniques have maximum number of comparison occurs.

c)   Worst case: The cases occur when sorting techniques have average number of comparison occurs.

 

    11)                 Among all the sorting technique which is the best technique discuss with example.

Quick sort is widely used sorting algorithm that makes o(n log n) comparison in the average case to sort an array of n elements. However in the worst case it has a quadratic running time given s o(n²). Basically the quick sot is faster than other algorithms, because its efficient implementation can minimize the probability of requiring quadratic time. It is also known as partition exchange sort. Quick sort can be used to sort arrays of small size, medium size or large size.

Example: as per the lect. Notes

   12)                 Which is better searching technique?

There are two popular methods for searching the array elements linear search and binary search. Now which algorithm should be used depends entirely on how the values are organized in the array. If the elements of the array are arranged in ascending order, then binary search should be used as it is more efficient for sorted list.

    13)                 Explain merge sort with example.

Ø Merge sort is a sorting algorithm that uses the divide, conquer, and combine algorithmic theory.

Ø Divide means partitioning the n-element array to be sorted into two sub-arrays of n/2 elements in each sub-array.

Ø Conquer means sorting the two sub-arrays recursively using merge sort.

Ø Combine means merging the two sorted sub-arrays of size n/2 each to produce the sorted array of n elements.

Ø Complexity of merge sort.

The running time of merge sort in the average case and the worst case can be given as      o(n logn). It needs an additional space of o(n) for the temporary array TEMP.

   14)                 What is prerequisite of binary search?

The prerequisite of binary search is data from which we want to search must be in sorted order.

   15)                 Define the terms linked list and node

Linked terms: A Linked list in simple terms is a linear collection of data elements.

Node: A Linked list in simple terms is a linear collection of data elements. These data elements called nodes.

    16)                 Why we need dynamic memory allocation?

Dynamic memory allocation means allocating memory space to a variable while running the program. If we want to allocating memory during run time this is possible by using standard library functions malloc() and calloc().

   17)                 Define malloc() and strrev().

Malloc(): malloc() is a function  used to allocate memory it returns address of the memory as successful otherwise returns NULL if memory allocation is unsuccessful.

Strrev(): strrev() is a library function that reverse all the characters in the string except the null character.

   18)        Name any four operations of doubly link list.

1)  Traversing

2)  Insertion

3)  Deletion

4)  Searching

5)  Sorting

6)  merging