It is assumed that there is a list A which has elements which are already sorted.
The task at hand is to insert another element (referred to as key) into the sorted list A so that after the insertion, the list must continue to remain sorted.
The key is made part of the sorted list by increasing the size by 1 and placing it as the last element of the list. Therefore, space complexity is O(1).
An iteration of j is begun from i-1 all the way to 0
The key is compared with the last element A[j-1] of the sorted list. If the element is greater than the key, it is shifted right to A[j].
If key is greater than the element in the list, insertion happens at the location j and the iteration is exited
The function returns with the list containing key and maintaining the sort order.
Algorithm in pseudocode
func INSERT_INTO_SORTEDARRAY:
(input) sorted list, and key to be inserted
(output) sorted list with key inserted
key: <- last element in A // A is already sorted
index: <- length(List) - 1
iterate j from index to 1
if A[j-1] > key then
shift the element right
else
break
if j != index:
A[j] = key // inserted at the right location
return A
end func
Example
Assume sorted list ar = [3, 5, 6, 7] and element to insert is 2.
During the intermediary steps, the contents of ar are as shown below. The key is value 2 and eventually it gets inserted at beginning of the list.
def printarray(arr):
for e in arr: print (e, end = " ")
#print()
def insert_into_sortedArray(ar):
key = ar[-1] # the candidate to insert
i = len(ar)-1 # position of candidate
j = i
while j > 0 and ar[j-1] > key:
printarray(ar)
print("", key)
ar[j] = ar[j-1] # move bigger element right
j = j-1
if j != i:
ar[j] = key
printarray(ar)
Output
# sorted array
ar = [1, 2, 5, 6, 7, 9]
insert_into_sortedArray (ar + [4])
Tower of Hanoi
The Tower of Hanoi problem is a popular puzzle that is used to introduce the concept of Recursion. It also helps to demonstrate the power of recursion in how it can present an elegation solution to a problem of medium complexity.
The rules one must follow when solving the tower puzzle are:
Disks must be removed one at a time from the top of one tower and placed onto the top of another tower.
No disk can be larger than any disk below it (i.e., the disks on each tower make a pyramid shape).
In our three-disc example, we had a simple base case of moving a single disc and a recursive case of moving all of the other discs (two in this case), using the third tower temporarily. We could break the recursive case into three steps:
1\. Move the upper n-1 discs from tower A to B
(the temporary tower), using C as the in-between.
2\. Move the single lowest disc from A to C.
3\. Move the n-1 discs from tower B to C,
using A as the in-between.
The amazing thing is that this recursive algorithm works not only for three discs, but for any number of discs. We will codify it as a function called hanoi() that is responsible for moving discs from one tower to another, given a third temporary tower.
In our Towers of Hanoi solution, we recurse on the largest disk to be moved. That is, we will write a recursive function that takes as a parameter the disk that is the largest disk in the tower we want to move. Our function will also take three parameters indicating from which peg the tower should be moved (source), to which peg it should go (dest), and the other peg, which we can use temporarily to make this happen (spare).
Pseudocode 1
func moveDisk (A, B)
print "Moving top disk from tower {A} to tower {B} "
func towerOfHanoi (n, fromTower, toTower, tempTower)
if (n >= 1)
towerOfHanoi(n-1, fromTower, tempTower, toTower)
moveDisk(fromTower, toTower)
towerOfHanoi(n-1, tempTower, toTower, fromTower)
end func
Pseudocode 2
Pseudo code:
BEGIN
READ disk, source, dest, aux
FUNCTION Hanoi (disk, source, dest, aux)
END
Pseudo code for function Hanoi (disk, source, dest, aux)
BEGIN
IF disk=1 THEN
Move disk from source to dest
ELSE
Hanoi (disk-1, source, aux, dest)
Move disk from source to dest
Hanoi (disk-1, source, aux, dest)
ENDIF
END
Output for 3 disc Hanoi Problem
Move top disk from tower Tower1 to tower Tower2
Move top disk from tower Tower1 to tower Inter
Move top disk from tower Tower2 to tower Inter
Move top disk from tower Tower1 to tower Tower2
Move top disk from tower Inter to tower Tower1
Move top disk from tower Inter to tower Tower2
Move top disk from tower Tower1 to tower Tower2
Python Code
c = 0
def moveTower(height,fromPole, toPole, withPole):
if height == 1:
moveDisk(height, fromPole, toPole)
else:
moveTower(height-1,fromPole,withPole,toPole)
moveDisk(height, fromPole,toPole)
moveTower(height-1,withPole,toPole,fromPole)
def moveDisk(disk, fp,tp):
global c
c += 1
print("Step", c, ": moving Disk", tower[disk], "from",fp,"to",tp)
tower = ['', 'red ', 'green', 'blue ']
moveTower(3, "Start", "Dest", "Middle")
Hanoi Output
Step 1 : moving Disk red from Start to Dest
Step 2 : moving Disk green from Start to Middle
Step 3 : moving Disk red from Dest to Middle
Step 4 : moving Disk blue from Start to Dest
Step 5 : moving Disk red from Middle to Start
Step 6 : moving Disk green from Middle to Dest
Step 7 : moving Disk red from Start to Dest
