TopCoder/ Sorting

Things to consider

1. efficiency
2. memory space
3. stability

Bubble sort

for (int i=0; i<data.size()-1; i++){
	for(int j=0; j<data.size()-i-1; j++){
        if(data[j] > data[j+1]){
            swap(data[j],data[j+1]);
        }
    }
}

it’s O(n^2), 常数的memory space, stable sort

Insertion Sort

for(int i=1; i<data.size(); i++){
    int j = i-1;
  	int temp = data[i];
  while(j >= 0 && data[j] > data[i]){
      data[j+1] = data[j];
      j--;
  }
  data[j+1] = temp;
}

插入排序对近似已经有序的序列效果很好。还有就是对于动态增长的序列，使用插入排序可以动态维护。

Merge Sort

void mergeSort(vector<int>& data, int left, int right){
	if(left < right){
        int m = left+(right-left) / 2; // here right-left to avoid overflow when right left and right is very big
      	mergeSort(data, m+1, right);
      	mergeSort(data, left, m);
      
      	merge(data, left, m, right);
    }
}

void merge(vector<int>& data, int left, int m, int right){
  	int n_left = m-left+1;
  	int n_right = right-m; // not inclued m
    vector<int> L(data.begin()+left, data.begin()+m+1); // [)
  	vector<int> R(data.begin()+m+1, data.begin()+right+1);
  
  	int i=0; // initial index of left array
   	int j = 0; // initial index of right array
  	int k = left; // initial index of data
  
  	while(i<n_left && j < n_rigt){
        if(L[i] <= R[j]){
            data[k] = L[i];
          	i++;
        }
      	else{
            data[k] = R[j];
          	j++;
        }
      	k++;
    }
  	// Copy the remainging elements of L or R
  	while(i<n_left){
        data[k++] = L[i++];
    }
  	while(j<n_right){
        data[k++] = R[j++];
    }
}

n(n^logn) . mege sort比较适合对链表的排序，因为quick sort里面有比较多的random access操作，所以quick sort对list并不是很合适。

Heap Sort

可以使用STL里面的priority_queue, 默认是最大堆，如果想使用最小堆，可以这样priority_queue<int, vector<int>, greater<int> > pq 然后pq就是最小堆了。记得跟greater less相反就行。

注意跟sort中greater less用法的不同。

sort(arr.begin(), arr.end(), less<int>()) // 这是增序 1，2 ，3
sort(arr.begin(), arr.end(), greater<int>()) // 这是降序 3, 2, 1

priority_queue<int, vector<int>, less<int> > pq // 这是最大堆， 3
priority_queue<int, vector<int>, greater<int> > pq // 这是最小堆， 1
 
还有一个不同是，sort传递的是函数，greater<int>()要有括号，而priority_queue不是

Quick Sort

void quicksort(vector<int>&data, int low, int high){
	if(low < high){
        int pi = partition(data, low, high);
      	quicksort(data, low, pi-1);
      	quicksort(data, pi+1, high);
    }
}

int partition(vector<int>& data, int low, int high){
    int pivot = data[high]; // choose the last item as pivot
  	int i = (low-1);
  	for(int j=low; j<high; j++){
        if(data[j] <= pivot){
            i++;
          	swap(data[i], data[j]);
        }
    }
  	swap(data[i+1], data[high]);
  	return i+1;
}

Quick sort time complexity is O(n^logn), worst case is O(n^2)

Counting Sort

Time complexity is O(n+k), n is the number of elements in input array and k is the range of input.

pseudocode: the data are in the range 0 to k ($0 <= data_i <= k$)

1. Take a count array to store the count of each unique object
2. Modify the count array such that each element at each index stores the sum of previous counts. It indicates the position of each object in the output sequence.
3. Ouput each object from the input sequence followed by decreasing its count by 1.

void countSort(vector<int>& arr){
  const int RANGE = k; // k should be a constant number, e.g. 9
  vector<int> output(arr.size());
  vector<int> count(RANGE + 1, 0);
  
  // 1
  for(int i=0; i<arr.size(); i++){
    ++count[arr[i]];
  }
  
  // 2
  for(int i=1; i<=RANGE; i++){
    count[i] += count[i-1];
  }
  
  // 3, this is unstable(left to right); right to left is stable
  for(int i=0; i<arr.size(); i++){
    output[count[arr[i]] - 1] = arr[i]; // -1 because starts from 0
    --count[arr[i]];
  }
  
  // copy the output back to arr
  copy(output.begin(), output.end(), arr.begin());
}

Radix Sort

As we know, counting sort’s time complexity is O(n+k), what if the elements are in range from 0 to $n^2$? We cannot use counting sort because counting sort will take $O(n^2)$ which is worse than comparision based sorting algorithms. Can we sort such an array in linear time?

Radix sort is to do digit by digit sort starting from least significant digit to most significant digit. Radix sort uses counting sort as a subroutine to sort.

This algorithm is only used to sort numbers

Time Complexity $O((n+b)d)$ or $O((n+b)log_b(m))$

Where n is the size of arrary, b is the representation base, for example, for decimal system, b is 10. d is the digits number of input integers. For example, m is the max number of array, then d should be $log_b(m)$

void countSort(vector<int>& arr, int exp){
  vector<int> output(arr.size());
  vector<int> count(10, 0);
  // count all occurance
  for(int i=0; i<arr.size(); i++){
    count[(arr[i]/exp)%10]++;
  }
  
  for(int i = 1; i<10; i++){
    count[i] += count[i-1];
  }
  
  // Reason for right to left is to be stable
  for(int i=(int)arr.size()-1; i>=0; i--){
    output[count[(arr[i]/exp)%10]-1] = arr[i];
    count[(arr[i]/exp)%10]--;
  }
  
  copy(output.begin(), output.end(), arr.begin());
}

void radixSort(vector<int>& arr){
  int m = *max_element(arr.begin(), arr.end());
  
  for(int exp = 1; m/exp > 0; exp *= 10){
    countSort(arr, exp);
  }
}

Bucket Sort

In some special cases, counting sort or radix sort could achieve linear time complexity. However, for counting sort or radix sort, they both have the same limitation that they use key as index. So if u want to sort a range of float number? How to do it?

Bucket sort is mainly useful when input is uniformly distributed over a range. For example, consider the following problem. Sort a large set of floating point numbers which are in range from 0.0 to 1.0 and are uniformly distributed across the range. How do we sort the numbers efficiently?

Pseudocode:

1. Create some buckets and put elements into them
2. apply some sorting algo to sort the elements in each bucket(insertion sort)
3. Take out and join all buckets together

Time Complexity average case is O(n+k) k is the number of buckets.

Worst is O(n^2), depends on the distribution of input.

pseudo code:
scatter: divide into diff buckets
sort each bucket
gather: put all elements back to original array


// Here arr's value is between 0 to 1
void bucketSort(vector<float>& arr){
  int len = arr.size();
  vector<float> buckets[len]; // here is a array of vector
  
  for(int i=0; i<len; i++){
    int index = len * arr[i];
    buckets[index].push_back(arr[i]);
  }
  
  for(int i=0; i<len; i++){
    sort(bucket[i].begin(), bucket[i].end());
  }
  
  int idx = 0;
  for(int i=0; i<len; i++){
    for(int j=0; j<buckets[i].size(); j++){
      arr[idx++] = buckets[i][j];
    }
  }
}

External Sort

When the data is too big or the computer’s memory is too small to load the data completely, at that time, we can take use of disk.

Reference Link: http://faculty.simpson.edu/lydia.sinapova/www/cmsc250/LN250_Weiss/L17-ExternalSortEX2.htm

External Sorting: Example of multiway external sorting

Ta1: 17, 3, 29, 56, 24, 18, 4, 9, 10, 6, 45, 36, 11, 43

Assume that we have three tapes (k = 3) and the memory can hold three records.

Main memory sort

The first three records are read into memory, sorted and written on Tb1,
the second three records are read into memory, sorted and stored on Tb2,
finally the third three records are read into memory, sorted and stored on Tb3.

Now we have one run on each of the three tapes:

Tb1: 3, 17, 29

Tb2: 18, 24, 56

Tb3: 4, 9, 10

The next portion of three records is sorted into main memory
and stored as the second run on Tb1:

Tb1: 3, 17, 29, 6, 36, 45

The next portion, which is also the last one, is sorted and stored onto Tb2:

Tb2: 18, 24, 56, 11, 43

Nothing is stored on Tb3.Thus, after the main memory sort, our tapes look like this:

Tb1: 3, 17, 29, | 6, 36, 45

Tb2: 18, 24, 56, | 11, 43

Tb3: 4, 9, 10

Merging

–Merging runs of length M to obtain runs of length k*M

In our example we merge runs of length 3
and the resulting runs would be of length 9.

We build a heap tree in main memory out of the first records in each tape.
These records are: 3, 18, and 4.

We take the smallest of them - 3, using the deleteMin operation, and store it on tape Ta1.

The record ‘3’ belonged to Tb1, so we read the next record from Tb1 - 17, and insert it into the heap. Now the heap contains 18, 4, and 17.

The next deleteMin operation will output 4, and it will be stored on Ta1.The record ‘4’ comes from Tb3, so we read the next record ‘9’ from Tb3
and insert it into the heap.
Now the heap contains 18, 17 and 9.Proceeding in this way, the first three runs will be stored in sorted order on Ta1.

Ta1: 3, 4, 9, 10, 17, 18, 24, 29, 56

Now it is time to build a heap of the second three runs.
(In fact they are only two, and the run on Tb2 is not complete.)The resulting sorted run on Ta2 will be:

Ta2: 6, 11, 36, 43, 45

This finishes the first pass.

–Building runs of length k*k*M

We have now only two tapes: Ta1 and Ta2.
We build a heap of the first elements of the two tapes - 3 and 6, and output the smallest element ‘3’ to tape Tb1.

Then we read the next record from the tape where the record ‘3’ belonged - Ta1, and insert it into the heap.

Now the heap contains 6 and 4, and using the deleteMin operation. the smallest record - 4 is output to tape Tb1.

Proceeding in this way, the entire file will be sorted on tape Tb1.

Tb1: 3, 4, 6, 9, 10, 11, 17, 18, 24, 29, 36, 43, 45, 56

The number of passes for the multiway merging is logk(N/M).

In the example this is [log3(14/3)] + 1 = 2.