How to skip sorted part of an array in a sorting program if my array is already partly sorted

Question

So we were taught bubble sort in our class and I have this code

!Sorting n real numbers 
program bubblesort
implicit none   
integer::i,j,n
integer,allocatable,dimension(:)::A 
write(*,*)"Enter the number of elements"
read(*,*)n
allocate (A(n))
write(*,*)"Enter the numbers"
read(*,*)(A(i),i=1,n)
do while (n>1)
    do i=1,n-1
        if(A(i) > A(i+1)) then
            j = A(i)
            A(i) = A(i+1)
            A(i+1) = j
        endif
    enddo
    n = n-1
enddo   
write(*,*)"The sorted array is - ",A
end program

now my professor asked me to modify it in a way that if part of the given array to be sorted is already in the correct place then we should skip that part, for example say my array is 5 3 1 2 4 6 7 8, here 6 7 8 are in the correct place so how can we write a program such that it automatically skips these last 3 elements.

I've looked everywhere online but I couldn't find how it optimize bubble sort in this way, I could only find ways to check if the entire array is sorted and then how to end the sorting when that happens.

Thanks for the help in advance!

Answer 1

I was able to solve this using 2 different subroutines, one is for the first check which goes through the array and checks how many elements at the end do not need further sorting and then I used another subroutine for the rest of the bubble sort runs

!This is the first run of bubble sort to know the range 
subroutine Bubtest(n,A,k)
implicit none
integer::i,j,k,n,A(8)
do i=1,n-1
    if(A(i) > A(i+1)) then
        j = A(i)
        A(i) = A(i+1)
        A(i+1) = j
        k = i
    endif
enddo
k = k+1
end subroutine

This is the first subroutine which determines k, which finds the reduced range

!This is the main bubble sort subroutine
subroutine sortBub(k, A)
implicit none
integer::i,j,k,A(8)
do while (k>1)
    do i=1,k-1
        if(A(i) > A(i+1)) then
            j = A(i)
            A(i) = A(i+1)
            A(i+1) = j
        endif
    enddo
    k = k-1
enddo
end subroutine

And this is for the regular bubble sort using the reduced range in the array

In my main program I just call these two consecutively