void quickSort(int ints[], int low, int high)
{
    if(low < high) {
        int p = partition(ints, low, high);
        quickSort(ints, low, p-1);
        quickSort(ints, p+1, high);
    }
}

int partition(int ints[], int low, int high)
{
    int x = ints[high];
    int i = low - 1;
    for(int j = low; j < high; j++) {
        if(ints[j] <= x) {
            i++;
            swap(ints[i], ints[j]);
        }
    }

    swap(ints[i+1], ints[high]);
    return i+1;
}

* Strings
* null-terminated '\0'

#include <iostream>

int strlen(char s[])
{
    int i;

    for(i = 0; s[i] != '\0'; i++) {}
    return i;
}

int strrep(char s[], char src, char dst)
{
    for(int i = 0; s[i] != '\0'; i++) {
        if(s[i] == src) {
            s[i] = dst;
        }
    }
}

int strcmp(char s1[], char s2[])
{
    for(int i = 0; s1[i] != 0 && s2[i] != 0; i++) {
        if(s1[i] != s2[i]) {
             return s1[i] - s2[i];
        }
    }

    if(s1[i] == 0 && s2[i] != 0) {
        return s2[i];
    } else if(s1[i] != 0 && s2[i] == 0) {
        return s1[i];
    } else {
        return 0;
    }    
}

int main()
{
    const char[] MAGIC_STR = "Hello";
    const char[] EXIT_STR = "exit";
    char str[80];
    bool found = false;

    cout << "Type in the magic string.  Type exit if you give up.\n";

    while(!found) {
        if(strcmp(str, EXIT_STR) == 0) {
            cout << "Try again!\n";
            return 0;
        }
 
        if(strcmp(str, MAGIC_STR) == 0) {
            cout << "Good Job!\n";
            found = true;
        }
    }

    return 0;
}

int atoi(char s[])
{
    int i;
    int unit;
    int total = 0;
    int len = strlen(s);
    bool neg = false;

    unit = 0;
    if(s[0] == '-') {
        neg = true;
    }

    for(i = len - 1; i >= (neg ? 1 : 0); i--) {
        total = total + (s[i] - '0') * pow(10, unit);
        unit++;
    }

    return neg ? -1 * total : total;
}


* Pointers
* Memory

#include <iostream>

int main()
{
    int *p, v;

    v = 1;
    p = &v;
    *p = 24;
 
    cout << v << endl;

    return 0;
}

* arrays are pointers to the first element in a sequence values.
* you can treat pointers exactly like arrays.  arrays are almost exactly
like pointers, except you cannot write to an array variable itself, only
to elements in the array.  For pointers, you can write to the pointer or the
values pointed to by that pointer.


#include <iostream>

int main()
{
    int x[3] = {1,2,3};
    int *px;

    px = x;
    cout << *px << endl;
    cout << px[0] << endl;
    cout << px[1] << endl;
    cout << px[2] << endl;

    return 0;
}

px[i] <=> (*px + i)

void strcpy(char *dst, char *src)
{
    while(*src != '\0') {
        *dst = *src;
        dst++;
        src++;
    }
}

int main()
{
    char s[] = "hello\n";
    char d[10];

    strcpy(d, s);

    cout << d << endl;

    return 0;
}


void swap(int *x, int *y)
{
    int t = *x;
    *x = *y;
    *y = t;
}

int main()
{
    int x = 1, y = 2;

    swap(&x, &y);
    cout << x << " " << y << endl;
    return 0;
}

* Arrays of pointers

int main()
{
    char *strings[] = {"hello\n", "goodbye\n", "ciao\n"};

    for(i = 0; i < 3; i++) {
        cout << strings[i];
    }
}

* Arguments to your program
#include <iostream>
int main(int argc, char *argv[])
{
    for(int i = 0; i < argc; i++) {
        cout << argv[i] << endl;
    }
}

* Dynamic memory management

#include <iostream>
int main()
{
    int *p = new int;

    *p = 5;

    cout << *p << endl;
}

* Stack vs. Heap

* Dynamically allocated arrays

int main()
{
    int i;
    int n;
    int *nums;

    cout << "How many numbers do you want to sum? ";
    cin > n;

    nums = new int[n];

    for(i = 0; i < n; i++) {
        cout << "Enter number " << i + 1 << ": ";
        cin >> nums[i];
    }

    cout << "The sum is " << sum(nums, n) << endl;

    return 0;
}

* Once you allocate something, it doesn't get deallocated until the program
exits or you deallocate it.

delete x;
delete [] nums;

* Always delete any dynamically allocated memory, or you might run out.

int main()
{
    while(true) {
        int *x = new int;
    }

    return 0;
}

int main()
{
    while(true) {
        int *x = new int;
        delete x;
    }

    return 0;
}