Created
September 3, 2022 10:33
-
-
Save shiva-karthick/b0e9b0bb9bb7b72e4bec09965ccdb734 to your computer and use it in GitHub Desktop.
EE2028 Assignment 1
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* | |
* bubble_sort.s | |
* | |
* Created on: 4/8/2022 | |
* Author: Shankar | |
*/ | |
.syntax unified | |
.cpu cortex-m4 | |
.fpu softvfp | |
.thumb | |
.global bubble_sort | |
@ Start of executable code | |
.section .text | |
@ EE2028 Assignment 1, Sem 1, AY 2022/23 | |
@ (c) ECE NUS, 2022 | |
@ Bubble sort arr in decending order | |
@ Write Student 1’s Name here: Shankar | |
@ Write Student 2’s Name here: Wei Heng | |
@ You could create a look-up table of registers here: | |
@ R0 contains the address of the first element in the array | |
@ R1 contains the literal value 6 | |
@ R2 i; outer loop counter | |
@ R3 j; inner loop counter | |
@ R4 len(array) - 1 | |
@ R5 temporary register | |
@ R6 temporary register | |
@ R7 temporary register | |
@ R8 Global Swap Counter | |
@ write your program from here: | |
bubble_sort: | |
PUSH {R2-R8} | |
@Initialise the registers here | |
LDR R2, =#0 @ i value; outer loop | |
LDR R3, =#0 @ j value; inner loop | |
SUB R4, R1, #1 @ R4 = N(Number of elements)-1 | |
LDR R5, =#0 @ temporary register | |
LDR R6, =#0 @ temporary register | |
LDR R7, =#0 @ temporary register | |
LDR R8, =#0 @ Swap Counter | |
PUSH {R14} | |
@ START | |
@B SUBROUTINE -- Backup Plan | |
FUNCTION1: | |
@ Reset the variables | |
LDR R3, =#0 @ j value; inner loop | |
LDR R5, =#0 @ temporary register | |
LDR R6, =#0 @ temporary register | |
LDR R7, =#0 @ temporary register | |
@PUSH {R14} @ Store the return address value to Stack register safely! | |
CMP R2, R4 @ check if R2 == 5; if its equal ... | |
ITTTT EQ @ Set the equal flag when R2 - R4 = 0 | |
MOVEQ R0, R8 | |
POPEQ {R14} | |
POPEQ {R2-R8} | |
BXEQ LR @if the loop has finished, end the loop. | |
PUSH {R0} | |
BL LOOP | |
@ <After LOOP ends, come here> | |
POP {R0} | |
ADD R2, #1 @ Increment the outer loop counter | |
@POP {R14} | |
B FUNCTION1 | |
@ END | |
@ Should not execute HERE!!! | |
@ BX LR | |
@ Backup Plan | |
SUBROUTINE: | |
CMP R2, R4 @ check if R2 == 5; if its equal ... | |
IT EQ @ Set the equal flag when R2 - R4 = 0 | |
BXEQ LR @if the loop has finished, end the loop. | |
PUSH {R0} | |
B LOOP | |
@ <come here> | |
POP {R0} | |
ADD R2, #1 @ Increment the outer loop counter | |
B SUBROUTINE @ Loop SUBROUTINE | |
@ BX LR | |
LOOP: | |
CMP R3, R4 @ check if R3 == 5; if its equal ... | |
IT EQ @ Set the equal flag when R2 - R4 = 0 | |
BXEQ LR @if the loop has finished, end the loop. | |
LDR R5, [R0, #0] @ 34 --> 32 | |
LDR R6, [R0, #4] @ 32 --> 34 | |
CMP R6, R5 @ R6 - R5 | |
ITTTT MI @ if the result is negative, conduct the swap operation | |
MOVMI R7, R5 @ Swap the bigger value to temp R7 | |
MOVMI R5, R6 @ Swap the smaller value to R5 | |
MOVMI R6, R7 @ Swap the value in temp R7 R6 | |
STRMI R5, [R0] | |
@ Extension of the above code; when the result is negative | |
ITTT MI @ if the result is negative, conduct the swap operation | |
ADDMI R0, 4 @ Postman Walking to next address | |
STRMI R6, [R0] | |
AddMI R8, #1 @ Add the total_swap counter, if swap is done | |
IT PL @ If dont need to swap, come here | |
ADDPL R0, 4 | |
ADD R3, #1 @ Increment the inner loop counter | |
B LOOP | |
@ Store result in SRAM (4 bytes), static random access memory | |
@.lcomm ADDRESS 4 | |
.end |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/** | |
****************************************************************************** | |
* @project : EE2028 Assignment 1 Program Template | |
* @file : main.c | |
* @author : Shankar, Wei Heng | |
* @brief : Main program body | |
****************************************************************************** | |
* @attention | |
* | |
* <h2><center>© Copyright (c) 2021 STMicroelectronics. | |
* All rights reserved.</center></h2> | |
* | |
* This software component is licensed by ST under BSD 3-Clause license, | |
* the "License"; You may not use this file except in compliance with the | |
* License. You may obtain a copy of the License at: | |
* opensource.org/licenses/BSD-3-Clause | |
* | |
****************************************************************************** | |
*/ | |
#include "stdio.h" | |
#define M 6 // No. of numbers in array | |
// #define M 2 // No. of numbers in array | |
// Necessary function to enable printf() using semihosting | |
extern void initialise_monitor_handles(void); | |
// Functions to be written | |
extern int bubble_sort(int* arg1, int arg2); | |
int main(void) | |
{ | |
// Necessary function to enable printf() using semihosting | |
initialise_monitor_handles(); | |
int arr[M] = {18, 34, 32, 75, 11, 97}; | |
// int arr[M] = {18, 9}; | |
int swap,i; // no. of total swaps | |
// Bubble sort with bubble_sort.s | |
swap = bubble_sort((int*)arr, (int)M); | |
printf("After %d rounds of swap, the array is sorted as: \n{ ", swap); | |
// int *p = 0x20017FE4; | |
// printf("%d \n", *p); | |
for (i=0; i<M; i++) | |
{ | |
printf("%d ", arr[i]); | |
} | |
printf("}\n"); | |
// Infinite loop | |
while(1){} | |
} |
/*
* bubble_sort.s
*
* Created on: 4/8/2022
* Author: Shankar
* Author: Wei Heng
*/
.syntax unified
.cpu cortex-m4
.fpu softvfp
.thumb
.global bubble_sort
@ Start of executable code
.section .text
@ EE2028 Assignment 1, Sem 1, AY 2022/23
@ (c) ECE NUS, 2022
@ Bubble sort arr in decending order
@ Write Student 1’s Name here: Shankar
@ Write Student 2’s Name here: Wei Heng
@ You could create a look-up table of registers here:
@ R0 contains the address of the first element in the array
@ R1 contains the literal value 6
@ R2 i; outer loop counter
@ R3 j; inner loop counter
@ R4 len(array) - 1
@ R5 temporary register used to swap elements
@ R6 temporary register used to swap elements
@ R7 temporary register used to swap elements
@ R8 Total Swap Counter; increment by 1 if a swap operation is perfomed
@ R9 Local Swap Counter; if (R9 == no.of elements) {array is sorted so exit the asm function}
@ write your program from here:
bubble_sort:
PUSH {R2-R9} @ Help us preserve the "marking" when we navigate back to main function in main.c
@Initialise the registers here -- Only Execute for the first time
LDR R2, =#0 @ i value; outer loop
LDR R3, =#0 @ j value; inner loop
SUB R4, R1, #1 @ R4 = N(Number of elements)-1
LDR R5, =#0 @ temporary register used to swap elements
LDR R6, =#0 @ temporary register used to swap elements
LDR R7, =#0 @ temporary register used to swap elements
LDR R8, =#0 @ Total Swap Counter; increment by 1 if a swap operation is perfomed
LDR R9, =#0 @ ++1st Additions(4)++ @ Local Swap Counter; if (R9 == no.of elements) {array is sorted so exit the asm function}
PUSH {R14} @ Store the return address value to Stack Register safely used to navigate back to main function in main.c
@B SUBROUTINE -- Backup Plan
FUNCTION1:
CMP R2, R4 @ check if outer loop counter == 5; if its equal, we have gone through the max no. of iterations
ITTTT EQ @ Set the equal flag when R2 - R4 = 0
MOVEQ R0, R8
POPEQ {R14}
POPEQ {R2-R9} @ Set the R2-R9 registers back to the original values
BXEQ LR @if the loop has finished, end the loop to return back to main function in main.c file
CMP R9, R4 @ ++2nd Additions(4)++ @ check if local swap counter == 5; if its equal meaning no swap took place, the array is sorted.
ITTTT EQ @ Set the equal flag when R9 - R4 = 0
MOVEQ R0, R8
POPEQ {R14}
POPEQ {R2-R9} @ Set the R2-R9 registers back to the original values
BXEQ LR @if the loop has finished, end the loop to return back to main function in main.c file
@ Reset the variables after every ith iteration (every outer loop iteration)
LDR R3, =#0 @ j value; inner loop
LDR R5, =#0 @ temporary register used to swap elements
LDR R6, =#0 @ temporary register used to swap elements
LDR R7, =#0 @ temporary register used to swap elements
LDR R9, =#0 @ ++3rd Additions (4)++ @ set local swap counter to 0
PUSH {R0}
BL LOOP
@ <After LOOP ends, come here>
POP {R0} @ Reset the R0 pointer back to the memory address pointing to the first element in the array
ADD R2, #1 @ Increment the outer loop counter
B FUNCTION1 @ Loop back to the start of FUNCTION1 subroutine
@ Backup Plan
SUBROUTINE:
CMP R2, R4 @ check if R2 == 5; if its equal ...
IT EQ @ Set the equal flag when R2 - R4 = 0
BXEQ LR @if the loop has finished, end the loop.
PUSH {R0}
B LOOP
@ <come here>
POP {R0}
ADD R2, #1 @ Increment the outer loop counter
B SUBROUTINE @ Loop SUBROUTINE
@ BX LR
LOOP:
CMP R3, R4 @ check if inner_loop_counter == 5; if its equal, we have completed 1 iteration
IT EQ @ Set the equal flag when R2 - R4 = 0
BXEQ LR @ if the loop has finished, end the loop.
LDR R5, [R0, #0] @ De-Reference the memory address in (R0 + 0) ... (R0 + 4)
LDR R6, [R0, #4] @ De-Reference the memory address in (R0 + 4) ... (R0 + 8)
CMP R6, R5 @ CMP performs R6 - R5
ITTTT MI @ if the result of the above operation is negative, perform the swap operation
MOVMI R7, R5 @ Swap the bigger value to temp R7
MOVMI R5, R6 @ Swap the smaller value to R5
MOVMI R6, R7 @ Swap the value in temp R7 R6
STRMI R5, [R0]
@ Extension of the above code; when the result is negative
ITTT MI @ if the result is negative, perform the swap operation
ADDMI R0, 4 @ Move R0 pointer by 4 bytes to point to the next subsequent memory location
STRMI R6, [R0]
ADDMI R8, #1 @ Increment the total_swap counter by 1, if swap is done
ITT PL @ If dont need to swap, come here
ADDPL R0, 4 @ Move R0 pointer by 4 bytes to point to the next subsequent memory location
ADDPL R9, #1 @ ++4th Additions(4)++ @ Increment the local swap counter
ADD R3, #1 @ Increment the inner loop counter
B LOOP @ Loop back to the start of LOOP subroutine
.end
Changes
Additions
- More comments added
- Cleaned up whitespace
- Added local swap counter; meaning if no swaps took place; array is sorted and end the asm function; go back to main
Deletions
- NIL
CMP R9,R4 executes when innerloop completed with R9 == R4 number of times of no swap required.
/*
* bubble_sort.s
*
* Created on: 4/8/2022
* Author: Shankar
* Author: Wei Heng
*/
.syntax unified
.cpu cortex-m4
.fpu softvfp
.thumb
.global bubble_sort
@ Start of executable code
.section .text
@ EE2028 Assignment 1, Sem 1, AY 2022/23
@ (c) ECE NUS, 2022
@ Bubble sort arr in decending order
@ Write Student 1’s Name here: Shankar
@ Write Student 2’s Name here: Wei Heng
@ You could create a look-up table of registers here:
@ R0 contains the address of the first element in the array
@ R1 contains the literal value 6
@ R2 i; outer loop counter
@ R3 j; inner loop counter
@ R4 len(array) - 1
@ R5 temporary register used to swap elements
@ R6 temporary register used to swap elements
@ R7 temporary register used to swap elements
@ R8 Total Swap Counter; increment by 1 if a swap operation is perfomed
@ R9 Local Swap Counter; if (R9 == no.of elements) {array is sorted so exit the asm function} else {set to 0}
@ write your program from here:
bubble_sort:
PUSH {R2-R9} @ Help us preserve the "marking" when we navigate back to main function in main.c
@Initialise the registers here -- Only Execute for the first time
LDR R2, =#0 @ i value; outer loop
LDR R3, =#0 @ j value; inner loop
SUB R4, R1, #1 @ R4 = N(Number of elements)-1
LDR R5, =#0 @ temporary register used to swap elements
LDR R6, =#0 @ temporary register used to swap elements
LDR R7, =#0 @ temporary register used to swap elements
LDR R8, =#0 @ Total Swap Counter; increment by 1 if a swap operation is perfomed
LDR R9, =#0 @ ++1st Additions(4)++ @ Zero Swap Counter; if (R9 == no.of elements) {array is sorted so exit the asm function}
PUSH {R14} @ Store the return address value to Stack Register safely used to navigate back to main function in main.c
OUTER_LOOP:
CMP R2, R4 @ check if outer loop counter == 5; if its equal, we have gone through the max no. of iterations
ITTTT EQ @ Set the equal flag when R2 - R4 = 0
MOVEQ R0, R8
POPEQ {R14}
POPEQ {R2-R9} @ Set the R2-R9 registers back to the original values
BXEQ LR @if the loop has finished, end the loop to return back to main function in main.c file
CMP R9, R4 @ ++2nd Additions(4)++ @ check if zero swap counter == 5; if its equal meaning no swap took place, the array is sorted.
ITTTT EQ @ Set the equal flag when R9 - R4 = 0
MOVEQ R0, R8
POPEQ {R14}
POPEQ {R2-R9} @ Set the R2-R9 registers back to the original values
BXEQ LR @if the loop has finished, end the loop to return back to main function in main.c file
@ Reset the variables after every ith iteration (every outer loop iteration)
LDR R3, =#0 @ j value; inner loop
LDR R5, =#0 @ temporary register used to swap elements
LDR R6, =#0 @ temporary register used to swap elements
LDR R7, =#0 @ temporary register used to swap elements
LDR R9, =#0 @ ++3rd Additions (4)++ @ set zero swap counter to 0
PUSH {R0}
BL INNER_LOOP
@ <After INNER_LOOP ends, come here>
POP {R0} @ Reset the R0 pointer back to the memory address pointing to the first element in the array
ADD R2, #1 @ Increment the outer loop counter
B OUTER_LOOP @ Loop back to the start of OUTER_LOOP subroutine
INNER_LOOP:
CMP R3, R4 @ check if inner_loop_counter == 5; if its equal, we have completed 1 iteration
IT EQ @ Set the equal flag when R2 - R4 = 0
BXEQ LR @ if the loop has finished, end the loop.
LDR R5, [R0, #0] @ De-Reference the memory address in (R0 + 0) ... (R0 + 4)
LDR R6, [R0, #4] @ De-Reference the memory address in (R0 + 4) ... (R0 + 8)
CMP R6, R5 @ CMP performs R6 - R5
ITTTT MI @ if the result of the above operation is negative, perform the swap operation
MOVMI R7, R5 @ Swap the bigger value to temp R7
MOVMI R5, R6 @ Swap the smaller value to R5
MOVMI R6, R7 @ Swap the value in temp R7 R6
STRMI R5, [R0]
@ Extension of the above code; when the result is negative
ITTT MI @ if the result is negative, perform the swap operation
ADDMI R0, 4 @ Move R0 pointer by 4 bytes to point to the next subsequent memory location
STRMI R6, [R0]
ADDMI R8, #1 @ Increment the total_swap counter by 1, if swap is done
ITT PL @ If dont need to swap, come here
ADDPL R0, 4 @ Move R0 pointer by 4 bytes to point to the next subsequent memory location
ADDPL R9, #1 @ ++4th Additions(4)++ @ Increment the zero swap counter
ADD R3, #1 @ Increment the inner loop counter
B INNER_LOOP @ Loop back to the start of INNER_LOOP subroutine
.end
/**
******************************************************************************
* @project : EE2028 Assignment 1 Program Template
* @file : main.c
* @author : Shankar, Wei Heng
* @brief : Main program body
******************************************************************************
* @attention
*
* <h2><center>© Copyright (c) 2021 STMicroelectronics.
* All rights reserved.</center></h2>
*
* This software component is licensed by ST under BSD 3-Clause license,
* the "License"; You may not use this file except in compliance with the
* License. You may obtain a copy of the License at:
* opensource.org/licenses/BSD-3-Clause
*
******************************************************************************
*/
#include "stdio.h"
// #define M 6 // No. of numbers in array
// #define M 3 // No. of numbers in array
// Necessary function to enable printf() using semihosting
extern void initialise_monitor_handles(void);
// Function Definitions
extern int bubble_sort(int *arg1, int arg2);
int BubbleSort(int arr[], int size);
int main(void) {
// Necessary function to enable printf() using semihosting
initialise_monitor_handles();
int arr[] = { -18, -34, -32, -75, 11, 97 };
int arr_for_c[] = { -18, -34, -32, -75, 11, 97 };
int swap, i; // no. of total swaps
int M = sizeof(arr) / sizeof(int);
printf("Length of the array = %d \n", M);
// Bubble sort with bubble_sort.s
swap = bubble_sort((int*)arr, (int)M);
printf("After %d rounds of swap, the array is sorted as: \n{ ", swap);
for (i = 0; i < M; i++) {
printf("%d ", arr[i]);
}
printf("}\n");
// Bubble sort implemented in C
swap = BubbleSort(arr_for_c, (int) M);
printf("\n It took %d rounds of swap for the array to be sorted. \n{ ", swap);
// Infinite loop
while (1) {
}
}
int BubbleSort(int arr[], int size) {
int i, j, temp, flag = 0;
int total_swap_counter = 0;
for (i = 0; i < size; i++) {
flag = 0;
for (j = 0; j < size - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
flag = 1;
temp = arr[j + 1]; // Swap operation
arr[j + 1] = arr[j];
arr[j] = temp;
total_swap_counter += 1;
}
}
if (flag == 0) { // array is already sorted
// printf("\n Array is already Sorted!!");
printf("\n The array Sorted in ascending order is :\n");
printf("{");
for (i = 0; i < size; i++) {
printf(" %d ", arr[i]);
}
printf("}");
return total_swap_counter;
}
}
return total_swap_counter;
}
Changes
- Subroutine names updated
- Removed subroutine
SUBROUTINE
- can also sort negative numbers
- added bubble sort c to main.c file
Author : Wei Heng
/*
* bubble_sort.s
*
* Created on: 4/8/2022
* Author: Shankar
* Author: Wei Heng
*/
.syntax unified
.cpu cortex-m4
.fpu softvfp
.thumb
.global bubble_sort
@ Start of executable code
.section .text
@ EE2028 Assignment 1, Sem 1, AY 2022/23
@ (c) ECE NUS, 2022
@ Bubble sort array in ascending order
@ Write Student 1’s Name here: Shankar
@ Write Student 2’s Name here: Wei Heng
@ You could create a look-up table of registers here:
@ R0 contains the address of the first element in the array
@ R1 contains the literal value 6
@ R2 i; outer loop counter and j; inner loop counter
@ R3 number of elements - 1
@ R4 temporary register used to swap elements
@ R5 temporary register used to swap elements
@ R6 Total Swap Counter; increment by 1 if a swap operation is perfomed
@ R7 Local Swap Counter; if (R9 == no.of elements) {array is sorted so exit the asm function} else {set to 0}
bubble_sort:
PUSH {R2-R7} @ Help us preserve the "marking" when we navigate back to main function in main.c
PUSH {R14} @ Store the return address value to Stack Register safely used to navigate back to main function in main.c
@ Initialize the registers here -- Execute this portion for the first time ONLY
LDR R2, =#0 @ Set Loops counter to 0
SUB R3, R1, #1 @ R3 = N(Number of elements)-1
LDR R4, =#0 @ temporary register used to swap elements
LDR R5, =#0 @ temporary register used to swap elements
LDR R6, =#0 @ Total Swap Counter; increment by 1 if a swap operation is perfomed
LDR R7, =#0 @ Zero Swap Counter
B OUTER_LOOP @ Branch to OUTER_LOOP
OUTER_LOOP:
CMP R2, R3 @ check if outer loop counter == 5; if its equal, we have gone through the max no. of iterations
ITTTT EQ @ Set the equal flag when R2 - R3 = 0
MOVEQ R0, R6 @ Move R6 total swap counter value to R0 to return back to the main function in main.c
POPEQ {R14}
POPEQ {R2-R7} @ Set the R2-R7 registers back to the original values
BXEQ LR @if the loop has finished, end the loop to return back to main function in main.c file
CMP R7, R3 @ Check if zero swap counter == 5; if its equal, meaning the array is already sorted.
ITTTT EQ @ Set the equal flag when R7 - R3 = 0
MOVEQ R0, R6 @ Move R6 total swap counter value to R0 to return back to the main function in main.c
POPEQ {R14}
POPEQ {R2-R7} @ Set the R2-R7 registers back to the original values
BXEQ LR @if the loop has finished, end the loop to return back to main function in main.c file
PUSH {R2} @ Retaining OUTER_LOOP counter
PUSH {R0} @ Retaining array 1st address
@ Reset the variables after every ith iteration (every outer loop iteration)
LDR R2, =#0 @ initialise counter for INNER_LOOP usage
LDR R4, =#0 @ temporary register used to store elements; not necessary to perform this instruction
LDR R5, =#0 @ temporary register used to store elements; not necessary to perform this instruction
LDR R7, =#0 @ set zero swap counter to 0
BL INNER_LOOP
@ After INNER_LOOP completed, execute the following:
POP {R0} @ Reset the R0 pointer back to the memory address pointing to the first element in the array
POP {R2} @ Retrieving previous OUTER_LOOP counter
ADD R2, #1 @ OUTER_LOOP counter increment
B OUTER_LOOP @ Loop back to the start of OUTER_LOOP subroutine
INNER_LOOP:
CMP R2, R3 @ check if inner_loop_counter == 5; if its equal, we have completed 1 iteration
IT EQ @ Executes when R2 - R3 = 0
BXEQ LR @ If the loop has finished, links back to OUTER_LOOP.
LDR R4, [R0, #0] @ De-Reference the memory address in (R0 + 0) ... (R0 + 4)
LDR R5, [R0, #4] @ De-Reference the memory address in (R0 + 4) ... (R0 + 8)
CMP R5, R4 @ CMP performs R5 - R4
ITTTT MI @ If the result of the above operation is negative, perform the swap operation
STRMI R5, [R0] @ Storing smaller value to address R0
ADDMI R0, #4 @ Increment R0 pointer by 4
STRMI R4, [R0] @ Storing larger values to next address
ADDMI R6, #1 @ Add swap count
ITT PL @ If dont need to swap, come here
ADDPL R0, #4 @ Move R0 pointer by 4 bytes to point to the next subsequent memory location
ADDPL R7, #1 @ Increments the zero swap counter by 1
ADD R2, #1 @ Increment the INNER_LOOP counter
B INNER_LOOP @ Loop back to INNER_LOOP subroutine
.end
Changes
- Optimized assembly code to 6 registers
- Tested and debug the code
- Peer Reviewed
- Modified comments by changing to the appropriate register values
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Bubble Sort
Bubble sort is comparison-based algorithm as it compares pairs of elements of the array and decide whether to swap them or not. It is the
easiest to implement but also not the most efficient, as they run in O(N^2).
Given an array of N elements, Bubble Sort will:
(the last pair is the (N-2)-th and (N-1)-th items as we use 0-based indexing),
We then reduce N by 1 and repeat Step 1 until we have N = 1.
Bubble Sort: Early Termination
Bubble Sort is actually inefficient with its O(N^2) time complexity. Imagine that we have N = 10^5 numbers. Even if our computer is super fast and can compute 10^8 operations in 1 second, Bubble Sort will need about 100 seconds to complete.
However, it can be terminated early, e.g. on the small sorted ascending example shown above [3, 6, 11, 25, 39], Bubble Sort can terminates in O(N) time.
The improvement idea is simple: If we go through the inner loop with no swapping at all, it means that the array is already sorted and we can stop Bubble Sort at that point.