📜 Code Examples

sum(array, len){
    sum = 0
    i = 0
    while(i < len){
        sum += array[i]
        i++
    }
    return sum
}

algori(Arr, len){
    i = 1
    x = Arr[0]
    while(i < len){
        if (Arr[i] > x){
            x = Arr[i]
        }
        i++
    }
    return x
}

find(arr, len, key){
    i = 0
    while(i < len){
        if (arr[i] == key)
            return i
        i++
    }
    return -1
}

search(S, len, key){

    l = 0
    r = len - 1

    while(l <= r){
        m = (l + r) / 2
        if(S[m] == key) return m
        else
            if(S[m] > key) r = m - 1
            else l = m + 1
    }

    return -1
}

// input: S - sequence; l,r - left/right indexes
// output: index i of pivot M; array reorganised
partition(S, l, r)
  // Selects element M and re-organises S such that:
  //   all elements left of M are ≤ M
  //   all elements right of M are ≥ M
  // Returns the final index i of element M

// Find k-th positional statistic using partition
quickSelect(S, l, r, k):
    // 1. call partition on the sequence
    m = partition(S, l, r)

    // 2. if returned index equals k → return S[k]
    if(m == k) return S[k]

    // 3. else recurse on the "left" or "right" sub-sequence
    if(k < m) return quickSelect(S, l, m - 1, k)
    else       return quickSelect(S, m + 1, r, k)

selectionSort(S, len){
    i = 0
    while(i < len){
        mini = indexOfMin(S, i, len)
        swap(S, i, mini)
        i++
    }
}

// where:
// indexOfMin(S, i, len) - return index of minimum among S[j], i ≤ j < len
// swap(S, i, mini)      - swap positions of S[i] and S[mini]

insertionSort(arr, len){

    for(next = 1; next < len; next++){

        curr = next;
        temp = arr[next];

        while((curr > 0) && (temp < arr[curr - 1])){

            arr[curr] = arr[curr - 1];
            curr--;
        }

        arr[curr] = temp;
    }
}

mergeSort(S, len){
    // 1. divide the sequence into 2 halves
    // 2. sort each half separately (recursively)
    // 3. merge the sorted halves

    if(len <= 1) return S

    mid = len / 2
    left  = mergeSort(S[0..mid-1], mid)
    right = mergeSort(S[mid..len-1], len - mid)

    return merge(left, mid, right, len - mid)
}

// input: a1, a2 - sorted sequences (of lengths len1, len2)
// output: return merged (and sorted) sequences a1 and a2

merge(a1, len1, a2, len2){

    i = j = k = 0;
    result[len1 + len2]  // memory allocation

    while((i < len1) && (j < len2))
        if(a1[i] < a2[j]) result[k++] = a1[i++];
        else result[k++] = a2[j++];

    while(i < len1) result[k++] = a1[i++];

    while(j < len2) result[k++] = a2[j++];

    return result;
}

// input: a - array of integers; l,r - leftmost and rightmost indexes
// output: final index of pivot M; array reorganised

partition(a, l, r){

    i = l + 1;
    j = r;
    m = a[l];         // pivot = leftmost element
    temp;

    do{
        while((i < r) && (a[i] <= m)) i++;
        while((j > i) && (a[j] >= m)) j--;
        if(i < j) {temp = a[i]; a[i] = a[j]; a[j] = temp;}
    }while(i < j);

    // when (i==r):
    if(a[i] > m) {a[l] = a[i - 1]; a[i - 1] = m; return i - 1;}
    else {a[l] = a[i]; a[i] = m; return i;}
}

// input: a - array of integers; l,r - leftmost and rightmost indexes
// (the procedure does not return anything)

quicksort(a, l, r){

    if(l >= r) return;
    k = partition(a, l, r);
    quicksort(a, l, k - 1);
    quicksort(a, k + 1, r);
}

// input: a - array of non-negative integers; l - its length

countSort(a, l){

    max = maxValue(a, l);
    l1 = max + 1;
    counts[l1];           // allocate counts array
    result[l];            // allocate result array
    for(i = 0; i < l1; i++) counts[i] = 0;

    for(i = 0; i < l; i++) counts[a[i]]++;
    for(i = 1; i < l1; i++) counts[i] += counts[i - 1];
    for(i = l - 1; i >= 0; i--)
        result[--counts[a[i]]] = a[i];
}

// RadixSort is a scheme, not a single algorithm.
// It applies a stable internal sorting algorithm
// to consecutive positions starting from the LAST position.

radixSort(a, len, d):   // d = number of positions (e.g. digits)
    for(pos = d - 1; pos >= 0; pos--)
        stableSort(a, len, by position pos)
        // e.g. countSort on the digit at position pos

print(SList l){
    node = l.head
    while(node != null){
        print node.element
        node = node.next
    }
}

// Cut out sublist (a,...,b) and insert it after t
splice(a, b, t){
    a_prev = a.prev; b_next = b.next;
    a_prev.next = b_next; b_next.prev = a_prev;
    
    t_next = t.next;
    b.next = t_next; a.prev = t;
    t.next = a; t_next.prev = b;
}

upheap(i)              // i > 0, heap ok under i
    key = heap[i]
    parent = i / 2
    while((parent > 0) && (heap[parent] > key))
        heap[i] = heap[parent]
        i = parent
        parent /= 2
    heap[i] = key

downheap(i)
    l = 2*i              // left son
    r = 2*i + 1          // right son
    if l <= n and heap[l] < heap[i]:
        min = l
    else:
        min = i
    if r <= n and heap[r] < heap[min]:  // n is the size of heap
        min = r
    if min != i:
        swap(i, min)     // swap the elements under indexes (not indexes themselves)
        downheap(min)    // go down

// insert(x): add x to the bottom and restore heap order upward
insert(x):
    add x at the bottom of the heap
    upheap(bottom)                  // O(log n)

// findMin(): root always holds the minimum
findMin():
    return heap[root]               // O(1)

// delMin(): move bottom element to root and restore heap order downward
delMin():
    min = heap[root]
    heap[root] = heap[bottom]
    remove bottom
    downheap(root)                  // O(log n)
    return min

// Naive: n × insert → Θ(n log n)
// Faster way — bottom-up construction:

for(i = n/2; i > 0; i--) downHeap(i)

// Sort using a Priority Queue (pq = priority queue object)

heapSort(s):
    // Phase 1: insert all elements into PQ
    while(s.hasNext())
        pq.insert(s.next())

    // Phase 2: extract min repeatedly
    while(!pq.isEmpty())
        result.add(pq.delMin())

// Recursive version — called with node == root
searchRecursive(node, key):
    if ((node == null) or (node.key == key)) return node
    if (key < node.key) return search(node.left, key)
    else return search(node.right, key)

// Iterative version — called with node == root
searchIterative(node, key):
    while ((node != null) and (node.key != key))
        if (key < node.key) node = node.left
        else node = node.right
    return node

minimum(node):         // called with node == root
    while (node.left != null) node = node.left
    return node

maximum(node):         // called with node == root
    while (node.right != null) node = node.right
    return node

successor(node):
    if (node.right != null) return minimum(node.right)
    p = node.parent
    while ((p != null) and (node == p.right))
        node = p
        p = p.parent
    return p

// predecessor is analogous to successor

insert(node, key):
    if (key < node.key) then
        if node.left == null:
            n = create new node with key
            node.left = n
        else: insert(node.left, key)
    else:  // (key >= node.key)
        if node.right == null:
            n = create new node with key
            node.right = n
        else: insert(node.right, key)

procedure delete(node, key)
    if (key < node.key) then
        delete(node.left, key)
    else if (key > node.key) then
        delete(node.right, key)
    else begin  // key == node.key
        if node is a leaf then
            deletesimple(node)
        else
            if (node.left != null) then
                find x = the rightmost node in node.left
                node.key := x.key;
                delete1(x);
            else
                proceed analogously for node.right
                (we are looking for the leftmost node now)

// Abstract data structure extending the dictionary (type K is linearly ordered)

search(K key)               // find element by key
insert(K key, V value)      // insert key-value pair
delete(K key)               // remove element by key
minimum()                   // return element with smallest key
maximum()                   // return element with largest key
predecessor(K key)          // return element with next smaller key
successor(K key)            // return element with next larger key