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!
CodePudding user response:
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