zallarak

def InsertionSort(A):
    """ 
    Takes a list, returns a list.
    """
    for j in range(len(A)):
        key = A[j]
        i = j-1 
        while (i>=0) and (A[i]>key):
            A[i+1] = A[i]
            i = i-1

zallarak

def InsertionSort(a)

  a.each_with_index do |item, index|
    i = index - 1 
          
    while i>=0
      break if item >= a[i]
      a[i+1] = a[i]
      i -= 1
    end 

zallarak

; One may form pairs in Scheme with (cons ITEM1 ITEM2)
; For example, (cons 1 2) represents the pair 1 and 2
; Let's define a the pair of 1 and 2 as one-and-two:

(define one-and-two (cons 1 2)) 

; Now one can invoke the pair with one-and-two
;1 ]=> one-and-two
; Value 11: (1 . 2)

zallarak

; Mapping a singly linked list in Scheme.

; map-1 - the name of our mapping function
; proc - the tranformation
; items - the list

(define (map-1 proc items)
  (if (null? items)
    ()
    (cons (proc (car items))

zallarak

; This creates a simple tree
(define tree-1 (cons (list 1 2) (list 3 4)))

; Quick linked list review
(list 1 2 3 4) ;is equivalent to:
(cons 1 (cons 2 (cons 3 (cons 4 ()))))

; And here is some interpreter action
; just for practice:

zallarak

(define (count-leaves t)
  (cond ((null? t) 0)
        ((not (pair? t)) 1)
        (else (+ (count-leaves (car t)) 
        (count-leaves (cdr t))))))

; The general logic of this function is:
; If the tree is null, return 0
; elif: return 1 if at a leaf. We know
; That we're at a leaf if the position is not null and not a pair

zallarak

def MergeSort(a):
    """ 
    Takes a list, returns a list.
    """
    if (len(a) < 2): 
        return a
    else:
        mid = (len(a)) / 2 
        left = a[:mid]
        right = a[mid:]

zallarak

def Merge(left, right):
    output = []
    x, y = 0, 0
    while x < len(left) and y < len(right):
        if left[x] <= right[y]:
            output.append(left[x])
            x += 1
        else:
            output.append(right[y])
            y += 1

zallarak

; Symbolic differentiation
(define (deriv exp var)
  (cond ((number? exp) 0)
        ((variable? exp)
          (if (same-variable? exp var) 1 0)) 
        ((sum? exp)
          (make-sum (deriv (addend exp) var)
                    (deriv (augend exp) var)))
        ((product? exp)
          (make-sum

zallarak

; sets as unordered lists:

; a set for now is defined as as being able 
; to undergo the following operations

; 1)  element-of-set? checks if x is in set
(define (element-of-set? x set)
  (cond ((null? set) false)
        ((equal? x (car set)) true)
        (else (element-of-set? x (cdr set)))))