# 14101 Quick Select Algorithm

## Brief
You are tasked to implement two helper functions to find the k^th^ smallest string in a list.
For detailed explanation, visit [this link](https://acm.cs.nthu.edu.tw/problem/14101/).
## Idea
To swap the strings, you might try to copy the string, something like:

void SwapString(char **str1, char **str2) {
    char tmp[1000];
    strcpy(tmp, *str1);
    strcpy(*str1, *str2);
    strcpy(*str2, tmp);
}

However, this approach falls flat to the fact that the strings are not necessarily equal in size. This means the longer string won't fit in the space for the shorter string, so we have to change the method. But how to do this? This is where **pointers** come into rescue.

In case you don't know what pointers are, here's a quick recap: a pointer is a variable that stores the "position" of another variable within the memory, i.e. the **address** of the variable. To give you a rough idea, if Mr. Holmes lives at the address 221B, Baker Street, then a piece of paper with the address *221B, Baker Street* scribbled on is technically a pointer that points to Mr. Holmes.

But how does this help? Well, we already know strings in C are merely arrays of characters whose head is determined by where the first character is located, and we know that the pointers are storing the address of that first character, so to "swap" two strings, we can simply make the pointer that points to one points to the other and vice versa.

To partition the strings, there are various ways to do this. Here is the version I think is the easiest to understand:

PROCEDURE Partition(A, l, r):
    min_idx ← l   //The index whose left side is all less than A[right]
    max_idx ← l   //The element we'll consider in each round
    while(max_idx < r):
        if A[max_idx] should come before A[r]:
            SWAP A[max_idx] and A[min_idx]
            min_idx ← min_idx + 1
        max_idx ← max_idx + 1
        /*
        After each iteration, all elements from l to min_idx-1 is less than A[r]
        and all elements from min_idx to max_idx-1 is greater or equal to A[r].
        The proof is tr***al and is left as an ex****se to the reader. :)
        
        Hint: Mathematical induction
        */
    SWAP A[min_idx] and A[r]
    return min_idx

This algorithm is quite intuitive when you think about it. Let's imagine you have a collection of books on a bookshelf, and you want to organize them. You choose the rightmost book as the pivot, which acts as a reference point for sorting. Now, starting from the left side of the shelf, you go through each book one by one.

If a book is "larger" (comes after) than the pivot, it's already on the right side—pun not intended—of the pivot. However, if a book is "smaller" (comes before) than the pivot, you'd like to insert it between the "smaller" and "larger" groups, but the "bookshelf" here has a fixed length, and inserting a book between two others isn't straightforward. So, what do you do? Well, you temporarily take out the first book larger than the pivot, creating a space for the new book. You then put the new book in the empty space, and finally place the larger book in the new book's former spot. You can do this until all the books has been compared with the pivot, at which point you can swap the first largest book with the pivot and you now know for sure that the pivot partitions the books into the "smaller" group and "larger" group.


## Solution
<details>
<summary>I believe in your ability, but do you?</summary>

void SwapString(char **str1, char **str2) {
    char *tmp = *str1;
    *str1 = *str2;
    *str2 = tmp;
}

int Partition(char **A, int l, int r) {
    int i = l;
    for (int j = l; j < r; j++) {
        if (strcmp(A[j], A[r]) < 0) {
            SwapStrings(&A[i], &A[j]);
            i++;
        }
    }
    SwapStrings(&A[i], &A[r]);
    return i;
}

</details>