Computer Science Test - 14

The correct answer is option 3.

Concept:

Insertion sort:

 Insertion sort is a basic sorting algorithm that operates in the same manner that you arrange cards in your hands. The array is divided into two halves, one sorted and one not. Values from the unsorted section are selected and placed in the sorted section at the appropriate location.

Explanation:

Consider the array is,

Input: 4 3 2 10 12 1 5 6

Output: 1 2 3 4 5 6 10 12

Explanation:

The implementation of insertion sort that there are again n−1 passes to sort n items. The iteration starts at position 1 and moves through position n−1, as these are the items that need to be inserted back into the sorted sublists.

Hence the total number of elements in an array is n=8.

Total pass will run insertion sort with 8 elements is = 7.

Hence the correct answer is 7.

The correct answer is option 1.

Concept:

Selection sort:

The selection sort algorithm sorts an array by continually picking the smallest member from the unsorted segment and placing it at the beginning (in ascending order). In a given array, the method keeps two subarrays.

• This is the subarray that has previously been sorted.
• The remaining unsorted subarray.

Best case:

No swaps are required as all elements are properly arranged. Selection sort is the algorithm that takes a minimum number of swaps, and in the best case, it takes ZERO (0) swaps when the input is in the sorted array-like

Example:

1,2,3,4.

Worst case:

The worst-case scenario for the number of swaps is n-1. However, it does not occur for merely the oppositely ordered input; rather, the oppositely ordered input like 6,5,3,2,1 takes n/2 swaps rather than the worst number of swaps.

So, what is the input for which the number of swaps is N-1?

A worst-case input is alternately increased and decreased, similar to the crest and trough.

Example:

Input: 7 6 8 5 9 4 10 3 Here 8 elements will require 7 swaps.

Output: 3 4 5 6 7 8 9 10 

Pass1:

3 6 8 5 9 4 10 7 (1 swap)

Pass 2:

3 4 8 5 9 6 10 7 (2 swap)

Pass 3:

3 4 5 8 9 6 10 7 (3 swap)

Pass 4:

 4 5 6 9 8 10 7 (4 swap)

Pass 5:

3 4 5 6 7 8 10 9 (5 swap)

Pass 6:

3 4 5 6 7 8 10 9 (6 swap)

Pass 7:

3 4 5 6 7 8 9 10 (7 swap)

Hence the correct answer is zero, n-1

The correct answer is option 1.

Concept:

Bubble Sort:

Bubble Sort is the most basic sorting algorithm, which operates by exchanging neighboring elements in the wrong order repeatedly. Bubble Sort is the most basic sorting algorithm, which operates by exchanging neighboring elements in the wrong order repeatedly.

Important Points

• In the first pass of the bubble sorts the highest element at the end. After each pass, the next highest element is stored.
• If there are no swaps in the list then the list is stored in order but the bubble sort runs n-1 passes.

Best Case:

Bubble sort best-case swaps are zero. The list would already be sorted. So no swaps are required.

Best case example:

Input: 1 2 3 4 5

Output: 1 2 3 4 5

Pass 1:

1 2 3 4 5 compare 1, 2 and no swap.

1 2 3 4 5 compare 2, 3 and no swap.

1 2 3 4 5 compare 3, 4 and no swap.

1 2 3 4 5  compare 4, 5 and no swap.

Pass 2:

1 2 3 4 5 compare 1, 2 and no swap.

1 2 3 4 5 compare 2, 3 and no swap.

1 2 3 4 5 compare 3, 4 and no swap.

Pass 3:

1 2 3 4 5 compare 1, 2 and no swap.

1 2 3 4 5 compare 2, 3 and no swap.

Pass 4:

1 2 3 4 5 compare 1, 2 and no swap.

Worst Case:

Bubble sort worst case swaps n(n-1)/2. The smallest element is at end of the list so it needs the n(n-1)/2 swaps are required.

Worst-case example:

Input: 5 4 3 2 1

Output: 1 2 3 4 5

Pass 1: 

4 5 3 2 1  compare 4, 5 and swap

4 3 5 2 1  compare 3, 5 and swap

 4 3 2 5 1 compare 2, 5 and swap

4 3 2 1 5 compare 1, 5 and swap

Pass 2:

3 4 2 1 5 compare 3, 4, and swap

3 2 4 1 5 compare 2, 4 and swap

3 2 1 4 5 compare 1, 4 and swap

Pass 3:

2 3  1 4 5 compare 2, 3, and swap

2 1 3 4 5 compare 1, 3, and swap

Pass 4:

1 2 3 4 5 compare 1, 2 and swap

Total swaps are  1+2+3+4 =10 =5(5-1)/2

Hence the correct answer is n2 and zero.

The correct answer is option 3.

Concept:

The given statement follows the bubble sort.

Bubble Sort:

Bubble Sort is the most basic sorting algorithm, which operates by exchanging neighboring elements in the wrong order repeatedly. Bubble Sort is the most basic sorting algorithm, which operates by exchanging neighboring elements in the wrong order repeatedly.

Best Case:

Bubble sort best-case swaps are zero. The list would already be sorted. So no swaps are required.

Best case example:

Input: 1 2 3 4 5

Output: 1 2 3 4 5

Pass 1:

1 2 3 4 5 compare 1, 2 and no swap.

1 2 3 4 5 compare 2, 3 and no swap.

1 2 3 4 5 compare 3, 4 and no swap.

1 2 3 4 5  compare 4, 5 and no swap.

Pass 2:

1 2 3 4 5 compare 1, 2 and no swap.

1 2 3 4 5 compare 2, 3 and no swap.

1 2 3 4 5 compare 3, 4 and no swap.

Pass 3:

1 2 3 4 5 compare 1, 2 and no swap.

1 2 3 4 5 compare 2, 3 and no swap.

Pass 4:

1 2 3 4 5 compare 1, 2 and no swap.

Here statement 1 is true, Best case= zero swaps and n(n-1)/2 ​ comparisons.

Worst Case:

Bubble sort worst case swaps n(n-1)/2. The smallest element is at end of the list so it needs the n(n-1)/2 swaps are required.

Worst-case example:

Input: 5 4 3 2 1

Output: 1 2 3 4 5

Pass 1: 

4 5 3 2 1  compare 4, 5 and swap

4 3 5 2 1  compare 3, 5 and swap

 4 3 2 5 1 compare 2, 5 and swap

4 3 2 1 5 compare 1, 5 and swap

Pass 2:

3 4 2 1 5 compare 3, 4, and swap

3 2 4 1 5 compare 2, 4 and swap

3 2 1 4 5 compare 1, 4 and swap

Pass 3:

2 3  1 4 5 compare 2, 3, and swap

2 1 3 4 5 compare 1, 3, and swap

Pass 4:

1 2 3 4 5 compare 1, 2 and swap

Total swaps are  1+2+3+4 =10 =5(5-1)/2

Here statement 2 is true, Worst case = n(n-1)/2 swaps and  n(n-1)/2 comparsions.

Important Points

Statement 3 and statement 4 is true.

• In the first pass of the bubble sorts the highest element at the end. After each pass, the next highest element is stored.
• If there are no swaps in the list then the list is stored in order but the bubble sort runs n-1 passes.

Hence the correct answer is Bubble sort.

The correct answer is option 3.

Concept:

The given example is a player playing a card game and sorting the cards. The Player first picks one card then picks the next card and put it after the first card if it is bigger or before the first card if it is smaller; then he picks another card and inserts it into its proper position.

A player follows the Insertion sort, It is a straightforward sorting algorithm that works similarly to how you arrange cards in your hands. The cards are divided into two parts: sorted and unsorted. The values of cards from the unsorted component are selected and placed in the sorted part in the proper order.

Example:

Consider the cards already sorted with 2, 4, 5, and 10. An unsorted card is 7 and is placed in the right position of a set of cards. Here card 7 is compared with 2, 4, 5, and 10 placed card 7 before 10. 

Hence the correct answer is Insertion Sort.

Additional Information

•  The selection sort algorithm sorts an array by continually picking the smallest member from the unsorted segment and placing it at the beginning (in ascending order). In a given array, the method keeps two subarrays. This is the subarray that has previously been sorted. The remaining unsorted subarray.
• Bubble Sort is the most basic sorting algorithm, which operates by exchanging neighbouring components in the wrong order repeatedly.

The correct answer is option 2.

Concept:

Selection sort:

The selection sort algorithm sorts an array by continually picking the smallest member from the unsorted segment and placing it at the beginning (in ascending order). In a given array, the method keeps two subarrays.

• This is the subarray that has previously been sorted.
• The remaining unsorted subarray.

The given array is,

Input: 64 25 12 22 11

Output: 11 12 22 25 64

Consider that min=64 is the minimum value.

Pass 1:

Now 64 compares every element and updates the min value. At last, we found the min=11 now swap 11 with 64.

11 25 12 22 64

Pass 2:

Now, 25 compares every element and updates the min value. At last, we found the min=12 and now swap 12 with 25.

11 12 25 22 64

Pass 3:

Now, 25 compares every element and updates the min value. At last, we found the min=22 and now swap 22 with 25.

11 12 22 25 64

Pass 4:

Now, 25 compares every element and updates the min value. At last, we found the min=25, and no swap is required.

11 12 22 25 64

Hence the correct answer is 11 12 25 22 64.

The correct answer is option 1.

Concept:

Insertion sort:

 Insertion sort is a basic sorting algorithm that operates in the same manner that you arrange cards in your hands. The array is divided into two halves, one sorted and one not. Values from the unsorted section are selected and placed in the sorted section at the appropriate location.

Explanation:

The given array is,

Input: 4 3 2 10 12 1 5 6

Output: 1 2 3 4 5 6 10 12

Hence the correct answer is 1 2 3 4 10 12 5 6.

The correct answer is option 3.

Concept:

Selection sort:

The selection sort algorithm sorts an array by continually picking the smallest member from the unsorted segment and placing it at the beginning (in ascending order). In a given array, the method keeps two subarrays.

• This is the subarray that has previously been sorted.
• The remaining unsorted subarray.

ii) Selection sort = a)

Bubble Sort:

Bubble Sort is the most basic sorting algorithm, which operates by exchanging neighboring components in the wrong order repeatedly.

i) Bubble sort = c)

Insertion sort:

Insertion sort is a straightforward sorting algorithm that works similarly to how you arrange cards in your hands. The array is divided into two parts: sorted and unsorted. The values from the unsorted component are selected and placed in the sorted part in the proper order.

iii) Insertion sort= b)

Hence the correct answer is i- c, ii- a, iii- b.

The correct answer is option 4.

Concept:

Selection sort:

The selection sort algorithm sorts an array by continually picking the smallest member from the unsorted segment and placing it at the beginning (in ascending order). In a given array, the method keeps two subarrays.

• This is the subarray that has previously been sorted.
• The remaining unsorted subarray.

The given array is,

Input: 30, 28, 12 , 24, 8

Output: 8, 12, 24, 28, 30

Consider that min=30 is the minimum value.

Pass 1:

Now, 30 compares every element and updates the min value. At last, we found the min=8 now swap 8 with 30.

8, 28, 12 , 24, 30

Pass 2:

Now, 28 compares every element and updates the min value. At last, we found the min=12 and now swap 12 with 28.

8, 12, 28 , 24, 30

The given hint is,

Inversion:

Let array A[1...n] be an array of elements, If the two indexes I, j od the array. If iA[j] then the pair i,j is known as inversion of the array. 

Inversion is,

Hence the correct answer is 1.

The correct answer is option 1.

Concept:

Selection sort:

The selection sort algorithm sorts an array by continually picking the smallest member from the unsorted segment and placing it at the beginning (in ascending order). In a given array, the method keeps two subarrays.

• This is the subarray that has previously been sorted.
• The remaining unsorted subarray.

Best case:

No swaps are required as all elements are properly arranged. Selection sort is the algorithm that takes a minimum number of swaps, and in the best case, it takes ZERO (0) swaps when the input is in the sorted array-like

Example:

3 4 5 6 7 8 9 10 

Worst case:

Case 1:

The worst-case scenario for the number of swaps is n-1. However, it does not occur for merely the oppositely ordered input; rather, the oppositely ordered input like 10 9 8 7 6 5 4 3 takes n/2 swaps rather than the worst number of swaps.

Example: 

Input: 10 9 8 7 6 5 4 3

Output: 3 4 5 6 7 8 9 10 

Pass1:

3 9 8 7 6 5 4 10 (1 swap)

Pass 2:

3 4 8 7 6 5 9 10 (2 swap)

Pass 3:

3 4 5 7 6 8 9 10 (3 swap)

Pass 4:

3 4 5 6 7 8 9 10 (4 swaps)

Total number of swaps are= 4

Case 2:

If we dig a little more, we will discover that the worst case is "SINE WAVE KIND OF AN INPUT." That is, input is alternately increased and decreased, similar to the crest and trough.

Example:

Input: 7 6 8 5 9 4 10 3 Here 8 elements will require 7 swaps.

Output: 3 4 5 6 7 8 9 10 

Pass1:

3 6 8 5 9 4 10 7 (1 swap)

Pass 2:

3 4 8 5 9 6 10 7 (2 swap)

Pass 3:

3 4 5 8 9 6 10 7 (3 swap)

Pass 4:

 4 5 6 9 8 10 7 (4 swap)

Pass 5:

3 4 5 6 7 8 10 9 (5 swap)

Pass 6:

3 4 5 6 7 8 10 9 (6 swap)

Pass 7:

3 4 5 6 7 8 9 10 (7 swap)

The total number of swaps are= 7.

Hence the correct answer is 7, 4