A.1. Modify(A) J ß 5 For i=0 , i=A.length-1 , i++ IF A[i] = odd A[i] ß A[i]+A[i+
ID: 3874000 • Letter: A
Question
A.1.
Modify(A)
J ß5
For i=0 , i=A.length-1 , i++
IF A[i] = odd
A[i] ß A[i]+A[i+1]
A[i+1] ß A[i] – A[i+1]
A[i] ß A[i+1] – A[i]
Else
A[i] ß A[i]+J
J++
EndIF
EndFor
EndAlg
moodle.griffith..e a Given an Array BI] consisting of N elements, use pseudocode to describe how Bubble Sort would be performed. (8 marks) b) The table below displays an array of animal types being sorted. Column A = the starting Array, Column G shows the final, sorted, order. The columns in between show different sorting algorithms (listed below) at different stages of the sorting process. Identify which sorting algorithm produced which: A: Start B End vark le cat vark horse Cit at ark horse lephant horse le dvark cat ctopus Octopus le Squid le Octopus Squid TO Algorithm list: HeapSort(Max) BubbleSort, MergeSort, InsertionSort, SelectionSort, (10 marks) e) The Pseudocode in Appendix A.1 will fail if run as is. Correct edit) and apply the function to the the issue (requires following Array: 11 142721 22 196 Write out the final Array values when the algorithm has completed (7 marks) Total (25 marks)Explanation / Answer
Answer (a)
In bubble sort, neighbouring pairs of elements are compared, and if they are not in accordance with the sorting order, they are swapped. After the first pass, the largest element (in case of ascending order) bubbles to the end of the array. After the second pass, the second largest element bubbles to the second last position and so on. In the first iteration, (n-1) comparisons are made, in the second pass, (n-2) comparisons are made and so on. The pseudo code for bubble sort is as follows:
Bubble-Sort(A)
EndAlg
Answer (b):
In insertion sort, starting with an array of size 0 (trivially sorted), elements are inserted to keep the sort order intact. So at any time, the array is visualized as a beginning sorted sub-array, and a list of elements yet to be added.
Starting with dog, horse, cat, aardvark, zebra, octopus, squid, elephant, beetle, mouse,
Insertion sort gives the following array after each pass (| denotes the partition between the sorted array, and the elements yet to be inserted):
Pass 1: dog | horse, cat, aardvark, zebra, octopus, squid, elephant, beetle, mouse
Pass 2: dog, horse | cat, aardvark, zebra, octopus, squid, elephant, beetle, mouse
Pass 3: cat, dog, horse | aardvark, zebra, octopus, squid, elephant, beetle, mouse
Pass 4: aardvark, cat, dog, horse | zebra, octopus, squid, elephant, beetle, mouse
Pass 5: aardvark, cat, dog, horse, zebra | octopus, squid, elephant, beetle, mouse
Pass 6: aardvark, cat, dog, horse, octopus, zebra | squid, elephant, beetle, mouse
Pass 7: aardvark, cat, dog, horse, octopus, squid, zebra | elephant, beetle, mouse
Pass 8: aardvark, cat, dog, elephant, horse, octopus, squid, zebra | beetle, mouse
Pass 9: aardvark, beetle, cat, dog, elephant, horse, octopus, squid, zebra | mouse
Pass 10: aardvark, beetle, cat, dog, elephant, horse, mouse, octopus, squid, zebra |
So none of the stages in the list is reached by insertion sort.
For bubble sort, the following arrays are obtained after each pass:
Pass 1: dog, cat, aardvark, horse, octopus, squid, elephant, beetle, mouse, zebra
Pass 2: cat, aardvark, dog, horse, octopus, elephant, beetle, mouse, squid, zebra
So column B is a stage in bubble sort
In selection sort, the passes will be as follows:
Pass 1: aardvark, horse, cat, dog, zebra, octopus, squid, elephant, beetle, mouse
Pass 2: aardvark, beetle, cat, dog, zebra, octopus, squid, elephant, horse, mouse
Pass 3: aardvark, beetle, cat, dog, zebra, octopus, squid, elephant, horse, mouse
Pass 4: aardvark, beetle, cat, dog, zebra, octopus, squid, elephant, horse, mouse
Pass 5: aardvark, beetle, cat, dog, elephant, octopus, squid, zebra, horse, mouse
So column C is a step in selection sort
In merge sort, the array is split recursively, and then pairs of subarrays are merged to give the final sorted array. At each stage, the | shows the array boundaries. The number of |'s shows the recursion depth.
Stage 1: dog |||| horse ||| cat || aardvark ||| zebra | octopus |||| squid ||| elephant || beetle ||| mouse
Stage 2: dog , horse ||| cat || aardvark ||| zebra | octopus , squid ||| elephant || beetle ||| mouse
Stage 3: cat, dog , horse || aardvark, zebra | elephant, octopus , squid || beetle, mouse
Stage 4: aardvark, cat, dog , horse, zebra | beetle, elephant, mouse, octopus , squid
Stage 3: dog , horse | cat | aardvark, zebra | octopus , squid | elephant | beetle , mouse
So column E is a step in merge sort
In heap sort, at any stage after the formation of heap, there will be a sorted subarray at the end with a heap formed of the remaining elements. Column F can be represented in this manner. The heap is:
horse
|
elephant dog
| |
beetle aardvark cat
while the sorted part is: mouse, octopus, squid, zebra
So column F is a stage in heap sort
So the columns correspond to:
Answer (c):
In the loop, the test condition i=A.length-1 is wrong. This will result in the loop test condition being false in the first iteration itself. The test should instead be: i<A.length-1
So the correct pseudo code would be:
Modify(A)
EndAlg
The algorithms works as follows: If A[i] is odd, the values of A[i] and A[i+1] are swapped, with A[i+1] being negated as well. If A[i] is not odd, the value of J is added to it and J is incremented.
Running the algorithm on A= 11,14,2,7,21,22,19,6, gives the following values after each loop iteration:
Array A at end of iteration
So the final values in A are: 14,2,7,21,22,19,6,-11
Value of iArray A at end of iteration
J at end of iteration 0 14,-11,2,7,21,22,19,6 5 1 14,2,11,7,21,22,19,6 5 2 14,2,7,-11,21,22,19,6 5 3 14,2,7,21,11,22,19,6 5 4 14,2,7,21,22,-11,19,6 5 5 14,2,7,21,22,19,11,6 5 6 14,2,7,21,22,19,6,-11 5Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.