October 2010 - Fusing Data and AI into VR

Quick Sort This is used in research code when built-in qsort does not satisfy the demands.

void qs(int l, int r){
    int p, mid, i, j;

    i = l; j = r; mid = avg[(l + r) >> 1];
    do {
        while (avg[i] < mid) ++i;
        while (avg[j] > mid) --j;
        if (i <= j){
            swap(avg[i], avg[j]);
            swap(order[i], order[j]);
            ++i;
            --j;
        }
    } while (i < j);
    if (l < j) qs(l, j);
    if (i < r) qs(i, r);
}

void qs(int l, int r){

int p, mid, i, j;

i = l; j = r; mid = avg[(l + r) >> 1];

do {

while (avg[i] < mid) ++i;

while (avg[j] > mid) --j;

if (i <= j){

swap(avg[i], avg[j]);

swap(order[i], order[j]);

++i;

--j;

}

} while (i < j);

if (l < j) qs(l, j);

if (i < r) qs(i, r);

}

K-th element Qsort can be used to find the Kth smallest element a[k]:

void Kth(int l,int r,int k)
{
    int i = l,j = r,mid= a [(i + j) >> 1];
    while (i <= j) {
        while (a[i] < mid) ++i;
        while (a[j] > mid) --j;
        if (i<=j) {
            int t = a[i]; a[i] = a[j]; a[j] = t;
            ++i;--j;
        }
    }
    if (k >= i && k<= r) Kth(i, r, k);
    if (k >= l && k<= j) Kth(l, j, k);
}

void Kth(int l,int r,int k)

{

int i = l,j = r,mid= a [(i + j) >> 1];

while (i <= j) {

while (a[i] < mid) ++i;

while (a[j] > mid) --j;

if (i<=j) {

int t = a[i]; a[i] = a[j]; a[j] = t;

++i;--j;

}

if (k >= i && k<= r) Kth(i, r, k);

if (k >= l && k<= j) Kth(l, j, k);

}

In Python,

class Solution(object):
    def kSort(self, a, l, r, k):
        i, j, p = l, r, a[(l + r) >> 1]
        while i < j:
            while a[i] < p:
                i += 1
            while a[j] > p:
                j -= 1
            if i <= j:
                a[i], a[j] = a[j], a[i]
                i += 1
                j -= 1
        if l < j and k <= j:
            self.kSort(a, l, j, k)
        if i < r and k >= i:
            self.kSort(a, i, r, k)
    
    def findKthLargest(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        self.kSort(nums, 0, len(nums) - 1, len(nums) - k)
        return nums[len(nums) - k]

class Solution(object):

def kSort(self, a, l, r, k):

i, j, p = l, r, a[(l + r) >> 1]

while i < j:

while a[i] < p:

i += 1

while a[j] > p:

j -= 1

if i <= j:

a[i], a[j] = a[j], a[i]

i += 1

j -= 1

if l < j and k <= j:

self.kSort(a, l, j, k)

if i < r and k >= i:

self.kSort(a, i, r, k)

def findKthLargest(self, nums, k):

"""

:type nums: List[int]

:type k: int

:rtype: int

"""

self.kSort(nums, 0, len(nums) - 1, len(nums) - k)

return nums[len(nums) - k]

Use partition to sort 0, 0, 0, 1, 1, 2, 2, 2…

void Solutions::sortColors(vector<int>& nums) {
    partition(
        partition(nums.begin(), nums.end(), bind1st(equal_to<int>(), 0)),
        nums.end(), bind1st(equal_to<int>(), 1)
        );
}