如果我的数组已经部分排序，如何在排序程序中跳过数组的已排序部分

Question

所以我们在 class 中学习了冒泡排序，我有这段代码

!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

现在我的教授要求我修改它，如果要排序的给定数组的一部分已经在正确的位置，那么我们应该跳过那部分，例如我的数组是 5 3 1 2 4 6 7 8 ，这里 6 7 8 位于正确的位置，那么我们如何编写一个程序，使其自动跳过这最后 3 个元素。

我在网上到处都找遍了，但我找不到它是如何优化冒泡排序的，我只能想办法检查整个数组是否已排序，然后如何在发生排序时结束排序。

提前感谢您的帮助！

Answer 1

我能够使用 2 个不同的子例程解决这个问题，一个是第一次检查遍历数组并检查末尾有多少元素不需要进一步排序，然后我使用另一个子例程来处理其余的冒泡排序运行


!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

这是确定k的第一个子程序，它找到缩小的范围

!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

这是使用数组中缩小范围的常规冒泡排序

在我的主程序中我只是连续调用这两个

如果我的数组已经部分排序，如何在排序程序中跳过数组的已排序部分

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

arrays

sorting

fortran

bubble-sort

fortran90