Test: Sorting - 2 - CUET Humanities MCQ

In the first pass, key = 47. Here, 82 from 1^st subfile and 31 from 2^nd subfile are swapped. It ends at number 16 which is swapped with the key, i.e. 47. This makes the array sorted.

It works by repeatedly stepping through the list to be sorted, comparing each pair of adjacent items and swapping them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted.

It would be a good idea to use bubble sort as a place holder, until you implement something else.

Selection sort algorithm is used to sort the elements of an arrays by finding the maximum or minimum element of the array and then putting that element into its correct position to sort the array in ascending or descending order.
In the array given above, to sort it into an ascending array, the first step is to find the minimum element which is 11 and replace it with 64.
After the first step array becomes: 11 25 12 22 64
Hence, option 1 is correct.

If there are n elements in the list, then (n - 1) passes are required to compare the elements in the first pass.
Thus, total number of comparisons (A) in bubble sort for a list of N elements = n - 1 = 7 - 1 = 6
In selection sort, selecting the lowest element requires n - 1 + n - 2 + n - 3 + ... comparisons for n elements.

Hence, A < B.

Consider the array: [5, 4, 3, 2, 1]
The 1^st iteration will compare the 4 numbers (4, 3, 2, 1) with 5.
The 2^nd iteration will compare next 3 numbers (3, 2, 1) with 4.
The 3^rd iteration will compare next 2 numbers (2, 1) with 3.
The 4^th iteration i will compare last number i.e.1 with 2.
So, total number of comparisons = 4 + 3 + 2 + 1 = 10
It can be viewed as the sum of the sequence of the first (n - 1) numbers starting by 1.
S = (n × (n - 1))/2 (here, n = 5)
S = 10

Best Case Time Complexity is: O(N²).

Insertion sort, on average, takes O(n²) time.

For a sorted list with few random numbers:

• Bubble sort will take O(n²) time in best case.
• Selection sort will take O(n²) time in best case.
• Quick sort will take O(n²) time in this case because it is the worst case for quick sort.
• Insertion sort will take O(n)

Insertion sort take time only to sort unsorted elements. Here most of the elements are sorted hence insertion sort will be the perfect choice.
So, option (4) is correct.

Open addressing is a solution of collision.
The open addressing is another technique for collision resolution. Unlike chaining, it does not insert elements to some other data-structures. It inserts the data into the hash table itself.