Merge Sort in c++

#include<iostream>
#include<vector>
using namespace std;

void merge(vector<int> &v,int l, int m,int r)
  {
    vector<int> a(v.begin()+l,v.begin()+m+1);
    vector<int> b(v.begin()+m+1,v.begin()+r+1);
    int ptr1=0,ptr2=0,ptr=l;
    while(ptr1<a.size() && ptr2<b.size())
        if(a[ptr1]<b[ptr2])
            v[ptr++]=a[ptr1++];
        else
            v[ptr++]=b[ptr2++];
    while(ptr1<a.size())
        v[ptr++]=a[ptr1++];
    while(ptr2<b.size())
        v[ptr++]=b[ptr2++];
  }

void mergesort(vector<int> &vec,int l,int r )
   {
      if(l<r)
       {
           int m=(l+(r-1))/2;
           mergesort(vec,l,m);
           mergesort(vec,m+1,r);
           merge(vec,l,m,r);
       }
   }

int main()

  {

    int arr[] ={99,8,22,11,44,55,2,1,5,26,98,8,888,36,99,75,48,74,587,4};
    vector<int> vec(arr,arr+sizeof(arr)/sizeof(int));
    mergesort(vec,0,(vec.size())-1);
    for(int i=0;i<vec.size();i++)
        cout<<vec[i]<<" ";
    return 0;

  }

C++ Program to print a 2-d matrix/vector in spiral order

vector<int> spiralOrder(const vector<vector<int> > &A)

{

    vector<int> result;
    long min_x=0,min_y=0,done=0,count=0,i=0,j=0;
    long n,max_x=A[0].size()-1, m,max_y=A.size()-1;
    long size=(max_x+1)*(max_y+1);
    while(count<size)
        {  
            if(i==min_y && j==min_x)
                {  if(done==1)
                       { min_x++;min_y++;max_x--;max_y--;i=min_y;j=min_x;  }
                    else done=1;
                }
            result.push_back(A[i][j]);
            count++;
            if(i==min_y && j<max_x)        j++;
            else if(i==min_y && j==max_x)  i++;
            else if(i<max_y && j==max_x)   i++;
            else if(i==max_y && j==max_x)  j--;
            else if(i==max_y && j>min_x)   j--;
            else if(i==max_y && j==min_x)  i--;
            else if(i>min_y && j==min_x)   i--;
        }
    return result;
}

Python code for Quick Sort using original Hoare partition scheme

from random import randint
def quicksort(array, low, high):
    if low < high:
        p = partition(array, low, high)
        quicksort(array, low, p)
        quicksort(array, p + 1, high)

def partition(array, low, high):
    pivot = array[low]
    i=low-1
    j=high+1
    while 1:
    i = i + 1
        while array[i] < pivot:
            i = i + 1
        j=j-1
        while array[j] > pivot:
            j=j-1
       
        if i >= j:
            return j
        array[i],array[j]=array[j],array[i]




array=[]
for p in range(10):
    array.append(randint(1,100))

quicksort(array,0,len(array)-1)
print array

Implementation of iterative deepening A* (Star) Algorithm

#node              current node
#g                 the cost to reach current node
#f                 estimated cost of the cheapest path (root..node..goal)
#h(node)           estimated cost of the cheapest path (node..goal)
#cost(node, succ)  step cost function
#is_goal(node)     goal test
#successors(node)  node expanding function
V={}
E={}
V=({'A':7,'B':9,'C':6,'D':5,'E':6,'F':4.5,'H':4,'I':2,'J':3,'K':3.5,'G':0})
E=({('B','D'):2,('A','B'):4,('A','C'):4,('A','D'):7,('D','E'):6,('E','F'):5,('D','F'):8,('D','H'):5,('H','I'):3,('I','J'):3,('J','K'):3,('K','H'):3,('F','G'):5})
INFINITY=10000000
cameFrom={}
def h(node):
    return V[node]
def cost(node, succ):
    return E[node,succ]

def successors(node):
    neighbours=[]
    for item in E:
        if node==item[0][0]:
            neighbours.append(item[1][0])
    return neighbours

def reconstruct_path(cameFrom, current):
    total_path = [current]
    while current in cameFrom:
        current = cameFrom[current]
        total_path.append(current)
    return total_path
   
def ida_star(root,goal):
    global cameFrom
    def search(node, g, bound):
        min_node=None
        global cameFrom
        f = g + h(node)
        if f > bound:return f
        if node==goal:return "FOUND"
        minn = INFINITY
        for succ in successors(node):
            t = search(succ, g + cost(node, succ), bound)
            if t == "FOUND":return "FOUND"
            if t < minn:
                minn = t
                min_node=succ
        cameFrom[min_node]=node
        return minn
       
    bound= h(root)
    count =1
    while 1:
        print "itertion"+str(count)
        count+=1
        t = search(root, 0, bound)
        if t == "FOUND":
            print reconstruct_path(cameFrom, goal)
            return bound
        if t == INFINITY:return "NOT_FOUND"
        bound = t
  
print ida_star('A','G')
   

Implementation of A* algorithm in python

V={}
E={}
V=({'A':7,'B':9,'C':6,'D':5,'E':6,'F':4.5,'H':4,'I':2,'J':3,'K':3.5,'G':0})
E=({('B','D'):2,('A','B'):4,('A','C'):4,('A','D'):7,('D','E'):6,('E','F'):4.5,('D','F'):8,('D','H'):4,('H','I'):3,('I','J'):3,('J','K'):3,('K','H'):3,('F','G'):5})



INFINITY=10000000
def find_neighbours(node):
    neighbours=[]
    for item in E:
        if node==item[0][0]:
            neighbours.append(item[1][0])
    return neighbours
   


def reconstruct_path(cameFrom, current):
    total_path = [current]
    while current in cameFrom:
        current = cameFrom[current]
        total_path.append(current)
    return total_path
    #

def Astar(start, goal):
   
    current = start
    fScore={}
    gScore={}
   
   
   
   
    # The set of currently discovered nodes still to be evaluated.
    openSet = set()
    # The set of nodes already evaluated.
    closedSet = set()
    # Initially, only the start node is known.
    openSet.add(current)
   
    # For each node, which node it can most efficiently be reached from.
    # If a node can be reached from many nodes, cameFrom will eventually contain the
    # most efficient previous step.
    cameFrom ={}#the empty map

    # For each node, the cost of getting from the start node to that node.
    for node in V:
        gScore[node] = INFINITY #map with default value of Infinity
    # The cost of going from start to start is zero.
    gScore[start] = 0
    # For each node, the total cost of getting from the start node to the goal
    # by passing by that node. That value is partly known, partly heuristic.
    for node in V:
        fScore[node] = INFINITY #map with default value of Infinity
    # For the first node, that value is completely heuristic.
    fScore[start] = V[start]#heuristic_cost_estimate(start, goal)
   
    def heuristic_cost_estimate(node, goal):
    return E[cameFrom[node],node]+V[node]
    count=0
    while openSet:
        count+=1
        if count>10:
            break
        print openSet
        minn=INFINITY
        for node in openSet:
            if fScore[node]<minn:
                current=node
        if current==None:
            current=start
        #current = node in openSet having the lowest fScore[] value)
        if current == goal:
            return reconstruct_path(cameFrom, goal)

        openSet.remove(current)
        #Add it to the closed set
        closedSet.add(current)
        for neighbor in find_neighbours(current):
            if neighbor in closedSet:
                continue        # Ignore the neighbor which is already evaluated.
            # The distance from start to goal passing through current and the neighbor.
            tentative_gScore = gScore[current] + E[(current, neighbor)]
            if neighbor not in openSet:    # Discover a new node
                openSet.add(neighbor)
            elif tentative_gScore >= gScore[neighbor]:
                continue        # This is not a better path.

            # This path is the best until now. Record it!
            cameFrom[neighbor] = current
            gScore[neighbor] = tentative_gScore
            fScore[neighbor] = gScore[neighbor] + heuristic_cost_estimate(neighbor, goal)

    return "failure"



print Astar('A','K')