Consider the following sorting algorithm for an Array A[1..n]: Algorithm 2: BubbleSort(A) 1 for i:=1 ......

Transcribed Image Text:

Consider the following sorting algorithm for an Array A[1..n]: Algorithm 2: BubbleSort(A) 1 for i:=1 ... n do 2 3 4 for j = 1... n-i do if A[i] > A[j] swap(A[i],A[i+1]) 1. Give an example execution of the algorithm. Use it to visualise yourself how the algo- rithm works. 2. Now show that the algorithm indeed sorts the array. 3. Analyse the algorithm's worst case running time. 4. What is the best-case running time of the algorithm? 5. Does the algorithm follow one of your already known design conepts? If yes, which one? 6. Find a simple way to improve/optimise the running time. Consider the following sorting algorithm for an Array A[1..n]: Algorithm 2: BubbleSort(A) 1 for i:=1 ... n do 2 3 4 for j = 1... n-i do if A[i] > A[j] swap(A[i],A[i+1]) 1. Give an example execution of the algorithm. Use it to visualise yourself how the algo- rithm works. 2. Now show that the algorithm indeed sorts the array. 3. Analyse the algorithm's worst case running time. 4. What is the best-case running time of the algorithm? 5. Does the algorithm follow one of your already known design conepts? If yes, which one? 6. Find a simple way to improve/optimise the running time.

Answer rating: 100% (QA)

1 Example Execution Lets consider an array A 42719 Pass 1 2 4 1 7 9 Comparison 4 2 swap 2 1 4 7 9 Co... View the full answer