-
Notifications
You must be signed in to change notification settings - Fork 252
/
BlockSwapAlgorithmRecursive.rb
68 lines (49 loc) · 1.48 KB
/
BlockSwapAlgorithmRecursive.rb
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
# Block swap algorithm for array rotation(Recursive)
#Initialize A=[0..d-1], B=[d..size-1]
#until size of A is equal to size of B
# a) If A is shorter
# 1. Divide B into Bl and Br such that Br is of same length as A.
# 2. Swap A and Br to change ABlBr into BrBlA.
# 3. Now A is at its final place, so recur on pieces of B.
# b) If A is longer
# 1. Divide A into Al and Ar such that Al is of same length as B.
# 2. Swap Al and B to change AlArB into BArAl.
# 3. Now B is at its final place, so recur on pieces of A.
#Finally when A and B are of equal size, block swap them.
# Recursive Approach
#Driver function
def rotate_array(a, d) #Input array "a" and rotation by "d" elemets
finish =a.length-1
block_swap(a,0,finish,d)
end
def block_swap(a,start,finish,d)
n=finish-start+1
if n>0
if d>n
d%=n
end
if d==0
return a
end
if d==n-d
swap(a,start,start+d,d)
return a
elsif d<n-d
swap(a,start,finish-d+1,d)
block_swap(a,start,finish-d,d)
else
swap(a,start,d,n-d)
block_swap(a,n-d,n-1,(2*d)-n)
end
end
return a
end
#Utility function for swapping
def swap(a,start1,start2,d)
for i in 0...d
temp = a[start1+i]
a[start1+i] = a[start2+i]
a[start2+i] = temp
end
end
rotate_array([1,2,3,4,5,6,7,8,9,10],6)