Searching, Sorting and Complexity Analysis: Two Marks Important Questions and Answers

Data Structures using C ++

Chapter 9: Searching, Sorting and Complexity Analysis

Two Marks Questions with Answers

 

1. What is the time complexity of binary search and quick sort ?

Answer:

The time complexity of binary search is O(logn) and the best case and average case time complexity of quick sort is O(logn) the worst case time complexity is O(n²).

2. What do you mean by sorting? Mention its types.

Answer:

The sorting is a method of arranging the data in some systematic order. The data can be arranged in ascending order or descending order.

There are two types of sorting ‒

1. Internal sorting : The internal sorting is a method which is applied on the data stored on the main memory. Various techniques of internal sorting method are ‒

a) Bubble sort

b) Insertion sort

c) Shell sort

d) Heap sort

e) Merge sort

f) Quick sort

2. External sorting : In this sorting method the data resides on external or secondary storage devices such as hard disk, floppy disk etc.

3. What is external sorting?

Answer:

External sorting is a sorting method in which the data resides on external or secondary storage devices such as floppy disks, hard disks etc. The external sorting is a complex sorting method. The data stored on secondary memory is part by part loaded into the main memory and then the sorting is done on main memory itself. The sorted data can be stored in the intermediate files. Thus many files can be generated. And finally all the sorted intermediate files are merged in a single file. Thus a huge amount of data is sorted using this technique.

4. Sort the following using merge sort: 15,25,70,07,11,65,81,57.

Answer:

Consider, 15, 25, 70, 07, 11, 65, 81, 57. These elements are stored in an array.

We will go on dividing an array.

Now if we divide the above sublists we will get a single element in each sublist. Further division is not possible hence we will stop dividing and start merging. Now we will sort the elements in each sublist.

Now merge two sublists

is a sorted list.

5. State the algorithmic technique used in merge sort.

Answer:

Divide and conquer is an algorithmic strategy used to perform merge sort.

6. What is worst case complexity of quick sort?

Answer:

If the pivot element is chosen as the smallest or largest element from an array then it occupies either first or last position and then we have to sort the list with respect to pivot. Thus instead of logn in (n − 1) levels the complete list time complexity O(n²).

7. What is sorting? How is sorting essential for database applications ?

Answer:

Sorting is a systematic arrangement of data. In database applications, huge amount of data is stored. This data is nothing but collection of records. For example in employee database ‒ the information like employee name, ID, salary, Department, Date of joining is stored. Various operations that can be performed in the database are insertion of record, deletion of record, searching of particular record and modification of specific record.

If the records are sorted using some key (For instance Emp‒ID) then these operations can be performed very efficiently. Hence sorting is essential for database applications.

8. Which is the fastest sorting algorithm in practice? What is the average and worst running time of it?

Answer:

The fastest sorting algorithm in practice is quick sort. The average case time complexity is O(logn) and the worst running time of it is O(n²).

9. Differentiate between stable and unstable sort.

Answer:

In stable sorting if the same value elements are present in the list then the order of the elements remain the same even after the sorting. But in the unstable sorting the order of the similar value elements get changed.

10. What is the worst case and best case number of comparisons in linear search?

Answer:

In linear search if the entire list of elements need to be searched for locating the key element then the worst case number of comparisons are O(n) where n denotes the total number of elements in the list. During the best case the elements which is to be searched is present almost at the initial place. Hence very few comparisons are required in best case. The best case number of comparisons are O(1).

11. List the four types of sorting techniques

Answer:

The four types of sorting techniques are ‒

1. Bubble sort

2. Quick Sort

3. Insertion sort

4. Merge Sort

12. State why quick sort is more efficient than merge sort ?

Answer:

Merge sort requires auxiliary memory to perform sorting while the quick sort is a in‒place sorting method. The merge sort is more towards the processing of elements and quick sort is more towards storing of elements. These features make the quick sort more efficient than the merge sort.

13. How to perform union operation ?

Answer:

The union operation is a operation in which the elements from one set are combined with the elements of the another set. The repetition of element is avoided.

Following C++ implements this operation.

#define MAX 10

class UnionClass

{

private:

      int a[MAX],b[MAX];

      int i,term1,term2;

public:

void getData()

{

    cout<<"\n How many elements are there in First set?";

    cin>>term1;

    cout<<"\n Enter the elements in First set\n";

    for(i=0;i<term1;i++)

        cin>>a[i];

    cout<<"\n How many elements are there in Second set? ";

    cin>>term2;

    cout<<"\n Enter the elements in Second set\n";

    for(i=0;i<term2;i++)

        cin>>b[i];

}

void Union()

{

    int c[MAX];

    int i,j,k,n,flag;

    k=0;flag=0;

    for(i=0;i<term1;i++)

    {

        c[k++]=a[i];

    }

    for(j=0;j<term2;j++)

    {

        flag=0;

        for(i=0;i<term1;i++)

        {

        if(a[i]= =b[j])

        flag=1;

        }

        if(flag= =0)

            c[k++]=b[j];

    }

    n=k;

    cout<<"\n The A union B={";

    for(k=0;k<n;k++)

    cout<<" "<<c[k];

    cout<<"}";

}

};

void main()

{

    UnionClass obj;

    obj.getData();

    obj.Union();

}

Output

How many elements are there in First set? 3

Enter the elements in First set

1 2 3

How many elements are there in Second set? 5

Enter the elements in Second set

2 2 3 3 4

The A union B={ 1 2 3 4}

14. What is the time complexity of quick sort and binary search?

Answer:

The time complexity of quick sort and binary search is O(nlogn)

15. Why stability of sorting is important?

Answer:

Stability of sorting is important for following reasons ‒

1. It helps to sort the records properly when multiple keys for sorting are used.

2. It determines the worst case performance of the sorting algorithm.

16. When will the worst case occur in linear search ?

Answer:

When the item is at the last position in the array or if the desired element is not present in the array, it is a worst case.

17. For rearranging the library books in a shelf in proper order at the end of each day, which sorting technique will be the ideal choice?

Answer: Insertion sort.

18. way a card game player arranges his cards as he picks them one by one is an example of ‒

Answer: Insertion sort.

19. Name the sorting technique in which array to be sorted is partitioned again and again in such a way that all the elements that are less than partitioning element appear just before it and all the greater elements will appear after it.

Answer: Quick sort.

20. What is meant by sorting?

The sorting is a method of arranging the data in some systematic order. The data can be arranged in ascending order or descending order.

21. What is time complexity?

Answer:

Time complexity is amount of time required by an algorithm to execute. The time complexity is denoted using the asymptotic notations such as Big oh, Big omega and Big theta notation.

22. How an array elements are sorted using merge sort ?

Answer:

In merge sort, the array elements are repeatedly divided in groups and these groups are then merged together and finally two sub‒groups are merged together to form a single sorted list.

23. List of advantages of quick sort ?

Answer:

Advantages of quick sort are:

1. Quick sort is inplace sorting algorithm. Hence it needs no temporary memory.

2. It is faster than other sorting algorithms

3. It can be modified to parallel quick sort algorithm, due to use of divide and conquer approach.

4. It is well suited for modern computer architecture.

24. Which search is faster and why?

Answer:

• Binary search is faster than linear search algorithm. The time complexity of binary search is O(logn).

• It is faster because, the list is divided into two sublists by keeping on middle element. Each time the middle element of the compared with the key element. Due to this strategy, entire list need not have to be searched for searching the key element.

25. What is the time complexity of linear search?

Answer:

The time complexity of linear search is O(n)

26. Name the sorting technique which use the divide and conquer strategy?

Answer:

The sorting techniques that use divide and conquer strategy are:

1) Quick sort

2) Merge sort

27. What are the drawbacks of insertion sort ?

Answer:

1. It has a high time complexity of O(n²) in the worst and average cases, making it slow for large datasets.

2. It requires many comparisons and shifts, which reduces performance on big input sizes.

28. Give an algorithm to search an element in an array using linear search.

• Linear search does not expect specific ordering of the data. Infact the data is arranged in the list. At every iteration the record will be compared with the help of the key. In this case sometimes all the elements get compared with the key value. Although this is an simple searching technique some unnecessary comparisons has to be performed. This method does not give the satisfactory solution for the system for large number of elements.

• The time complexity of this algorithm is O(n). The time complexity will increase linearly with the value of n. For higher value of n the linear search is not the satisfactory solution.