Tìm kiếm và sắp xếp

Bài giảng cho lớp cấu trúc dữ liệu. Bạn nào rảnh đọc thì góp ý giùm, nhất là phần C++.

Bài trước: thuật toán tồi tệ nhất trong lịch sử nhân loại
Bài sau: lớp Vector và phân tích khấu hao.


1. Binary search

Searching for a key (int, say) in a vector of integers is a simple linear-time procedure:

/**
 * -----------------------------------------------------------------------------
 * scan a vector, search for the key
 * -----------------------------------------------------------------------------
 */
bool linear_search(vector<int> vec, int key) {
    for (size_t i=0; i<vec.size(); i++) {
        if (key == vec[i]) return true;
    }
    return false;
}

However, if the input vector is already sorted, we can do better using binary search:

/**
 * -----------------------------------------------------------------------------
 * check the middle element, search the left or right accordingly
 * -----------------------------------------------------------------------------
 */
bool binary_search(vector<int> sorted_vec, int key, size_t left, size_t right) {
    while (left <= right) {
        // the following will cause problems if you do
        // mid = (left+right)/2, due to potential integer overflow
        size_t mid = left + (right - left)/2;
        if (key > sorted_vec[mid])
            left = mid+1;
        else if (key < sorted_vec[mid])
            right = mid-1;
        else return true;
    }
    return false;
}

Let T(n) denote the run time for binary search, it is not hard to write down a recurrence for it:

T(n) = \begin{cases} O(1) & n=1\\ T(\lceil n/2 \rceil)+O(1) & n>1\end{cases}

Then, using a method similar to the analysis of fib4() algorithm, we can guess the solution of T(n) = O(\log n).

Binary search is exponentially faster than linear search, given that the input array or vector is already sorted. Hence, if we are going to do a lot of searches over the same input, it would be wise to sort the input once and for all. (Later on in the semester, we will discuss other data structures which can help speed up multiple searches over the same data.) To be specific, suppose we perform m searches over an array of size n, then the total amount of time it takes is O(mn) if each search is linear. Now, if we pre-sort the input in time T(n) for some function T, then the total time it takes is O(T(n) + m\log n), which is potentially much faster than \Theta(mn) for m large. We discuss several well-known sorting algorithms next. This website has nice annimations of the sorting algorithms we discuss here.

2. Insertion sort

Insertion sort is based on the following idea. Say the input is A[0..n-1]. For each i from 1 to n-1, we find the right place in A[0...i-1] (which is already sorted) to insert A[i].

/**
 * -----------------------------------------------------------------------------
 * The Insertion Sort algorithm
 * for each i from 1 to n-1, insert vec[i] to the right place in the prefix
 * -----------------------------------------------------------------------------
 */
void insertion_sort(vector<int> &vec) {
    int temp, j;
    for (int i=1; i<vec.size(); i++) {
        temp = vec[i];
        j = i-1;
        while (j >= 0 && vec[j] > temp) {
            vec[j+1] = vec[j];
            j--;
        }
        vec[j+1] = temp;
    }
}

In the worst-case, A[i] shifts i elements in the prefix to the right, and inserts itself in position 0. Hence, the total running time is big-O of \sum_{i=1}^{n-1} i = n(n-1)/2 = O(n^2). Overall, the worst-case run time for insertion sort is O(n^2). If the input is already sorted (in ascending order), then no data movement is made and there are only at most n comparisons. That is the best-case scenario. The worst-case input is the inversedly sorted input, which requires both \Omega(n^2) moves (data movements) and \Omega(n^2) comparisons.

Two nice properties of insertion sort are: (1) the algorithm only uses O(1) extra space (this is called an in-place algorithm), and (2) it is a stable sorting algorithm in the sense that input data points which have equal values maintain their relative order in the output. Stability is important in applications such as databases.

3. Selection sort

The selection sort algorithm does the following: for each i from 0 to n-2, find the smallest element in the suffix A[i..n-1] and swap that element with A[i].

/**
 * -----------------------------------------------------------------------------
 * The Seclection Sort algorithm
 * for each i from 0 to n-2, move the i'th smallest element to its position
 * -----------------------------------------------------------------------------
 */
void selection_sort(vector<int> &vec) {
    int i, j, k;
    for (i=0; i<vec.size()-1; i++) {
        j=i;
        for (k=i+1; k<vec.size(); k++)
            if (vec[k] < vec[j]) j=k;
        if (j!=i) swap(vec[i], vec[j]);
    }
}

Finding the smallest element in A[i..n-1] takes n-i-1 steps, which only involves comparisons. Then, one single swap puts the correct element into A[i]. Hence, the total number of comparisons is \sum_{i=0}^{n-2} (n-i-1) = n(n-1)/2 = O(n^2), which is also the order of the run time. The number of data movements is only O(n). Thus, if we were sorting large objects (instead of integers), we might prefer selection sort over insertion sort, even though both algorithms have worst-case run time O(n^2). The sorting is in-place. Selection sort always runs in time O(n^2), even when the input is already sorted.

At this point, it should be noted that we do not always have to move the objects, depending on what we want out of sorting. For example, we can sort an array of pointers (or indices) to the objects without moving them explicitly. In that case, we only swap the pointers which is an inexpensive operation. On the other hand, if we seriously want to sort memory blocks according to some criterion, then the moves do matter. If implemented properly, the algorithm can be made stable; but then the number of moves can become O(n^2), negating the major advantage of selection sort.

4. Merge sort

Both selection sort and insertion sort have \Omega(n^2)-worst-case running time, which might be too high for many applications. (We will see some data later.) Merge sort is a classic divide and conquer algorithm which has a O(n\log n) run time, which is asymptotically optimal among the comparison sort algorithms! Roughly speaking, each comparison reveals one bit of information, and there are n! cases to distinguish; thus, there must be at least one case for which \log_2(n!) \approx n\log n comparisons are necessary. (The approximation \log_2(n!) \approx n\log n can be derived from Stirling approximation.)

The idea of merge sort is extremely simple: we split the input array into two halves, recursively sort the left and the right halves, and then merge the two halves. The key step is the merge step when we scan the two (sorted) halves left to right simultaneously and put the smaller element into the merged output. This idea is perhaps best explained in codes:

/**
 * -----------------------------------------------------------------------------
 *  merges two halves
 * -----------------------------------------------------------------------------
 */
void merge(vector<int> &target,
           const vector<int> &left,
           const vector<int> &right)
{
    if (target.size() != left.size() + right.size()) return; // sanity check

    size_t i=0, j=0, k=0;
    while (i < left.size() && j < right.size()) {
        if (left[i] <= right[j]) // stable, if '<' is used then unstable
            target[k++] = left[i++];
        else
            target[k++] = right[j++];
    }

    while (i < left.size()) target[k++] = left[i++];
    while (j < right.size()) target[k++] = right[j++];
}

/**
 * -----------------------------------------------------------------------------
 * The Merge Sort algorithm
 * - create a copy of the left half, and a copy of the right half
 * - recursively sort the left half and the right half
 * - then merge the two halves
 * -----------------------------------------------------------------------------
 */
void merge_sort(vector<int> &vec) {
    size_t n = vec.size();
    if (n <= 1) return;
    vector<int> left(vec.begin(), vec.begin()+n/2);
    vector<int> right(vec.begin()+n/2, vec.end());
    merge_sort(left);
    merge_sort(right);
    merge(vec, left, right);
}

For a target array of size n, the merge step takes O(n)-time. Hence, if we let T(n) be the time it takes merge sort to sort a vector of length n, then we have the following recurrence relation:

T(n) = T(\lfloor n/2 \rfloor) + T(\lceil n/2 \rceil) + cn

for some constant c which represents the fact that the merge step takes time cn. Now, as we have shown in the Fibonacci and the binary search ananalysis, it is often safe to ignore the issue of integrality; we can rewrite the recurrence as

T(n) = 2T(n/2) + cn

Every recurrence relation needs a base case. In our case, T(1) = O(1). To solve this recurrence, we can draw a tree of depth k, where k is such that n/2^k \approx 1 because that is the depth when the base case applies. Each level of the tree contributes cn to the total run time. There are k \approx \log_2 n levels. Thus, the worst-case run time for merge sort is cn \log n = O(n\log n).

The worst-case run time is great! However, merge sort suffers from the space-complexity problem. Consider, for example, an input of size n=16. First, two subarrays of size 8 each are created. Then, to sort the left subarray two subarrays of size 4 each are created and so on. Once the left side is sorted (after the call to merge_sort(left)), the extra space used for the left-side sort is released, the function returns, and the same process is repeated for the right side. Hence, if we let S(n) be the total extra space used for merge-sorting an input of size n, we have the following recurrence:

S(n) = S(n/2) + cn
.

for some constant c, which roughly measures how many bytes each input item requires. We can use the recurrence tree method again: the tree has \log n levels from k=1..\log n where level k contributes cn/2^{k-1} to the total space complexity. Hence,

S(n) = \sum_{k=1}^{\log n} cn/2^{k-1} \leq cn\left(\sum_{i=0}^\infty 1/2^i\right) = 2cn = O(n)

In particular, merge sort as implemented above is not an in-place sorting algorithm. It is possible to make merge-sort in place, at the cost of considerable code complexity.

Merge sort as shown above is stable, has \Theta(n\log n) comparisons and \Theta(n\log n) item moves. Thus, merge sort is very predictable, has nice worst-case run time. But, even when the input is already sorted it still takes \Omega(n\log n) time because of all the copying.

5. Solving recurrences

So, we have seen several recurrences of the forms

T(n) = T(n/2) + O(1) (from binary search, fib4())

T(n) = 2T(n/2) + O(1) (run time of merge sort)

S(n) = S(n/2) + O(n) (extra space complexity of merge sort)

In each of these cases, we can draw a tree and roughly estimate the contribution of each level to the overall function. The recurrence tree is a paticularly quick way of guessing a solution to the recurrence relation. In this course, we will not emphasize the proof part where after guessing we have to inductively prove that our guess works. You will do more formal proofs in CSE 331 and CSE 431. The recurrence tree method can be used to “solve” similar recurrences. Try the following:

T(n) = 3T(n/4) + O(1) T(n) = 9T(n/10) + T(n/10) + O(n) T(n) = 2T(n/2) + O(n^2) T(n) = T(n/2) + O(n^3)

6. Quicksort

The next sorting algorithm we discuss is Quick sort by Tony Hoare from 1960. The algorithm is in a sense an opposite of merge sort: merge sort has trivial partitioning and non-trivial merging, while quick sort has non-trivial partitioning and trivial merging. The main idea of quick sort has tree steps. Let A[p..q] be a sub-array that we want to sort.

  • The partition step: first, we rearrange items in A[p..q] such that there is an index p ≤ r ≤ q where A[i] < A[r] for all i = p..r-1 and A[r] ≤ A[i] for all i=r+1..q.
  • Recursively sort A[p..r-1]
  • Recursively sort A[r+1..q]

Because the left part and the right part are already in the correct order, no merging is necessary.

/**
 * -----------------------------------------------------------------------------
 * The Quick Sort algorithm
 * - we rearrange the members vec[p...q] so that there will be some r between
 *   p and q such that all vec[i] < vec[r] for p <= i < r and
 *                         vec[r] <= vec[j] for r < j <= q
 * - then sort vec[p..r-1] and vec[r+1..q]
 * -----------------------------------------------------------------------------
 */
void qs_with_range(vector<int> &vec, int p, int q) {
    if (p >= q) return;

    // partition
    int r=p-1;
    for (int j=p; j<q; j++)
        if (vec[j] < vec[q])
            swap(vec[++r], vec[j]);
    swap(vec[++r], vec[q]);

    // sort the left & the right parts
    qs_with_range(vec, p, r-1);
    qs_with_range(vec, r+1, q);
}

/**
 * -----------------------------------------------------------------------------
 * Wrapper to the quick sort algorithm
 * -----------------------------------------------------------------------------
 */
void quick_sort(vector<int> &vec) {
    qs_with_range(vec, 0, vec.size()-1);
}

In the qs_with_range sub-routine, we use vec[q] as the pivot element and try to partition vec[p..q] around that element. The choice of the pivot element is crucial.

First, let’s consider the case when the pivot element roughly partition vec[p..q] into roughly equal-size halves. Then, because the partition step takes time O(n), it is not hard to see that the run time recurrence for quick sort is the same as that of merge sort: T(n) = 2T(n/2) + O(n) which leads to an overall T(n) = O(n\log n) run time.

Second, if the input is either in sorted order or in the reversed sorted order, then we obtain the recurrence T(n) = T(n-1) + O(n) which (by the recurrence tree method) gives T(n) = O(n^2). We can see this behavior when we experiment with the sorting algorithms below.

Third, suppose we are not too unlucky and we get a 9n/10 vs n/10 partition each time, then the recurrence is T(n) = T(9n/10) + T(n/10) + O(n), which solves to be T(n) = O(n\log n) again!

The observation leads to the following natural idea: instead of always partitioning around vec[q] as the pivot, we can pick a random element in vec[p..q] to be a pivot. Then, with very high probability we have a good partition and the overall run time is T(n) = O(n\log n) in expectation.

/**
 * -----------------------------------------------------------------------------
 * The Randomized Quick Sort algorithm
 * - pick a random pivot, that's all
 * -----------------------------------------------------------------------------
 */
void rqs_with_range(vector<int> &vec, int p, int q) {
    if (p >= q) return;

    // pick a random pivot
    int m = rand() % (q-p+1);
    swap(vec[q], vec[p+m]);

    // partition
    int r=p-1;
    for (int j=p; j<q; j++)
        if (vec[j] < vec[q])
            swap(vec[++r], vec[j]);
    swap(vec[++r], vec[q]);

    // sort the left & the right parts
    rqs_with_range(vec, p, r-1);
    rqs_with_range(vec, r+1, q);
}

/**
 * -----------------------------------------------------------------------------
 * Wrapper to the randomized quick sort algorithm
 * -----------------------------------------------------------------------------
 */
void randomized_quick_sort(vector<int> &vec) {
    srand(static_cast<unsigned int>(time(0)));
    rqs_with_range(vec, 0, vec.size()-1);
}

It can be proved that the expected run-time of randomized quick sort is O(n\log n), and the run-time is in this order with high probability. In practice, quick sort is usually very fast, even faster than merge sort. This is an example of a Las Vegas algorithm, which is a randomized algorithm which always gives a correct output but the (worst-case) running time varies. By contrast, a Monte Carlo algorithm is a randomized algorithm which has a bounded worst-case run time but the output quality varies.

Even though partitioning is done in place, the recurive calls will require O(\log n) extra space (the calls are O(\log n)-level deep). See this paper.

Quick sort can be made O(n\log n)-worst-case run time if we use a linear time algorithm to select the median of vec[p..q] to partition around. The linear time median finding algorithm is classic, and you will learn about it in CSE 331 or CSE 431.

7. The (Binary) Heap data structure and the heapsort algorithm

A (binary) max heap is a data structure which can be visualized as a complete binary tree, which is a binary tree in which every level is completely filled except for possibly the last level which is filled from left to right as much as possible. Each node in the (max) heap holds a key; for our purposes in this lecture keys are integers. A parent node has key greater than or equal to the key of each of its children. Hence, the key of the root node is always the maximum key among all nodes. The following is an example max heap.

In a min heap, the parent’s key is at most the children’s keys. And thus the root node has the smallest key. A min heap can be used to implement a priority queue which is an extremely useful data structure. In fact, the Dijkstra’s shortest path algorithm often needs a priority queue; and half the networks on the Internet run a version of Dijkstra’s algorithm every few minutes or so to implement their link-state routing protocols. For now, let us get back to the max heap. By heap we mean max heap for the rest of this lecture.

We can implement a heap using an array of keys. If the heap has n nodes then the array (or vector) has n elements where the indices of the nodes in the array are numbered from the root down, left to right, starting from 0 as shown in the following picture.


From the picture, it is not hard to see how to compute the index of the parent, the left, or the right child of a given node indexed i.

Two sub-routines are important in building and using a heap:

  • heapify(array) turns an arbitrary array into a heap
  • sink(i, n, array) operates on the node indexed i of the heap array[0..n-1]. The procedure assumes that both sub-trees below node i are already heaps, and “sinks” i down (while floating some nodes up) until the sub-tree rooted at i is also a heap. This way, we can perform heapify by sink()‘ing from the bottom up.

Once the two sub-routines are in order, the heap sort algorithm simply builds a heap out of the input array, swap the max element to the end of the array and recursively call sink(0, n-1, array) to heapify the prefix. All three functions in C++ are self-explanatory.

/**
 * -----------------------------------------------------------------------------
 * sink node i of the heap vec[0..n-1]
 * - uses a recursive strategy for easy explanation
 * - if the greater of the left or the right child is greater than the node
 *   then swap and sink that subtree
 * -----------------------------------------------------------------------------
 */
void recursive_sink(vector<int> &vec, size_t i, size_t n) {
    size_t left = 2*i + 1;
    if (n > vec.size() || left >= n) return;
    size_t right = left + 1; // possibly >= n    
    size_t my_pick =
        (right >= n) ?  left : (vec[right] > vec[left]) ? right : left;

    if (vec[i] < vec[my_pick]) {
        swap(vec[i], vec[my_pick]);
        recursive_sink(vec, my_pick, n);
    }
}

/**
 * -----------------------------------------------------------------------------
 * turn the input vector into a heap
 * -----------------------------------------------------------------------------
 */
void heapify(vector<int> &vec) {
    for (int i=vec.size()/2; i>=0; i--)
        recursive_sink(vec, i, vec.size());
}


/**
 * -----------------------------------------------------------------------------
 * The Heap Sort algorithm
 * - heapify the array of size n
 * - swap the first and the last
 * - sink the first and recurse
 * -----------------------------------------------------------------------------
 */
void heap_sort(vector<int> &vec) {
    heapify(vec);
    for (int j=vec.size()-1; j>=1; j--) {
        swap(vec[0], vec[j]);
        recursive_sink(vec, 0, j);
    }
}

The recursive_sink() function has O(\log n) levels of recursive calls, imposing an extra O(\log n)-space complexity. Staring at the function for a while, it seems possible to turn it into an iterative procedure. (Formally, recursive_sink() is a form of tail recursion which can always be turned into an iterative procedure.)

/**
 * -----------------------------------------------------------------------------
 * "un-spinning" the previous recursive sinking procedure, so now the function
 * is non-recursive and only uses O(1)-extra space, making heap_sort a proper
 * in place sorting algorithm
 * -----------------------------------------------------------------------------
 */
void sink(vector<int> &vec, size_t i, size_t n) {
    if (n > vec.size()) return;
    size_t left, right, my_pick;

    while ((left = 2*i+1) < n) {
        right = left + 1; // note: right might be >= n    
        my_pick = right >= n ?  left : vec[right] > vec[left] ? right : left;
        if (vec[i] >= vec[my_pick]) break; // i's subtree is already a heap
        swap(vec[i], vec[my_pick]);
        i = my_pick;
    }
}

Then, we simply let heapify() and heap_sort() call sink() instead of recursive_sink(). Since the height of a complete binary tree with n nodes is \Theta(\log n), the sink(vec, i, n) procedure takes O(\log n) time. The heapify() procedure, at first glance, seems to work in time O(n\log n) because there are about n/2 nodes to be sink()‘ed and each sink() takes O(\log n)-time. However, the heights of the nodes to be sinked start from 1 and increase gradually to \log n. There are at most n/2^h nodes at height h. Hence, the total run time for heapify() is big-O of

\sum_{h=1}^{\log_2 n} (n/2^h)\cdot h \leq n \sum_{h=1}^\infty h/2^h \leq n \sum_{h=1}^\infty 1/2^{h-1} = 2n

Consequently, heapify() is a linear time algorithm. And, heap_sort runs in O(n\log n) time in the worst case. This is a rather beautiful result when a really simple data structure conceptually gives rise to an in place sorting algorithm. Unfortunately it is not stable.

8. Experimenting and evaluating the sorting algorithms

I wrote some codes to experiment with all five of the above algorithms. You should be able to fill in the search_sort.cpp and search_sort.h files by simple cut and pasting.

/*
 ******************************************************************************
 * file name  : main.cpp
 * author     : Hung Q. Ngo
 * description: test run all of the following sorting algorithms
 *  - insertion sort
 *  - selection sort
 *  - merge sort
 *  - quick sort
 *  - randomized quick sort
 *  - heap sort
 *  on random, sorted, and inversedly sorted inputs of varying sizes
 *  print the run times out in a csv file to be opened with Excel
 *  I did the graphing from Excel
 ******************************************************************************
 */
#include <iostream>
#include <vector>
#include <cstdlib>  // for rand() and srand()
#include <ctime>    // for time()

#include "search_sort.h"

using namespace std;

void print_vec(vector<int>& vec);

/**
 * -----------------------------------------------------------------------------
 * print a vector of integers, finish with a new line
 * -----------------------------------------------------------------------------
 */
void print_vec(vector<int>& vec) {
    for (int i=0; i<vec.size(); i++) {
        cout << vec[i] << " ";
    }
    cout << endl;
}

/**
 * -----------------------------------------------------------------------------
 * returns a random vector of n elements, each from 0 to n-1
 * not efficient due to vector copying, but should not affect runtime much
 * -----------------------------------------------------------------------------
 */
vector<int> random_vector(size_t n) {
    srand(static_cast<unsigned int>(time(0)));
    vector<int> ret(n);
    for (int i=0; i<n; i++) 
        ret[i] = rand() % n;
    return ret;
}

/**
 * -----------------------------------------------------------------------------
 * returns a descending vector of n elements, from n down to 1
 * -----------------------------------------------------------------------------
 */
vector<int> descending_vector(size_t n) {
    vector<int> ret(n);
    for (int i=0; i<n; i++) ret[i] = n-i-1;
    return ret;
}

/**
 * -----------------------------------------------------------------------------
 * returns a ascending vector of n elements
 * -----------------------------------------------------------------------------
 */
vector<int> ascending_vector(size_t n) {
    vector<int> ret(n);
    for (int i=0; i<n; i++) ret[i] = i;
    return ret;
}

/**
 * -----------------------------------------------------------------------------
 * returns an almost sorted array, only some 10 of the pairs are swapped
 * -----------------------------------------------------------------------------
 */
vector<int> almost_ascending_vector(size_t n) {
    vector<int> ret(n);
    int i, j,k;
    srand(static_cast<unsigned int>(time(0)));
    for (i=0; i<n; i++) ret[i] = i;
    for (i=0; i<10; i++) {
        j = rand() % n; k = rand() % n;
        swap(ret[j], ret[k]);
    }
    return ret;
}


/**
 *
 * -----------------------------------------------------------------------------
 * run a sorting algorithm pointed to by sort_algo
 * the test data is obtained by get_data
 * the different sizes of the test data is stored in input_sizes
 * -----------------------------------------------------------------------------
 */
void test_run(vector<int> input_sizes, void (*sort_algo)(vector<int>&),
              vector<int> (*get_data)(size_t)) 
{
    time_t start,end;
    double dif;
    vector<int> data;
    for(int i=0; i<input_sizes.size(); i++) {
        time(&start);
        data = get_data(input_sizes[i]);
        sort_algo(data);
        time (&end);
        dif = difftime(end,start);
        cout << dif;
        if (i < input_sizes.size()-1) cout << ",";
        else cout << endl;
    }
}

/**
 * -----------------------------------------------------------------------------
 *  I'm a bit lazy here, could use a map to clean the code up
 * -----------------------------------------------------------------------------
 */
void gather_data(vector<int> input_sizes, vector<int> (*fp)(size_t)) {
    cout << "Insertion,"; 
    test_run(input_sizes, insertion_sort, fp);
    cout << "Selection,"; 
    test_run(input_sizes, selection_sort, fp);
    cout << "Merge,"; 
    test_run(input_sizes, merge_sort, fp);
    cout << "Heap,"; 
    test_run(input_sizes, heap_sort, fp);
    cout << "Quicksort,"; 
    test_run(input_sizes, quick_sort, fp);
    cout << "Randomized Quicksort,"; 
    test_run(input_sizes, randomized_quick_sort, fp);
}

/**
 * -----------------------------------------------------------------------------
 * Test those guys and gather some data
 * We have 4 sorting algorithms: Insertion, Selection, Merge, Quick, and RQuick
 * We'll test them with different sizes and different types of input:
 *  n = 1000, 2000, 10000, 20000, 50000, 100000
 *  input already sorted
 *  input inversedly sorted
 *  input randomized
 *  input almost sorted
 * n=200000 gives me segmentation fault
 * -----------------------------------------------------------------------------
 */
int main() {
    // to test a specific sorting algorithm you can do
    /*
    vector<int> vec = almost_ascending_vector(20);
    cout << "Before: "; print_vec(vec);
    heap_sort(vec);
    cout << "After: ";  print_vec(vec);
    */

    static int arr[] = {1000,2000,10000,20000,50000,100000};
    vector<int> input_sizes(arr, arr + sizeof(arr)/sizeof(int));

    cout << "Randomized input: " << endl;
    for (int i=0; i<input_sizes.size(); i++) cout << "," << input_sizes[i];
    cout << endl;
    gather_data(input_sizes, random_vector);

    cout << endl;
    cout << "Almost sorted input: " << endl;
    for (int i=0; i<input_sizes.size(); i++) cout << "," << input_sizes[i];
    cout << endl;
    gather_data(input_sizes, almost_ascending_vector);

    cout << endl;
    cout << "Sorted input: " << endl;
    for (int i=0; i<input_sizes.size(); i++) cout << "," << input_sizes[i];
    cout << endl;
    gather_data(input_sizes, ascending_vector);

    cout << endl;
    cout << "Inversedly sorted input: " << endl;
    for (int i=0; i<input_sizes.size(); i++) cout << "," << input_sizes[i];
    cout << endl;
    gather_data(input_sizes, descending_vector);
}

The following graphs give the run times for different algorithms under different inputs. I tried input sizes of 200K but some algorithm didn’t finish due to memory errors. I didn’t bother to check which one did not finish. But that’s from my laptop. I will probably try again on timberlake or my imac which is much more powerful.

For randomized inputs, selection sort is way worse than insertion, which starts to get worse than the O(n\log n) algorithms at around 10K input size. Quick sort, Merge sort, and Randomized Quick sort all work very well. Heap sort is a little bit slower at n = 100K, but it is still under 1 second. Since the input is randomized, we theoretically expected that there is no difference between quick sort and randomized quick sort, and that shows. (I should have run more experiments and average out to be experimentally sound; but I’m lazy. You can do that youself.)

For inversely sorted input, quick sort starts to show its true color of a O(n^2) algorithm. It is still a lot faster than selection sort though. In this case, insertion sort and quick sort are comparable at n = 100K: they take more than 130 seconds.

The same problem with quick sort shows up when the input is already sorted. In this case, insertion sort is superb. It is a linear time algorithm for this input, after all.

For almost sorted inputs, again insertion sort does very well! (You should be able to see why that is the case.)

9. Sorting generic objects

9.1. C++ Template functions

So far we are only able to sort integers. To sort doubles or strings, what we can do is to overload those functions by cut-and-pasting the codes and change the types from int to double and to string. This strategy does not scale, obviously. C++ function templates is a construct which allows for generic programming in which the data types are essentially the parameters to the functions. Briefly, instead of sorting int or double, we can write a sorting function which sorts an Item_Type (which is just a place-holder name) which will be replaced by a specific type later when we invoke the function. We have seen templates before, in the forms vector<int> or vector<string>. What that says is that vector is a template class, which can be a vector of strings or a vector of integers. When we explicitly write vector<string> the compiler replaces the Item_Type place holder in the vector template class definition with the specific type string.

For a template function, it is very simple syntactically

/*
 ******************************************************************************
 * file name  : templ_sort.h
 * author     : Hung Q. Ngo
 * description: implementation a template version of randomized quick sort
 *              and insertion sort
 ******************************************************************************
 */

#include <vector>
#include <cstdlib>  // for rand() and srand()
#include <ctime>    // for time()

/**
 * -----------------------------------------------------------------------------
 * Template Insertion Sort
 * for each i from 1 to n-1, insert vec[i] to the right place in the prefix
 * -----------------------------------------------------------------------------
 */
template <typename Item_Type>
void insertion_sort(std::vector<Item_Type> &vec) {
    Item_Type temp, j;
    for (int i=1; i<vec.size(); i++) {
        temp = vec[i];
        j = i-1;
        // assumes compiler knows how to do '>' with Item_Type
        while (j >= 0 && vec[j] > temp) {
            vec[j+1] = vec[j];
            j--;
        }
        vec[j+1] = temp;
    }
}

/**
 * -----------------------------------------------------------------------------
 * The Randomized Quick Sort algorithm
 * - pick a random pivot, that's all
 * -----------------------------------------------------------------------------
 */
template <typename Item_Type>
void rqs_with_range(std::vector<Item_Type> &vec, int p, int q) {
    if (p >= q) return;

    // pick a random pivot
    int m = std::rand() % (q-p+1);
    std::swap(vec[q], vec[p+m]); 

    // partition
    int r=p-1;
    for (int j=p; j<q; j++)
        if (vec[j] < vec[q])
            std::swap(vec[++r], vec[j]);
    std::swap(vec[++r], vec[q]);

    // sort the left & the right parts
    rqs_with_range(vec, p, r-1);
    rqs_with_range(vec, r+1, q);
}

/**
 * -----------------------------------------------------------------------------
 * Wrapper to the randomized quick sort algorithm
 * -----------------------------------------------------------------------------
 */
template <typename Item_Type>
void randomized_quick_sort(std::vector<Item_Type> &vec) {
    std::srand(static_cast<unsigned int>(std::time(0)));
    rqs_with_range(vec, 0, vec.size()-1);    
}

The keyword typename can also be replaced by class. See here for more details.

Note that I’ve put the functions’ implementations in the header file because separate compilation is not possible with template functions: the compiler needs to know the specific type we want before it can generate machine codes. Hence, the easiest solution is to put all the definitions in the header file. There are other options too, but for us putting the function template definitions in the header is sufficient.

To use the function templates, you can use the syntax insertion_sort<double>(vec) as you did vector<double>, but that is not necessary because if we defined vector<double> vec then the compiler already knows the type of the vector passed in. Hence, it is sufficient to do the following:

/*
 ******************************************************************************
 * file name  : driver.cpp
 * author     : Hung Q. Ngo
 * description: test a few template sorting algorithms
 ******************************************************************************
 */
#include <iostream>
#include <vector>

#include "templ_sort.h"

using namespace std;

/**
 * -----------------------------------------------------------------------------
 * print a vector of Item_Type, finish with a new line
 * assumes compiler knows how to cout << Item_Type 
 * -----------------------------------------------------------------------------
 */
template <typename Item_Type>
void print_vec(vector<Item_Type>& vec) {
    for (int i=0; i<vec.size(); i++) {
        cout << vec[i] << " ";
    }
    cout << endl;
}

/**
 * -----------------------------------------------------------------------------
 *  test template insertion sort
 *  test template quick sort
 * -----------------------------------------------------------------------------
 */
int main() {
    vector<double> vec;
    vec.push_back(1.5); vec.push_back(-2.5); vec.push_back(5.3);
    vec.push_back(-2); vec.push_back(4);
    cout << "Before: "; print_vec(vec);
    randomized_quick_sort(vec);
    cout << "After: ";  print_vec(vec);
}

The above strategy doesn’t work if we want to sort objects which do not have built-in comparison operators. We can, however, use a callback function to make our sorting routines almost completely general.

/*
 ******************************************************************************
 * file name  : cb_sort.h
 * author     : Hung Q. Ngo
 * description: implementations of template versions of randomized quick sort
 *              and insertion sort with a callback function
 ******************************************************************************
 */

#include <vector>
#include <cstdlib>  // for rand() and srand()
#include <ctime>    // for time()

/**
 * -----------------------------------------------------------------------------
 * -1 if a < b, 0 if a==b, 1 if a>b
 * -----------------------------------------------------------------------------
 */
template <typename Item_Type>
int default_cmp(Item_Type a, Item_Type b) {
    return a < b? -1 : a == b ? 0 : 1;
}

/**
 * -----------------------------------------------------------------------------
 * Template Insertion Sort
 * for each i from 1 to n-1, insert vec[i] to the right place in the prefix
 * -----------------------------------------------------------------------------
 */
template <typename Item_Type>
void insertion_sort(std::vector<Item_Type> &vec, 
                    int (*cmp)(Item_Type, Item_Type) = default_cmp)
{
    Item_Type temp; 
    int j;
    for (int i=1; i<vec.size(); i++) {
        temp = vec[i];
        j = i-1;
        // assumes compiler knows how to do '>' with Item_Type
        while (j >= 0 && cmp(vec[j],temp) > 0) {
            vec[j+1] = vec[j];
            j--;
        }
        vec[j+1] = temp;
    }
}

/**
 * -----------------------------------------------------------------------------
 * The Randomized Quick Sort algorithm
 * - pick a random pivot, that's all
 * -----------------------------------------------------------------------------
 */
template <typename Item_Type>
void rqs_with_range(std::vector<Item_Type> &vec, int p, int q,
                    int (*cmp)(Item_Type, Item_Type))
{
    if (p >= q) return;

    // pick a random pivot
    int m = std::rand() % (q-p+1);
    std::swap(vec[q], vec[p+m]); 

    // partition
    int r=p-1;
    for (int j=p; j<q; j++)
        if (cmp(vec[j],vec[q])<0)
            std::swap(vec[++r], vec[j]);
    std::swap(vec[++r], vec[q]);

    // sort the left & the right parts
    rqs_with_range(vec, p, r-1, cmp);
    rqs_with_range(vec, r+1, q, cmp);
}

/**
 * -----------------------------------------------------------------------------
 * Wrapper to the randomized quick sort algorithm
 * -----------------------------------------------------------------------------
 */
template <typename Item_Type>
void randomized_quick_sort(std::vector<Item_Type> &vec,
                    int (*cmp)(Item_Type, Item_Type) = default_cmp) 
{
    std::srand(static_cast<unsigned int>(std::time(0)));
    rqs_with_range(vec, 0, vec.size()-1, cmp);
}

And here’s how to use the above routines

/*
 ******************************************************************************
 * file name  : driver.cpp
 * author     : Hung Q. Ngo
 * description: test a few template sorting algorithms
 ******************************************************************************
 */
#include <iostream>
#include <vector>
#include <cstdlib>  // for rand() and srand()
#include <ctime>    // for time()

// #include "templ_sort.h"
#include "cb_sort.h"

using namespace std;

/**
 * -----------------------------------------------------------------------------
 * print a vector of Item_Type, finish with a new line
 * assumes compiler knows how to cout << Item_Type 
 * -----------------------------------------------------------------------------
 */
template <typename Item_Type>
void print_vec(vector<Item_Type>& vec) {
    for (int i=0; i<vec.size(); i++) {
        cout << vec[i] << " ";
    }
    cout << endl;
}

int reverse_cmp(double a, double b) {
    return a>b ? -1 : (a<b) ? 1 : 0;
}

int str_cmp(string a, string b) {
    return a.compare(b);
}

/**
 * -----------------------------------------------------------------------------
 *  test template insertion sort
 *  test template quick sort
 * -----------------------------------------------------------------------------
 */
int main() {
    // sorting doubles, using default comparison operators
    vector<double> vec;
    vec.push_back(1.5); vec.push_back(-2.5); vec.push_back(5.3);
    vec.push_back(-2); vec.push_back(4);

    cout << "Sorting doubles in increasing order" << endl;
    cout << "Before: "; print_vec(vec);
    randomized_quick_sort(vec);
    cout << "After: ";  print_vec(vec);

    // sorting doubles in reversed order
    cout << "Sorting doubles in decreasing order" << endl;
    cout << "Before: "; print_vec(vec);
    insertion_sort(vec, reverse_cmp);
    cout << "After: ";  print_vec(vec);


    // sorting strings alphabetically
    vector<string> str_vec(6);
    str_vec[0] = "Alex"; str_vec[1] = "Carol"; str_vec[2] = "George";
    str_vec[3] = "Charles"; str_vec[4] = "Alice"; str_vec[5] = "Knuth";

    cout << "Sorting strings alphabetically" << endl;
    cout << "Before: "; print_vec(str_vec);
    insertion_sort(str_vec, str_cmp);
    cout << "After: ";  print_vec(str_vec);
}

10. A final twist to randomized quick sort

It turns out that the above implementation of randomized quick sort does not work well if the input items are chosen from a few values. In the worst case, for example, if all items in the input array are equal, then the randomized quick sort implementation above will run in \Omega(n^2)-time. The reason is that in the current implementation all elements strictly less than the pivot are on the left partition, and all elements greater than or equal to the pivot are on the right. Hence, if all input elements are equal then the left part of the partition will be empty and the right part has n-1 elements. You can use 3-way-partition quicksort which has been well-analyzed; but that involves heavy modification of the code.

There is a very simple modification which can take care of this problem. We can allow elements equal to the pivot to be on the left part too. And, we do this randomly: when we are scanning an element which is equal to the pivot, we flip a coin and put it on the left with probability half.

/*
 ******************************************************************************
 * file name  : better_rqs.cpp
 * author     : Hung Q. Ngo
 * description: a minor twist to the randomized quick sort algorithm which
 *              makes it run faster on inputs where the item values belong
 *              to a small finite class
 ******************************************************************************
 */
#include <iostream>
#include <vector>
#include <cstdlib>  // for rand() and srand()
#include <ctime>    // for time()

using namespace std;

/**
 *
 * -----------------------------------------------------------------------------
 * print a vector of Item_Type, finish with a new line
 * assumes compiler knows how to cout << Item_Type 
 * 
 * -----------------------------------------------------------------------------
 */
template <typename Item_Type>
void print_vec(vector<Item_Type>& vec) {
    for (int i=0; i<vec.size(); i++) {
        cout << vec[i] << " ";
    }
    cout << endl;
}

/**
 * -----------------------------------------------------------------------------
 * -1 if a < b, 0 if a==b, 1 if a>b
 * -----------------------------------------------------------------------------
 */
template <typename Item_Type>
int default_cmp(Item_Type a, Item_Type b) {
    return a < b? -1 : a == b ? 0 : 1;
}

/**
 * -----------------------------------------------------------------------------
 * The Randomized Quick Sort algorithm
 * - pick a random pivot, that's all
 * -----------------------------------------------------------------------------
 */
template <typename Item_Type>
void rqs_with_range(std::vector<Item_Type> &vec, int p, int q,
                    int (*cmp)(Item_Type, Item_Type))
{
    if (p >= q) return;

    // pick a random pivot
    int m = std::rand() % (q-p+1);
    std::swap(vec[q], vec[p+m]); 

    // partition
    int r=p-1;
    for (int j=p; j<q; j++) {
        if (rand() % 2 == 0) {
            if (cmp(vec[j],vec[q])<0)
                std::swap(vec[++r], vec[j]);
        } else {
            if (cmp(vec[j],vec[q])<=0)
                std::swap(vec[++r], vec[j]);
        }
    }
    std::swap(vec[++r], vec[q]);

    // sort the left & the right parts
    rqs_with_range(vec, p, r-1, cmp);
    rqs_with_range(vec, r+1, q, cmp);
}

/**
 * -----------------------------------------------------------------------------
 * Wrapper to the randomized quick sort algorithm
 * -----------------------------------------------------------------------------
 */
template <typename Item_Type>
void randomized_quick_sort(std::vector<Item_Type> &vec,
                    int (*cmp)(Item_Type, Item_Type) = default_cmp) 
{
    std::srand(static_cast<unsigned int>(std::time(0)));
    rqs_with_range(vec, 0, vec.size()-1, cmp);
}

/**
 * -----------------------------------------------------------------------------
 * returns a random vector of n elements, each from 0 to k-1
 * -----------------------------------------------------------------------------
 */
vector<int> random_vector(size_t n, size_t k) {
    srand(static_cast<unsigned int>(time(0)));
    vector<int> ret(n);
    for (int i=0; i<n; i++) 
        ret[i] = rand() % k;
    return ret;
}

// *****************************************************************************
int main() {
    // to test a specific sorting algorithm you can do
    vector<int> vec = random_vector(50000, 2);
    cout << "Before: "; print_vec(vec);
    randomized_quick_sort(vec);
    cout << "After: ";  print_vec(vec);
}
Chủ đề : Cấu trúc dữ liệu, Lập trình, Thuật Toán and tagged , , , . Bookmark the permalink. Trackbacks are closed, but you can post a comment.

16 Comments

  1. Posted 27/02/2012 at 4:12 pm | Permalink

    Anh Hưng soạn cẩn thận ghê, nhưng bài giảng nào cũng soạn thế này chắc hết thời gian nghiên cứu quá. :D Có cách nào để tính công giảng bài vào CV không nhỉ, chứ như hiện nay thì có vẻ ông lười cũng giống ông chăm. :D

    • Posted 27/02/2012 at 4:27 pm | Permalink

      Hi Nam, làm kỹ thì lần sau dạy lại đỡ tốn thời gian hơn nhiều. Ngoài ra, với những môn học thú vị và quan trọng như data structures, viết bài giảng cẩn thận cũng rất thú. Khi chạy các thí nghiệm ta thường khám phá ra những quan sát đơn giản mà phân tích lý thuyết có thể bỏ sót. Vả lại, không chạy thì làm thế nào mà biết merge sort, randomized quick sort, và heap sort cái nào thật sự nhanh hơn trên thực tế?

      Thật ra tôi thấy những GS nổi tiếng thường có các bài giảng rất hay, chi tiết, và chắc chắn là họ không cảm thấy mất thì giờ. (Hoàn toàn không có ý nói là tôi là một trong số họ, nhưng đó là điều tôi thấy nên học từ họ.) Việc trình bày lại một đề tài cơ bản như cấu trúc dữ liệu cũng là một công việc cực kỳ thú vị. Tôi thật sự không thích mấy cuốn sách hiện nay, kể cả textbook tôi dùng cho lớp này. Textbook mà viết sai thuật toán tìm kiếm nhị phân, chán phèo.

      • Posted 28/02/2012 at 1:17 am | Permalink

        Em cũng nghĩ là viết ra chi tiết, kể cả những thứ rất cơ bản sẽ giúp mình có một cái nhìn tốt hơn (và chính xác hơn) về vấn đề đó. Ngoài ra thì đây cũng là một cách khắc phục bệnh “ngại” nữa. :)

  2. RongChoi
    Posted 27/02/2012 at 5:38 pm | Permalink

    Anh Hưng có dạy thuật toán tìm kiếm Grover trên máy tính lượng tử không ạ? Một ví dụ đẹp và đơn giản cho thấy sức mạnh của máy lượng tử… (độ phức tạp N^{1/2} vượt qua cận dưới là thời gian tuyến tính cho máy tính thông thường)

    • Posted 27/02/2012 at 10:13 pm | Permalink

      Hi RongChoi, Chắc là không. Lớp này là lớp CTDL chứ không phải lớp thuật toán.

  3. Phien
    Posted 27/02/2012 at 8:17 pm | Permalink

    Bai giang cua thay Hung chi tiet ky luong ghe. Em cung vua hoc lop Data Structure vao semester truoc, nhung giao su cua em ko chuan bi bai giang ky luong nhu the nay.

  4. it4rb
    Posted 27/02/2012 at 10:11 pm | Permalink

    Chào GS Hưng, GS cho em hỏi là với các data 2 chiều (điểm trên bản đồ, gồm kinh độ và vĩ độ) thì có chiến lược nào để sắp xếp và tìm kiếm tốt nhất không ạ. Số là em có một bản đồ với khoảng 35000 điểm, và phải hiển thị dưới board nhúng, không thể load tất cả vào ram được. Cho nên em muốn sort trước trên PC rồi mới đưa xuống board, khổ nỗi em không biết cách so sánh cho loại data này như thế nào, mong anh cho em vài gợi ý. Em cám ơn :D

    • Posted 27/02/2012 at 10:17 pm | Permalink

      @it4rb, không rõ bạn muốn tìm kiếm như thế nào. Ví dụ, bạn có thể đinh nghĩa phép so sánh

      (x, y) < (a, b) nếu và chỉ nếu [x < a hoặc (x = ay<b)]

      rồi dùng tìm kiếm nhị phân như trên.

      • it4rb
        Posted 28/02/2012 at 12:06 am | Permalink

        Cám ơn GS.
        Em cần tìm kiếm các điểm nằm trong hình chữ nhật cho trước. Em sẽ xem lại theo cách của GS.

        • Posted 28/02/2012 at 9:02 am | Permalink

          @it4rb:

          Bài toán của bạn giống trường hợp đặc biệt của một bài toán tìm kiếm với range queries trong database. Ví dụ, trong DB ta có thể có một relation gồm 2 cột họ và tên. Và, ta muốn tìm tất cả các cặp (họ, tên) thuộc ([A--N], [X--Z]) chẳng hạn. Các range queries có thể gồm nhiều chiều hơn, ví dụ tìm một hộp trong không gian 3 chiều.

          K-d TreeR tree là các cấu cúc dữ liệu cổ điển cho bài toán đó.

  5. Vo Danh
    Posted 28/02/2012 at 5:52 am | Permalink

    Trong code về binary search, nên chăng cứ để: mid = (left+right)/2 -> vì nó đúng với bản chất vấn đề hơn, và thêm bình luận là nên lập công thức mid = left + (right – left)/2; để tránh tràn số. => những chi tiết kĩ thuật cũng quan trọng nhưng có lẽ không quan trọng bằng ý tưởng của thuật toán. Tương tự như vậy trong Insertion sort, có thể sử dụng luôn method insert của vector?

    • Posted 28/02/2012 at 8:50 am | Permalink

      @Vo Danh:

      Dùng insert của vector là sai vấn đề vì nó che thời gian chạy, và thậm chi nó … chạy sai vì nó sẽ shift tất cả các phần tử về bên phải

      Tôi không thấy (l+r)/2 là “đúng bản chất vấn đề hơn”.

  6. Nam
    Posted 29/02/2012 at 2:53 am | Permalink

    http://www.sorting-algorithms.com/

    Bài giảng của bác thật tuyệt vời :D Em đóng góp với bác trang này có animation về các thuật toán sắp xếp với các trạng thái ban đầu khác nhau, mà em nghĩ là nếu bố sung vào bài giảng được thì cũng rất thú vị. Hồi trước em học về sorting algorithm xem cái này nó visualize, ngộ ra bằng mấy chỉ đọc pseudo code :D

    • Posted 29/02/2012 at 8:59 am | Permalink

      Cảm ơn Nam. Tôi cũng biết website đó. Trong bài có câu: “This website has nice annimations of the sorting algorithms we discuss here.” và trong câu có link đến website Nam dẫn :-)

  7. tpd
    Posted 01/03/2012 at 6:52 am | Permalink

    Có hình rồi thì thêm tiếng nữa mới thú vị bác Hưng à, http://www.youtube.com/watch?v=t8g-iYGHpEA – What different sorting algorithms sound like :D

Post a Comment

Your email is never published nor shared. Required fields are marked *

*
*

You may use these HTML tags and attributes <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>