arrayssortingfortranbubble-sortfortran90

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

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"
allocate (A(n))
write(*,*)"Enter the numbers"
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!

Solution

• 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