Tut 08 - Searching and Sorting

Problem Set 21

Problem 21.1

The Loop version of Binary Search

long search_loop(const long list[], long i, long j, long q) {
    while(i<=j) {
        long mid = (i+j)/2;
        if (list[mid] == q) {
            return mid;
        }
        if (list[mid] > q) {
            j = mid - 1;
            continue;
        }
        i = mid + 1;
    }
    return -1;
}

Problem 21.2*

Question: Instead of returning -1 if the query q is not found, modify the binary search algorithm in Problem 21.1 such that it returns either:

• a position k, such that list[k] <= q <= list[k+1].

• -1 if q < list[0]

• n - 1 if q > list[n-1]

long search_loop(const long list[], long i, long j, long q) {
    while(i<=j) {
        long mid = (i+j)/2;
        if (list[mid] == q) {
            return mid;
        }
        if (list[mid] > q) {
            j = mid - 1;
            continue;
        }
        i = mid + 1;
    }
    return j;
}

The reason to return mid is easy to understand. But return j at last needs some pattern recognition skill. 😂

Problem Set 22

Problem 22.1*

Optimize the Bubble Sort.

Basically, when there is not swap, which means our list is sorted already.

void swap(long a[], size_t i, size_t j) {
    long temp = a[i];
    a[i] = a[j];
    a[j] = temp;
}

bool bubble_pass(size_t last, long a[]) {
    bool has_swapped = false;
    for (size_t i = 0; i < last; i += 1) {
        if (a[i] > a[i+1]) {
            swap(a, i, i+1);
            has_swapped = true;
        }
    }
    return has_swapped;
}

void bubble_sort(size_t n, long a[n]) {
    bool has_swapped = true;
    for (size_t last = n - 1; last > 0 && has_swapped; last -= 1) {
        has_swapped = bubble_pass(last, a);
    }
}

Problem 22.2*

Insertion sort by doing:

• take the first element X from the unsorted partition

• use binary search to find the correct position to insert X

• insert X into the right place

long search_loop(const long list[], long i, long j, long q) {
    
    while(i<=j) {
        long mid = (i+j)/2;
        if (list[mid] == q) {
            return mid;
        }
        if (list[mid] > q) {
            j = mid - 1;
            continue;
        }
        i = mid + 1;
    }
    return j;
}

void insert(long a[], size_t curr)
{
    long to_move = a[curr];
    size_t target = search_loop(a, 0, curr-1, to_move)+1;
    for(size_t i=curr; i > target; i--) {
        a[i] = a[i-1];
    }
    a[target] = to_move;
}

void insertion_sort(size_t n, long a[]) {
    for (size_t curr = 1; curr < n; curr += 1) {
        insert(a, curr);
    }
}

In Line 20, curr-1 means we exclude our current number from the search range first. And the +1 at last is because we want to insert at the position behind what we find using Problem 21.2*