Welcome To Sora Park

Heap Sort is conceptually a kind of binary tree. The advantage of Heap Sort is that no extra memory is needed in the sorting process!

A heap must satisfy the heap property, which says that the priority of every node is greater than or equal to the priority of any child nodes of that node.

When a heap is used to implement a priority queue, each node contains one of the items in the queue along with the number that specifies the priority of that item.

A priority queue is a generalisation of the stack and the queue, which supports the operations of inserting a new element and deleting the largest element. Each element of the queue has a priority associated with it.

The basic idea of Heap Sort is simply to build a heap containing the elements to be sorted and then to remove them all in order.

# Pseudocode

buf: array
n: array size

largest: index of largest value
l: index of left node
r: index of right node

sort()
    n := buf.size()
    
    for i is (n / 2) - 1 to 0 do:
    	heapify(n, i)
    else for
    
    for i is (n - 1) to 1 do:
    	swap(0, i)
        heapify(i, 0)
    else for
end

heapify(n, i)
	if l < n and buf[l] > buf[largest]
    	largest := l
    if r < n and buf[r] > buf[largest]
    	largest := r
    if largest is not equal to i
    	swap(i, largest)
        heapify(n, largest)
end

# Computation in C

# Time Complexity

• Worst complexity: O(n*log(n))
• Average complexity: O(n*log(n))
• Best complexity: O(n*log(n))

Merging is the operation of combining two sorted files to make one larger sorted file.

Merge Sort applies the "divide-and-conquer" paradigm as Quick Sort does. In Merge Sort, two recursive calls were followed by a merging procedure, which could be described as follows:

1. Divide the file in half
2. Sort the two halves recursively
3. Merge the two halves together while sorting them

Merge Sort is preferred over Quick Sort when there is a large dataset, and/or stored in external storage!

2021.08.24 - [Algorithms] - [Sorting] Quick Sort 퀵 정렬

# Example

# Pseudocode

mid: midpoint of the array

arr: original array
L: left-side array
R: right-side array
n1: left-side array size
n2: right-side array size

merge_sort(left, right):
	if left > right
    	return
    m := left + (right - 1) / 2;
    
    merge_sort(left, mid);
    merge_sort(mid + 1, right);
    
    merge(left, mid, right);
end

merge(left, mid, right):
    /* initialise both array sizes */
    n1 := mid - l + 1
    n2 := r - m
    
    /* Assign size to arrays each */
    L.resize(n1);
    R.resize(n2);
    
    /* insert values to L array */
    for i is 0 to n1 - 1 do:
    	L[i] := arr[l + i]
    end for
    
    /* insert values to R array */
    for j is 0 to n2 - 1 do:
    	R[j] := arr[m + 1 + j]
    end for
    
    /* initialise variables */
    i := 0
    j := 0
    k := l
    
    /* arrange values in ascending */
    while i < n1 and j < n2 do:
    	if L[i] <= R[j]
        	arr[k] := L[i++]
        else
        	arr[k] := R[j++]
        
        /* increase k by 1 */
        k++
    end while
    
    /* insert the rest of values in left array */
    while i < n1 do:
    	arr[k++] := L[i++]
    end while
        
    /* insert the rest of values in right array */
    while j < n2 do:
    	arr[k++] := R[j++]
    end while

# Computation in C

# Time Complexity

• Worst complexity: n*log(n)
• Average complexity: n*log(n)
• Best complexity: n*log(n)
• Space complexity: n

Merge Sort can always run in O(N log N) time, so this method is stable and simple to implement :)

Shell Sort is an in-place comparison sort that can be seen as either a generalisation of sorting by exchanging or sorting by insertion.

Insertion Sort is slow since it compares and exchanges only elements in neighbour, and Shell Sort solves this problem by allowing comparison and exchange of elements that are far apart to gain speed!

# Basic Idea

To arrange the list of elements so that, starting anywhere, taking every hth element produces a sorted list, which is called h-sort.

# Pseudocode

arr: array of elements
n: length of array
gap

tmp: temp value
j: temp index

for gap = n / 2; gap > 0; gap /= 2 do:
	for i is gap to n - 1 do:
    	/* select value to be inserted */
    	tmp := arr[i]
        
        /* shift element towards right */
        for j = i; j >= gap and arr[j - gap] > tmp; j -= gap do:
        	arr[j] := arr[j - gap];
        end for
        
        /* insert the value at hole position */
        arr[j] := tmp;
        
	end for
end for

# Computation in C

# Time Complexity

• Worst-case:
  - O(n^2) (worst known worst-case gap sequence)
  - O(n log^2 n) (best known worst-case gap sequence)
• Best-case performance:
  - O(n log n) (most gap sequences)
  - O(n log^2 n) (best known worst-case gap sequence)
• Average performance depends on gap sequence
• Worst-case space complexity:
  - О(n) total, O(1) auxiliary

The running time of this algorithm is heavily dependent on the gap sequence it uses!

# Basic Idea

To sort an array digit by digit starting at either the least significant digit (LSD) to most significant digit (MSD).

# Example

Original array: [170, 45, 75, 90, 24, 802, 2, 66]

1) LSD

1. Starting from the rightmost digit, sort the numbers based on that digit:
   [170, 90, 802, 2, 24, 45, 75, 66]
2. Next left digit:
   [802, 02, 24, 45, 66, 170, 75, 90]
3. And finally by the leftmost digit:
   [002, 024, 045, 066, 075, 090, 170, 802]

2) MSD

1. First digit, with brackets indicating buckets:
   [{045, 075, 090, 024, 002, 066}, {170}, {802}]
2. Next digit:
   [{ {002}, {024}, {045}, {066}, {075}, {090} }, 170, 802]
3. Final digit:
   [002, {024}, 045, 066, 075, 090, 170, 802]

# Pseudocode

arr: array
m: maximum value
mx: temp max value

count: temp array
output: ordered array
i: index

radix_sort()
	m := get_max()
    for exp = 1; (m / exp) > 0; exp *= 10 do:
    	count_sort(exp)
    end for
end

get_max()
	mx := arr[0]
    for i is 1 to arr.size() - 1 do:
    	if arr[i] is greater than mx
        	mx := arr[i]
    end for
	return mx
end

count_sort(exp)
	output.resize(arr.size())
    count.resize(10)
    
    for i is 0 to arr.size() - 1 do:
    	count[(arr[i] / exp) % 10]++
    end for
    
    for i is 1 to 9 do:
    	count[i] += count[i - 1]
    end for
    
    for i is (arr.size() - 1) to 0 do:
    	output[count[(arr[i] / exp) % 10] - 1] := arr[i]
        count[(arr[i] / exp) % 10]--
    end for
    
    for i is 0 to (arr.size() - 1) do:
    	arr[i] := output[i]
    end for
end

# Computation in C

# Time Complexity

• Worst complexity: n*k/d
• Average complexity: n*k/d
• Space complexity: n+2^d

n is the number of keys.

k is the maximum number of digits.

d is the key length.