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

Time:05-27

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

  • Related