catalog

• Quick Sorting
• • Steps
  • Implementation
• Heap Sorting
• • Steps
  • Implementation
• Merge Sorting
• • Steps
  • Implementation

Quick Sorting

The worst-case Scenario for quick sorting is O(n²), such as quick sorting of sequential sequences, but its average expected time is O(nlogn).

Steps

1. Select an element from the sequence and call it a pivot.
2. Reorder the sequence, placing all items smaller than the pivot before the pivot and those larger than the pivot after the pivor. This is called partitioning operation.
3. Recursively sort subsequence that is less than the pivot and subsequence that is greater than the pivot.

Implementation

void quick_sort(int q[], int l, int r)
{
	if (l >= r) return;

	int i = l - 1, j = r + 1, x = q[l + r >> 1];
	while (i < j)
	{
		do i++; while (q[i] < x);
		do j--; while (q[j] > x);
		if (i < j) swap(q[i], q[j]);
	}
	quick_sort(q, l, j);
	quick_sort(q, j + 1, r);
}

Heap Sorting

Max-Heap: The value of each node is greater than or equal to the value of its child node, used in acsending oreder in the heap sort algorithm.
Min-Heap: ~

Steps

1. create a heap
2. swap the head and the tail of the heap.
3. reduce the size of the heap by 1 and call shift_down(0), the purpose is to adjust the top data of the new array to the corresponding position.
4. repeat step 2 until the size of the heap is 1.

Implementation

void max_heapify(int arr[], int start, int end)
{
	// create parent node and child node
	int pa = start;
	int chd = pa * 2 + 1;
	while (chd <= end)
	{
		if (chd + 1 <= end && arr[chd] < arr[chd + 1])
			chd++;
		if (arr[pa] > arr[chd])
			return;
		else
		{
			swap(arr[pa], arr[chd]);
			pa = chd;
			chd = pa * 2 + 1;
		}
	}
}

void heap_sort(int a[])
{
	//initialize, adjust i from the last parent node
	for (int i = len / 2 - 1: i >= 0; i--)
		max_heapify(arr, i, len - 1);
	//swap the first element with the previous element of the sorted element until the sorting is completed.
	for (int i = len - 1; i > 0; i--)
	{
		swap(arr[0], arr[i]);
		max_heapify(arr, 0, i - 1);
	}
}

Merge Sorting

2 methods:

1. top-down recursion
2. buttom-up iteration

Steps

1. apply for a space that its size is the sum of two sorted sequences. This size is used to store merged sequence.
2. Set two pointers, with the initial positions being the starting positions of two sorted sequences.
3. compare the elements pointed to by the two pointers, select the relatively small one and put it in the merge space and move the pointer to the next position.
4. repeat step 3 until a pointer reaches the end of the sequence
5. copy all remaining elements from another sequence direct to the end of merge sequence.

Implementation

void merge_sort(int arr[], int reg[], int start, int end)
{
	if (start >= end) return;
	int len = end - start, mid = (len >> 1) + start;
	int start1 = start, end1 = mid;
	int start2 = mid + 1, end2 = end;
	merge_sort(arr, reg, start1, end1);
	merge_sort(arr, reg, start2, end2);
	int k = start;
	while (start1 <= end1 && start2 <= end2)
		reg[k++] = arr[start1]<arr[start2]?arr[start1++]:arr[start2++];
		while (start1 <= end1)
			reg[k++] = arr[start1++];
		while (start2 <= end2)
			reg[k++] = arr[start2++]
		for (k = start; k <= end; k++)
			arr[k] = reg[k];
}