Chapter – 10: UNDERSTANDING SORTING
Short Answer Type
Questions Q.1 What is sorting? Name some sorting Techniques.
Ans: In computer terms sorting refers to arranging elements in a
specific order – ascending or descending. Some sorting techniques are –
(i)
Selection Sort
(ii)
Bubble Sort
(iii)
Insertion Sort
(iv)
Heap Sort
(v)
Quick Sort
Q.2
What is the
basic principal of sorting in bubble sort?
Ans: The basic principal of bubble sort is to compare two adjoining
values and exchange them if they
are not in proper order.
Q.3
Why do
number-of-comparisons reduce in every successive iteration in bubble sort?
Ans: For the first iteration of the outer loop, when we are trying
to place the largest element in its correct position, N-1 comparisons takes
place. For the second iteration of the outer loop, there is no need to compare
against the last element of the list, because it was put at its correct position
on the previous pass. Therefore, the second iteration requires only N-2
comparisons.
And so on.
Q.4
On which
basis can you determine if an algorithm is efficient or not?
Ans: Efficiency of the algorithm is determined by its number of
operations. More number of operations means more CPU time. So the algorithm
with less number of operations will be more efficient.
Q.5
What is the
basic principal of sorting in Insertion sort?
Ans: Insertion sort is a sorting algorithm that builds a sorted
list by taking one element at a time
from the unsorted list and by
inserting the element at its correct position in sorted list.
Q.6
Number of
operations wise, compare bubble sort and insertion sort techniques.
Ans: In bubble sort in ith iteration you have n-i-1 inner
iterations (n^2)/2 total, but in insertion sort you have maximum i iterations
on i'th step, but i/2 on average, as you can stop inner loop earlier, after you
found correct position for the current element. So you have (sum from 0 to n) /
2 which is (n^2) / 4 total.
That's why insertion sort is
faster than bubble sort.
Q.7
Why
insertion sort is considered a better algorithm than bubble sort?
Ans: Insertion sort is slightly better than bubble sorting
algorithm. Though the worst case time complexity are same for both algorithms,
time complexity of insertion sort will depend on the data given. For a array
which is already sorted, insertion sort takes linear time, but for the bubble
sort algorithms it will take quadratic time complexity irrespective of
arrangement of data.
Q.8
In which
situations, insertion sort also becomes inefficient?
Ans: For large datasets, insertion sort becomes inefficient.
Q.9
What is the
main difference between insertion sort and bubble sort techniques?
Ans: Bubble Sort -
It is a sorting algorithm in which two adjacent elements of an array are
checked and swapped if they are in wrong order and this process is repeated
until we get a sorted array.
In this first two elements of the array
are checked and swapped if they are in wrong order. Then first and third
elements are checked and swapped if they are in wrong order. This continues
till the lat element is checked and swapped if necessary.
Insertion Sort -
In this, the second element is compared with the first element and is swapped
if it is not in order. Similarly, we take the third element in the next
iteration and place it at the right place in the sub-array of the first and
second elements (as the subarray containing the first and second elements is
already sorted). We repeat this step with the fourth element of the array in
the next iteration and place it at the right position in the subarray
containing the first, second and the third elements. We repeat this process
until our array gets sorted. Q.10 When
and why would you choose insertion sort over bubble sort?
Ans: When databases are smaller, insertion sort will be beneficial.
And where there are large databases than bubble sort will perform better.
Q.1
Ans:
Q.2
Ans:
0 comments:
Post a Comment
Thanks for leaving a comment. As soon as it's approved, it will appear.