External Sort

External Sort:

What algorithm you will you use to sort data as big as 2 GB? A 2 GB data tells you that you can't bring all the data into the memory. We can and do bring only part of the data into memory. 

Here is the algorithm for external sort:

Algorithm External Sort: 

Suppose we can being only X MB of data into the memory for once.

1. Divide the file into k chunks, such that X*K = 2GB. Bring each chunk into memory and sort it using a $O(n*logn)$ algorithm. Save the lines back into the file.
2. Now, bring the next chunk into memory and sort.
3. once we're done, merge them one by one.

This is called as external sorting. And Step 3 is known as N-way merge.

Custom Sorting in C++

Custom Sorting in C++:

As we can as always use the sort() function to sort a data in a fixed order. You can sort an array of integers in ascending order, you can sort a string.

But what if you want to sort with some custom rule, Here is what you can do.

Suppose you want to sort an array of strings so that all the anagrams are next to each other. You can use the custom sort function as follows. First, create a comparator, it will compare the elements as you want it to. 

bool AnagramComparator(string s1, string s2){
	sort(s1.begin(), s1.end());
	sort(s2.begin(), s2.end());
	return s1 == s2;
	}

Now you can call the sort function as follows.

	sort(arr, arr+n, AnagramComparator);

Quick Sort in C++

Quick Sort:

Here is link for the detailed explanation and algorithm for quicksort: https://rishabhjainiitbhu.blogspot.com/2019/08/sorting-algorithms.html#more

Here is the algorithm for quickSort:

QuickSort(arr, start, end)

• Define pivot as arr[end]
• Get the location of the point of the pivot in resulting array, pivot=partition(arr, start, end)
• quicksort(arr, start, pivot-1)
• quicksort(arr, pivot+1, end)

Here is the code that implements this in c++:

void quicksort(int* arr, int start, int end){
	if(start<end){
	int part = Partition(arr, start, end);
	quicksort(arr, start, part-1);
	quicksort(arr, part+1, end);
	}
	}

Here is the algorithm for the partition of the array: The detailed explanation for partition function can be found here: https://rishabhjainiitbhu.blogspot.com/2019/08/sorting-algorithms.html#more 

Partition(arr, start, end)

• Define pivot = arr[end]
• p_index = start //this is the position we will place pivot the at.
• loop for i=start up to the end
• ..... if arr[i]<pivot
• ..........swap(arr[p_index], arr[i])
• ...........p_index++
• Once the loop is completed swap(arr[p_index], pivot).

Here is the code that implements this:

int Partition(int* arr, int start, int end){
	int pivot = arr[end];
	int p_index = start;
	for(int i=start;i<end;i++){
	if(arr[i]<=pivot){
	swap(&arr[i], &arr[p_index]);
	p_index++;
	}
	}
	swap(&arr[end], &arr[p_index]);
	return p_index;
	}

Bucket Sort in C++

Bucket Sort:

The detailed explanation and algorithm are given here: https://rishabhjainiitbhu.blogspot.com/2019/08/sorting-algorithms.html#more

Suppose you want to sort a range of float points in the range 0 to 1.

The algorithm was:

• Create n empty buckets (you can use vectors for it)
• For each element arr[i] in arr. Insert arr[i] into bucket number n*arr[i]
• sort individual buckets
• concatenate all sorted buckets.

Here is the code that does it:

void bucketSort(float* arr, int n){
	vector<float> b[n];
	for (size_t i = 0; i < n; i++) {
	float a = arr[i];
	int index = n*a;
	b[index].push_back(a);
	}
	for (size_t i = 0; i < n; i++) {
	sort(b[i].begin(), b[i].end());
	}
	int index = 0;
	for (size_t i = 0; i < n; i++) {
	for(float t: b[i]){
	arr[index++] = t;
	}
	}
	}

Merge Sort in C++

Merge Sort

The detailed algorithm and explanation is shared here: https://rishabhjainiitbhu.blogspot.com/2019/08/sorting-algorithms.html#more

Here is the algorithm in short:

Divide the given array into two.

pass each into mergesort

merge these two arrays into one.

return this new array.

Here is the code for mergesort function in c++:

void mergeSort(int* arr, int l ,int r){
	if(l<r){
	int m= (r+l)/2;
	mergeSort(arr, l, m);
	mergeSort(arr, m+1, r);
	merge(arr, l, m, r);
	}
	}

The algorithm for merge function is:

• create two new arrays of lengths equal to these subarrays. Copy the contents into these.
• start iterating in two arrays, check for which element is shorter among the two and push the shorter into the original array.

Here is the code for merge in c++:

void merge(int* arr, int l, int m, int r){
	int n1 = m-l+1;
	int n2 = r-m;
	int left[n1];
	int right[n2];
	for (size_t i = 0; i < n1; i++) {
	left[i] = arr[l+i];
	}
	for (size_t j = 0; j < n2; j++) {
	right[j] = arr[m+1+j];
	}
	int i=0, j=0, k=l;
	while (i<n1 && j<n2) {
	if(left[i]<=right[j]){
	arr[k] = left[i];
	i++;
	}else{
	arr[k] = right[j];
	j++;
	}
	k++;
	}
	while (i<n1) {
	arr[k] = left[i];
	i++;
	k++;
	}
	while (j<n2) {
	arr[k] = right[j];
	j++;
	k++;
	}
	}

Selection Sort in C++

Selection Sort:

The detailed explanation and algorithm can be found here: https://rishabhjainiitbhu.blogspot.com/2019/08/sorting-algorithms.html#more

The basic algorithm was:

Start at the beginning of an array, pass through the array finding the minimum element, put it at the first location in the array. In the next round we find the second minimum, place it at the second location of the array. So on and so forth.

Here is the code:

void selectionSort(int* arr, int len){
	for (size_t i = 0; i < len; i++) {
	int min=i;
	for (size_t j = i; j < len; j++) {
	if(arr[j]<=arr[min]){
	min = j;
	}
	}
	if(min == i)
	break;
	swap(&arr[i], &arr[min]);
	}
	}