Monthly Archives: July 2012

Red Black Tree Python Implementation

Code adapted from newcenturycomputers.net

Refer “Introduction to Algorithms Third Edition by Cormen, Leiserson, Rivest and Stein” for the algorithm.

BLACK = 0
RED = 1

class RBNode(object):

    def __init__(self, key = None, color = RED):
        self.left = self.right = self.parent = None
        self.color = color
        self.key = key
        self.nonzero = 1

    def __nonzero__(self):
        return self.nonzero

class RBTree:
    def __init__(self):
        self.sentinel = RBNode()
        self.sentinel.left = self.sentinel.right = self.sentinel
        self.sentinel.color = BLACK
        self.sentinel.nonzero = 0
        self.root = self.sentinel
        self.elements = 0

    def rotateLeft(self, x):

        y = x.right

        # establish x.right link
        x.right = y.left
        if y.left != self.sentinel:
            y.left.parent = x

        # establish y.parent link
        if y != self.sentinel:
            y.parent = x.parent
        if x.parent:
            if x == x.parent.left:
                x.parent.left = y
            else:
                x.parent.right = y
        else:
            self.root = y

        # link x and y
        y.left = x
        if x != self.sentinel:
            x.parent = y

    def rotateRight(self, x):

        #***************************
        #  rotate node x to right
        #***************************

        y = x.left

        # establish x.left link
        x.left = y.right
        if y.right != self.sentinel:
            y.right.parent = x

        # establish y.parent link
        if y != self.sentinel:
            y.parent = x.parent
        if x.parent:
            if x == x.parent.right:
                x.parent.right = y
            else:
                x.parent.left = y
        else:
            self.root = y

        # link x and y
        y.right = x
        if x != self.sentinel:
            x.parent = y

    def insertFixup(self, x):
        #************************************
        #  maintain Red-Black tree balance  *
        #  after inserting node x           *
        #************************************

        # check Red-Black properties

        while x != self.root and x.parent.color == RED:

            # we have a violation

            if x.parent == x.parent.parent.left:

                y = x.parent.parent.right

                if y.color == RED:
                    # uncle is RED
                    x.parent.color = BLACK
                    y.color = BLACK
                    x.parent.parent.color = RED
                    x = x.parent.parent

                else:
                    # uncle is BLACK
                    if x == x.parent.right:
                        # make x a left child
                        x = x.parent
                        self.rotateLeft(x)

                    # recolor and rotate
                    x.parent.color = BLACK
                    x.parent.parent.color = RED
                    self.rotateRight(x.parent.parent)
            else:

                # mirror image of above code

                y = x.parent.parent.left

                if y.color == RED:
                    # uncle is RED
                    x.parent.color = BLACK
                    y.color = BLACK
                    x.parent.parent.color = RED
                    x = x.parent.parent

                else:
                    # uncle is BLACK
                    if x == x.parent.left:
                        x = x.parent
                        self.rotateRight(x)

                    x.parent.color = BLACK
                    x.parent.parent.color = RED
                    self.rotateLeft(x.parent.parent)

        self.root.color = BLACK

    def deleteFixup(self, x):
        #************************************
        #  maintain Red-Black tree balance  *
        #  after deleting node x            *
        #************************************

        while x != self.root and x.color == BLACK:
            if x == x.parent.left:
                w = x.parent.right
                if w.color == RED:
                    w.color = BLACK
                    x.parent.color = RED
                    self.rotateLeft(x.parent)
                    w = x.parent.right

                if w.left.color == BLACK and w.right.color == BLACK:
                    w.color = RED
                    x = x.parent
                else:
                    if w.right.color == BLACK:
                        w.left.color = BLACK
                        w.color = RED
                        self.rotateRight(w)
                        w = x.parent.right

                    w.color = x.parent.color
                    x.parent.color = BLACK
                    w.right.color = BLACK
                    self.rotateLeft(x.parent)
                    x = self.root

            else:
                w = x.parent.left
                if w.color == RED:
                    w.color = BLACK
                    x.parent.color = RED
                    self.rotateRight(x.parent)
                    w = x.parent.left

                if w.right.color == BLACK and w.left.color == BLACK:
                    w.color = RED
                    x = x.parent
                else:
                    if w.left.color == BLACK:
                        w.right.color = BLACK
                        w.color = RED
                        self.rotateLeft(w)
                        w = x.parent.left

                    w.color = x.parent.color
                    x.parent.color = BLACK
                    w.left.color = BLACK
                    self.rotateRight(x.parent)
                    x = self.root

        x.color = BLACK

    def insertNode(self, key):
        #**********************************************
        #  allocate node for data and insert in tree  *
        #**********************************************

        # find where node belongs
        current = self.root
        parent = None
        while current != self.sentinel:
            parent = current
            if key < current.key:
                current = current.left
            else:
                current = current.right

        # setup new node
        x = RBNode(key)
        x.left = x.right = self.sentinel
        x.parent = parent

        self.elements = self.elements + 1

        # insert node in tree
        if parent:
            if key < parent.key:
                parent.left = x
            else:
                parent.right = x
        else:
            self.root = x

        self.insertFixup(x)
        return x

    def deleteNode(self, z):
        #****************************
        #  delete node z from tree  *
        #****************************

        if not z or z == self.sentinel:
            return

        if z.left == self.sentinel or z.right == self.sentinel:
            # y has a self.sentinel node as a child
            y = z
        else:
            # find tree successor with a self.sentinel node as a child
            y = z.right
            while y.left != self.sentinel:
                y = y.left

        # x is y's only child
        if y.left != self.sentinel:
            x = y.left
        else:
            x = y.right

        # remove y from the parent chain
        x.parent = y.parent
        if y.parent:
            if y == y.parent.left:
                y.parent.left = x
            else:
                y.parent.right = x
        else:
            self.root = x

        if y != z:
            z.key = y.key

        if y.color == BLACK:
            self.deleteFixup(x)

        del y
        self.elements = self.elements - 1

    def findNode(self, key):
        #******************************
        #  find node containing data
        #******************************

        current = self.root

        while current != self.sentinel:
            if key == current.key:
                return current
            else:
                if key < current.key:
                    current = current.left
                else:
                    current = current.right

        return None

    def successor(self,node):
        if not node:
            return
        if node.right:
            n = node.right
            while n.left:
                n = n.left
            return n
        else:
            n = node
            while n.parent and n.parent.right is n:
                n = n.parent
            if n.parent and n.parent.left is n:
                return n.parent
            else:
                return

    def predecessor(self,node):
        if not node:
            return
        if node.left:
            n = node.left
            while n.right:
                n = n.right
            return n
        else:
            n = node
            while n.parent and n.parent.left is n:
                n = n.parent
            if n.parent and n.parent.right is n:
                return n.parent
            else:
                return

sourcecode : git

Balanced Binary Search Tree

Leave a reply

Deletion Algorithm:

Update Height
Identify height imbalance
Check and do if single rotation is possible else if double rotation if possible

        self.height = 0

def delete(x,T,parent=None):
    if T is None:
        print('Element Not Found')
    elif x<T.data:
        T.left = delete(x,T.left,T)
        if height(T.right) - height(T.left) ==2:
            if T.right.right:
                T = singleRotationWithRight(T)
            elif T.right.left:
                T = doubleRotationWithRight(T)
    elif x>T.data:
        T.right = delete(x,T.right,T)
        if height(T.left) - height(T.right) ==2:
            if T.left.left:
                T = singleRotationWithLeft(T)
            elif T.left.right:
                T = doubleRotationWithLeft(T)
    elif T.count==1:
        # 2 CHILDREN
        if T.left and T.right:
            TempNode = findMin(T.right)
            T.data = TempNode.data
            T.right = delete(TempNode.data,T.right,T)
            #No need to check for rotation here, taken care above
        # 0 CHILDREN
        elif T.left is None and T.right is None:
            T = None
        # 1 CHILDREN
        elif T.right is not None:
            T = T.right
            T.parent = parent
        elif T.left is not None:
            T = T.left
            T.parent = parent
    else:
        T.count = T.count - 1
    if T:
        T.height = max(height(T.left),height(T.right)) + 1
    return T

def insert(x,T,parent=None):
    if T is None:
        T = BSTNode(x,parent)
    elif x<T.data:
        T.left = insert(x,T.left,T)
        if height(T.left) - height(T.right) ==2:
            if x<T.left.data:
                T = singleRotationWithLeft(T)
            else:
                T = doubleRotationWithLeft(T)
    elif x>T.data:
        T.right = insert(x,T.right,T)
        if height(T.right) - height(T.left) ==2:
            if x>T.right.data:
                T = singleRotationWithRight(T)
            else:
                T = doubleRotationWithRight(T)
    else:
        T.count = T.count + 1
    T.height = max(height(T.left),height(T.right)) + 1
    return T

def height(P):
    if P is None:
        return -1
    else:
        return P.height

def singleRotationWithLeft(K2):
    K1 = K2.left
    K2.left = K1.right
    K1.right = K2

    K1.height = max(height(K1.left),height(K1.right)) + 1
    K2.height = max(height(K2.left),height(K2.right)) + 1
    return K1

def doubleRotationWithLeft(K3):
    K3.left = singleRotationWithRight(K3.left)
    return singleRotationWithLeft(K3)

def singleRotationWithRight(K1):
    K2 = K1.right
    K1.right = K2.left
    K2.left = K1

    K1.height = max(height(K1.left),height(K1.right)) + 1
    K2.height = max(height(K2.left),height(K2.right)) + 1
    return K2

def doubleRotationWithRight(K1):
    K1.right = singleRotationWithLeft(K1.right)
    return singleRotationWithRight(K1)

test

T = None

T = insert(4,T)
T = insert(2,T)
T = insert(6,T)
T = insert(1,T)

T = insert(3,T)
T = insert(5,T)
T = insert(7,T)

T = insert(16,T)
T = insert(15,T)
T = insert(14,T)
T = insert(13,T)

T = insert(12,T)
T = insert(11,T)
T = insert(10,T)
T = insert(8,T)

""" """

T = delete(5,T)
T = delete(6,T)
T = delete(1,T)

preorder(T)

T = delete(14,T)
T = delete(16,T)
T = delete(15,T)

preorder(T)
inorder(T)

output

13
    7
        3
            2
            4
        11
            10
                8
            12
    15
        14
        16
7
    3
        2
        4
    11
        10
            8
        13
            12
2 (4) 
('back:', 2)
3 (2) 
('next:', 4)
4  
('back:', 4)
7 (6) 
('next:', 8)
8 (10) 
('next:', 10)
('back:', 8)
10 (11) 
('next:', 11)
('back:', 10)
11 (12) 
('next:', 12)
12 (13) 
('next:', 13)
('back:', 12)
13 (14)

git

unable to make it work for deletion… please refer to red and black trees and Algorithms

Binary Search Tree Python Library

Leave a reply

Count, Parent Pointers

Parent pointers are easily implemented for insertion as the recursion travels top to bottom a copy of the parent is maintained. During deletion, There is no need to reallocate the pointer when data from a successor is copied or when a node is completely deleted. Except when a node is equated to either of its left or right children Its new parent has to be updated from current which is going to be deleted to the currents parent which can be obtained as a recursion parameter.

class BSTNode:
    def __init__(self,x,parent):
        self.data = x
        self.left = None
        self.right = None
        self.count = 1
        self.parent = parent

Insertion

def insert(x,T,parent=None):
    if T is None:
        T = BSTNode(x,parent)
    elif x<T.data:
        T.left = insert(x,T.left,T)
    elif x>T.data:
        T.right = insert(x,T.right,T)
    else:
        T.count = T.count + 1
    return T

Deletion

Similar to heaps, a bubble has to be created and moved down untill a leaf node can be deleted. Here its a little bit complex because of the extra constraints. An element is replaced by its child successor repeatedly until a leaf node or a node with single child is reached which is easily deleted. The recursive definition is easy and elegant.

def delete(x,T,parent=None):
    if T is None:
        print('Element Not Found')
    elif x<T.data:
        T.left = delete(x,T.left,T)
    elif x>T.data:
        T.right = delete(x,T.right,T)
    elif T.count==1:
        # 2 CHILDREN
        if T.left and T.right:
            TempNode = findMin(T.right)
            T.data = TempNode.data
            T.right = delete(TempNode.data,T.right,T)
        # 0 CHILDREN
        elif T.left is None and T.right is None:
            T = None
        # 1 CHILDREN
        elif T.right is not None:
            T = T.right
            T.parent = parent
        elif T.left is not None:
            T = T.left
            T.parent = parent
    else:
        T.count = T.count - 1
    return T

def findMin(T):
    if T.left:
        return findMin(T.left)
    else:
        return T

In order Successor

either (left most child of right child or right child) or (left farthest parent’s right parent or right parent)

def next(node):
    if node is None:
        return
    if node.right:
        n = node.right
        while n.left:
            n = n.left
        return n
    else:
        n = node
        while n.parent and n.parent.right is n:
            n = n.parent
        if n.parent and n.parent.left is n:
            return n.parent
        else:
            return

In order Predecessor

either (right most child of left child or left child) or (right farthest parent’s left parent or left parent)

def back(node):
    if node is None:
        return
    if node.left:
        n = node.left
        while n.right:
            n = n.right
        return n
    else:
        n = node
        while n.parent and n.parent.left is n:
            n = n.parent
        if n.parent and n.parent.right is n:
            return n.parent
        else:
            return

Inorder

import sys
def inorder(T):
    if T is None:
        return
    else:
        inorder(T.left)
        b = back(T)
        if b:
            print("back:",b.data)
        sys.stdout.write(str(T.data)+" ")
        if T.parent:
            sys.stdout.write("("+str(T.parent.data)+")")
        print(" ")
        n = next(T)
        if n:
            print("next:",n.data)
        inorder(T.right)

Preorder

def preorder(T,i=0):
    if T is None:
        return
    else:
        for j in range(i):
            sys.stdout.write("    ")
        print(T.data)
        preorder(T.left,i+1)
        preorder(T.right,i+1)

Test

T = None
T = insert(7,T)
T = insert(4,T)
T = insert(2,T)
T = insert(1,T)

T = insert(13,T)
T = insert(15,T)
T = insert(16,T)
T = insert(6,T)

T = insert(5,T)
T = insert(3,T)
T = insert(11,T)
T = insert(14,T)

T = insert(12,T)
T = insert(9,T)
T = insert(8,T)
T = insert(10,T)

T = delete(11,T)
T = delete(12,T)
T = delete(13,T)
T = delete(8,T)
T = delete(6,T)
T = delete(7,T)
preorder(T)
inorder(T)

Output

9
    4
        2
            1
            3
        5
    14
        10
        15
            16
1 (2) 
('next:', 2)
('back:', 1)
2 (4) 
('next:', 3)
('back:', 2)
3 (2) 
('next:', 4)
('back:', 3)
4 (9) 
('next:', 5)
('back:', 4)
5 (4) 
('next:', 9)
('back:', 5)
9  
('next:', 10)
('back:', 9)
10 (14) 
('next:', 14)
('back:', 10)
14 (9) 
('next:', 15)
('back:', 14)
15 (14) 
('next:', 16)
('back:', 15)
16 (15)

Red Black Tree Python Implementation

git

O(h) algo for the Inorder Successor/Predecessor of a Binary Search Tree Node using parent pointers!

Leave a reply

class Node:
	def __init__(self, data):
		"""
		Node constructor

		@param data node data object
		"""
		self.left = None
		self.right = None
		self.data = data
		self.count = 1
		self.parent = None
	
	def preorder(self):
		print(self.data)
		if self.left:
			self.left.preorder()
		if self.right:
			self.right.preorder()
	def postorder(self):
		if self.left:
			self.left.postorder()
		if self.right:
			self.right.postorder()
		print(self.data)
	def inorder(self):
		if self.left:
			self.left.inorder()
		print(self.data)
		b = self.back()
		if b:
			print("back:",b.data)
		n = self.next()
		if n:
			print("next:",n.data)
		if self.right:
			self.right.inorder()
	
	def insert(self, data):
		if data < self.data:
			if self.left is None:
				self.left = Node(data)
				self.left.parent = self
			else:
				self.left.insert(data)
		elif data > self.data:
			if self.right is None:
				self.right = Node(data)
				self.right.parent = self				
			else:
				self.right.insert(data)
		else:
			self.count = self.count + 1

	def lookup(self, data, parent=None):
		if data < self.data:
			if self.left is None:
				return None, None
			return self.left.lookup(data, self)
		elif data > self.data:
			if self.right is None:
				return None, None
			return self.right.lookup(data, self)
		else:
			return self, parent

	def delete(self, data):
		# get node containing data
		node, parent = self.lookup(data)
		if node.count==1:
			if node is not None:
				children_count = node.children_count()

			if children_count == 0:
				# if node has no children, just remove it
				if parent.left is node:
					parent.left = None
				else:
					parent.right = None
			elif children_count == 1:
				# if node has 1 child
				# replace node by its child
				if node.left:
					n = node.left
				else:
					n = node.right
				n.parent = parent
				if parent.left is node:
					parent.left = n
				else:
					parent.right = n
				del node
			else:
				# if node has 2 children
				# find its successor
				parent = node
				successor = node.right
				while successor.left:
					parent = successor
					successor = successor.left
				# replace node data by its successor data
				node.data = successor.data
				# fix successor's parent's child
				if parent.left == successor:
					parent.left = successor.right
					successor.right.parent = parent.left
				else:
					parent.right = successor.right
					successor.right.parent = parent.right
		elif node.count>1:
			node.count = node.count - 1
	
	def children_count(self):
		"""
		Returns the number of children

		@returns number of children: 0, 1, 2
		"""
		if self is None:
			return None
		cnt = 0
		if self.left:
			cnt += 1
		if self.right:
			cnt += 1
		return cnt
	
	def back(self):
		if self.left:
			n = self.left
			while n.right:
				n = n.right
			return n
		else:
			n = self
			while n.parent and n.parent.left is n:
				n = n.parent
			if n.parent and n.parent.right is n:
				return n.parent
			else:
				return None
	
	def next(self):
		if self.right:
			n = self.right
			while n.left:
				n = n.left
			return n
		else:
			n = self
			while n.parent and n.parent.right is n:
				n = n.parent
			if n.parent and n.parent.left is n:
				return n.parent
			return None
		return self

if __name__ == "__main__":
	root = Node(8)
	root.insert(3)
	root.insert(10)
	root.insert(1)
	root.insert(6)
	root.insert(4)
	root.insert(7)
	root.insert(14)
	root.insert(13)
	
	# DELETION
	#root.delete(3)
	
	# FIND
	'''
	node, parent = root.lookup(8)
	if node:
		print(node.data, "x", node.count)
	if parent:
		print("-->", parent.data)
	'''
	
	# NEXT
	#node2 = node.next()
	#node3 = node.back()
	#print("next: ",node2.data)
	#print("back",node3.data)
	
	# TRAVERSAL
	#root.preorder()
	#print("---")
	#root.postorder()
	#print("===")
	root.inorder()

'''
output
1
next: 3
3
back: 1
next: 4
4
back: 3
next: 6
6
back: 4
next: 7
7
back: 6
next: 8
8
back: 7
next: 10
10
back: 8
next: 13
13
back: 10
next: 14
14
back: 13
'''

On-line Insertion into Sorted Arrays BST and Heaps

Leave a reply

Insertion of 50,000 integers in Python
Sorted Array
execution time: 62.228999853134155 seconds
Binary Search Tree
execution time: 0.8529999256134033 seconds
Heap
execution time: 0.15599989891052246 seconds

I can see the array has nothing but leniar progression to figure out the location of an element thus taking so much time. Heaps though need to bubble up unlike BST, functions better than the BST because it is always balanced or depth of tree is lowest.!

Binary Search Tree with Repetition In Python

Leave a reply

minor code adaptations from Laurent Luce’s Blog

refer Weiss for theory!

class Node:
	"""
	Tree node: left and right child + data which can be any object
	"""
	def __init__(self, data):
		"""
		Node constructor

		@param data node data object
		"""
		self.left = None
		self.right = None
		self.data = data
		self.count = 1

	def insert(self, data):
		"""
		Insert new node with data

		@param data node data object to insert
		"""
		if data < self.data:
			if self.left is None:
				self.left = Node(data)
			else:
				self.left.insert(data)
		elif data > self.data:
			if self.right is None:
				self.right = Node(data)
			else:
				self.right.insert(data)
		else:
			self.count = self.count + 1

	def lookup(self, data, parent=None):
		"""
		Lookup node containing data

		@param data node data object to look up
		@param parent node's parent
		@returns node and node's parent if found or None, None
		"""
		if data < self.data:
			if self.left is None:
				return None, None
			return self.left.lookup(data, self)
		elif data > self.data:
			if self.right is None:
				return None, None
			return self.right.lookup(data, self)
		else:
			return self, parent

	def delete(self, data):
		"""
		Delete node containing data

		@param data node's content to delete
		"""
		# get node containing data
		node, parent = self.lookup(data)
		if node.count==1:
			if node is not None:
				children_count = node.children_count()

			if children_count == 0:
				# if node has no children, just remove it
				if parent.left is node:
					parent.left = None
				else:
					parent.right = None
			elif children_count == 1:
				# if node has 1 child
				# replace node by its child
				if node.left:
					n = node.left
				else:
					n = node.right
				if parent.left is node:
					parent.left = n
				else:
					parent.right = n
				del node
			else:
				# if node has 2 children
				# find its successor
				parent = node
				successor = node.right
				while successor.left:
					parent = successor
					successor = successor.left
				# replace node data by its successor data
				node.data = successor.data
				# fix successor's parent's child
				if parent.left == successor:
					parent.left = successor.right
				else:
					parent.right = successor.right
		elif node.count>1:
			node.count = node.count - 1
	
	def children_count(self):
		"""
		Returns the number of children

		@returns number of children: 0, 1, 2
		"""
		if self is None:
			return None
		cnt = 0
		if self.left:
			cnt += 1
		if self.right:
			cnt += 1
		return cnt



if __name__ == "__main__":
	root = Node(8)
	root.insert(3)
	root.insert(3)
	root.insert(10)
	root.insert(1)
	root.insert(6)
	root.insert(4)
	root.insert(7)
	root.insert(14)
	root.insert(13)
	
	root.delete(3)
	root.delete(3)
	
	node, parent = root.lookup(4)
	print(str(node.data) + " x " + str(node.count) + "-->" + str(parent.data))
	node, parent = root.lookup(6)
	print(str(node.data) + " x " + str(node.count) + "-->" + str(parent.data))

Quick Sort

Leave a reply

python

def InsertionSort(numbers):
	N = len(numbers)
	for p in range(1,N):
		temp = numbers[p]
		j=p
		while j>0:
			if numbers[j-1] > temp:
				numbers[j] = numbers[j-1]
			else:
				break
			j = j-1
		numbers[j] = temp

def QS(numbers,left,right):
	if right - left<=2:
		InsertionSort(numbers)
	else:
		center = int((left + right)/2)
		if numbers[left]>numbers[center]:
			numbers[center],numbers[left] = numbers[left],numbers[center]
		if numbers[left]>numbers[right]:
			numbers[left],numbers[right] = numbers[right],numbers[left]
		if numbers[center]>numbers[right]:
			numbers[center],numbers[right] = numbers[right],numbers[center]
		numbers[center],numbers[right-1] =  numbers[right-1],numbers[center]
		pivot = numbers[right-1]
		i = 1
		j=right-2
		while(True):
			while numbers[i]<pivot:
				i=i+1
			while numbers[j]>pivot:
				j=j-1
			if i<j:
				numbers[i],numbers[j]=numbers[j],numbers[i]
			else:
				break;
		numbers[i],numbers[right-1] = numbers[right-1],numbers[i]
		QS(numbers,left,i-1)
		QS(numbers,i+1,right)
C=[0,5,7,3,4,9]
QS(C, 0, len(C) - 1)

private void QuickSort(ref int[] iNumbers, int LEFT, int RIGHT)
        {
            if (RIGHT-LEFT<=2)
            {
                InsertionSort(ref iNumbers, 0, 0);
            }
            else
            {
                //pick pivot using medion of 3 ie ends and middle
                /*ARRAY SWAPING RATHEN THAN SORTING MAKES SURE YOU
                 HAVE THE POSITION TO SWAP PIVOT FINALLY NOT JUST THAT
                 ENSURES LEFT IS SMALLER AND RIGHT IS LAGER THAN PIVOT
                 SO CENTER IS SWAPPED WITH RIGHT-1 AND RIGHT-1 IS PIVOT*/
                int CENTER = (LEFT + RIGHT ) / 2;
                if (iNumbers[LEFT] > iNumbers[CENTER])
                {
                    Swap(ref iNumbers[LEFT], ref iNumbers[CENTER]);
                }
                if (iNumbers[LEFT] > iNumbers[RIGHT])
                {
                    Swap(ref iNumbers[LEFT], ref iNumbers[RIGHT]);
                }
                if (iNumbers[CENTER] > iNumbers[RIGHT])
                {
                    Swap(ref iNumbers[CENTER], ref iNumbers[RIGHT]);
                }
                Swap(ref iNumbers[CENTER], ref iNumbers[RIGHT-1]);
                int Pivot = iNumbers[RIGHT - 1];
                //find s1 - elements lesser than pivot
                //find s2 - elements grater than pivot
                int i = 1, j = RIGHT - 2;
                while (true)
                {
                    for (; iNumbers[i] < Pivot; i++) ;
                    for (; iNumbers[j] > Pivot; j--) ;
                    if (i < j)
                    {
                        Swap(ref iNumbers[i], ref iNumbers[j]);
                    }
                    else
                    {
                        break;
                    }
                }
                Swap(ref iNumbers[i], ref iNumbers[RIGHT - 1]);
                //QuickSort partitions()
                /* when u use*/
                QuickSort(ref iNumbers, LEFT, i - 1);
                QuickSort(ref iNumbers, i + 1, RIGHT);
            }
        }
        private void Swap(ref int p1, ref int p2)
        {
            int temp = p1;
            p1 = p2;
            p2 = temp;
        }

Insertion Sort

Leave a reply

Python

def InsertionSort(numbers):
	N = len(numbers)
	for p in range(1,N):
		temp = numbers[p]
		j=p
		while j>0:
			if numbers[j-1] > temp:
				numbers[j] = numbers[j-1]
			else:
				break
			j = j-1
		numbers[j] = temp

array=[9,1,0,4,7,9,6,3]
InsertionSort(array)
print(array)

private void InsertionSort(ref int[] iNumbers)
        {
            int N = iNumbers.Length;
            /* YOU PICK A POSITION and ENSURE it is INSERTED into the RIGHT PLACE
             * FROM FIRST.
             * UNTILL THEN, U KEEP MOVING/SWAPPING TO RIGHT AND FIT INTO LEFT
             * ASUMING LEFT IS SORTED 
             * STARTING FIRST PASS P=1 and FIRST = ELEMENT 0
             * NEXT P=2 and FIRST = 0,1. so if 1 is grater u swap 1 with 2, 
             * if 0 is grater u swap 0 with 2, 
             * but remember 0 is smaller than 1 from previos pass 
             * so u will need to push 1 one more position to 2, so to avoid this, 
             * u move graters to right and finally swap the number at position*/

            for (int P = 1; P <= N-1; P++)
            {
                int temp = iNumbers[P];
                int j;
                for (j = P; j > 0; j--)
                {
                    if (iNumbers[j - 1] > temp)
                    {
                        iNumbers[j] = iNumbers[j - 1];
                    }
                    else
                    {
                        break;
                    }
                }
                iNumbers[j] = temp;
            }
        }