K-least element

Iinked Array

• 分為
  1. 排好先後的數列 (indexed)
  2. sorted 的數列 (ordered)
• 每個 Unrolled linked list 的參數
  • flag:
    • 0: 從 0 -> N-1
    • 1: 從 N-1 -> 0
  • length:
    • array 中的資料量 (<subN)

Insert

Insertion with unordered / sufficient space

• Procedures
  • Find subarray
  • Find the i th element
  • Insert value into indexed array
  • Append value into unsorted array

Insertion with Ordered / sufficient space

Insertion with Orderd / insufficient space

Deletion

Deletion with remaining data

Deletion with garbage collection

Reverse

Query

Binary Search Algorithm

function binary_search(A, n, T) is
    L := 0
    R := n − 1
    while L ≤ R do
        m := floor((L + R) / 2)
        if A[m] < T then
            L := m + 1
        else if A[m] > T then
            R := m − 1
        else:
            return m
    return unsuccessful

Query

Copy an array

void *memcpy(void *dest, const void *src, size_t n);

Find i th element

Unrolled linked list

Skip List

Ref: GreekforGeek

Reverse Linked list

• Ref
  • 用 Stack 反轉 linked list
  • Reverse linked list

Binary search algorithm when finding the k-least element

https://www.geeksforgeeks.org/kth-smallest-element-in-a-subarray/

First strictly greater element in sorted array

int next(int arr[], int target, int end)
{
 int start = 0;
  
    int ans = -1;
    while (start <= end)
    {
        int mid = (start + end) / 2;
  
        // Move to right side if target is
        // greater.
        if (arr[mid] <= target)
            start = mid + 1;
  
        // Move left side.
        else
        {
            ans = mid;
            end = mid - 1;
        }
    }
  
    return ans;

• Ref: GreeekforGeek

Insert an element into sorted array

• Ref: [GreekforGeek]

Quick Sort

Ref: Quick sort in C. [link]

Usage

Make File

• make TEST
  • test/test.sh
• make GenData: generate random data
  • test/genData.sh

---

References

1. https://leetcode.com/problems/kth-smallest-element-in-a-bst/solution/