## Saturday, October 9, 2010

### Sorting? Awesome fun for whole family

Bubble sort is dumb. Let's look at quick sort and merge sort.

Quick sort:

• O(nlogn) best and average.
• Worst case is O(n^2)
• divide and conquer mother fucker
• probably not stable (same keys may change order)
• pick a pivot, p, in the array (usually in the middle)
• partition into two arrays, one with all values <= p, the other with all values >= p
• the partition step can be done in place
• call quicksort on the two arrays
• if the array size is zero, you're done
```template  void qs2 (vector&; arr, int left, int right)
{
if (left >= right)
return;

int i = left, j = right;

int pivot = arr[(left + right) / 2];

while (i <= j) {
while (arr[i] < pivot)
i++;
while (arr[j] > pivot)
j--;
if (i <= j) {
swap(arr[i], arr[j]);
i++;
j--;
}
};

qs2(arr, left, i - 1);
qs2(arr, i + 1, right);
}
```

Now let's try some mergesort:

• worst case is O(nlogn)
• better for using slower data access things like files, tape drives
• don't have to store everything in memory
```template  void mergeSort (vector& v)
{
if (v.size() < 2) return;
// first divide in two, until only size 1 left
int n = v.size();
int middle = n / 2;
vector left;
left.insert(left.begin(), v.begin(), v.begin() + middle);

vector right;
right.insert(right.begin(), v.begin() + middle, v.end());

mergeSort(left);
mergeSort(right);

v.clear();

// then reconstitute such that the new result is in order
while (left.size() > 0 || right.size() > 0)
{
if (left.size() > 0 && right.size() > 0)
{
if (left <= right)
{
v.push_back(left.front());
left.erase(left.begin());
}
else
{
v.push_back(right.front());
right.erase(right.begin());
}
}
else if (left.size() > 0)
{
v.insert(v.end(), left.begin(), left.end());
left.clear();
}
else if (right.size() > 0)
{
v.insert(v.end(), right.begin(), right.end());
right.clear();
}
}
}```