Geek Answers Handbook

Can someone explain how recursive insertion sorting works?

Assuming A is an array, n is the number of elements in A,

recursive_insertion_sort(A, n)
    IF n > 1 THEN
        recursive_insertion_sort(A, n-1)
        key = A[n]
        i = n - 1
        DOWHILE A[i] > key AND i > 0
            A[i+1] = A[i]
            i = i - 1
        ENDDO
        A[i+1] = temp
    ENDIF
END

Can someone explain how recursion works in this case? There are a few things that I do not understand:

  • I do not understand why we should call the function again if n> 1.
  • Why do we enter (n-1) when we call the function again? Is it really so that we start the whole process with n = 2, the first 2 elements?
  • How does recursion work at all? For example, as soon as we call this function again, do we ignore the code from line 4 and immediately proceed to the second call? Or are we launching the second call in conjunction with the first call?
+4
source share
2 answers

, , : A, n. n, , , , .

, , n > 1.

, , , n . , .. , . , .

(n-1), ?

n - , , n-1 . , , A[1..n-1] . , , - A[n] . DOWHILE: , , , A[n] . , A[n] . A[1..n] .

?

: , , , , .

, 4 ?

, , , . , A[1..n-1] , A[n] .

+5

, , :

recursive_insertion_sort([1, 7, 5, 2], 4)
    | recursive_insertion_sort([1, 7, 5, 2], 3)
    |    | recursive_insertion_sort([1, 7, 5, 2], 2)
    |    |    | recursive_insertion_sort([1, 7, 5, 2], 1) 
    |    | puts 7 in the right position between it ORDERED left values [1] -> [1,7]
    | puts 5 in the right position between it ORDERED left values [1,7] -> [1,5,7]
puts 2 in the right position between it ORDERED left values [1,5,7] -> [1,2,5,7]
+4

More articles:


All Articles