Welcome To Sora Park

The basic idea of Bubble Sort is to let greater elements bubble to the right-hand side of the sorted file (or array). The sorting process is as below:

1. Compare two elements in the neighbour. If they are not in the proper order, exchange them. Therefore, the greatest element bubbles to the most right.
2. Compare two elements in the neighbour, except the greatest ones that have already been sorted on the right. If they are not in order, swap them, so that a greater element bubbles to the right.
3. Repeat the above processes until all elements are sorted in the proper order.

# Example

array = { 170, 45, 75, 90, 802, 24, 2, 66 };

1. 170 ↔ 45 : { 45, 170, 75, 90, 24, 2, 66, 802 }
   170 ↔ 75 : { 45, 75, 170, 90, 24, 2, 66, 802 }
   170 ↔ 90 : { 45, 75, 90, 170, 24, 2, 66, 802 }
   170 ↔ 24 : { 45, 75, 90, 24, 170, 2, 66, 802 }
   170 ↔ 2 : { 45, 75, 90, 24, 2, 170, 66, 802 }
   170 ↔ 66 : { 45, 75, 90, 24, 2, 66, 170, 802 }
   170 and 802 are not swapped since 802 is greater than 170.
2. 90 ↔ 24 : { 45, 75, 24, 90, 2, 66, 170, 802 }
   90 ↔ 2 : { 45, 75, 24, 2, 90, 66, 170, 802 }
   90 ↔ 66 : { 45, 75, 24, 2, 66, 90, 170, 802 }
3. 75 ↔ 24 : { 45, 24, 75, 2, 66, 90, 170, 802 }
   75 ↔ 2 : { 45, 24, 2, 75, 66, 90, 170, 802 }
   75 ↔ 66 : { 45, 24, 2, 66, 75, 90, 170, 802 }
4. 45 ↔ 24 : { 24, 45, 2, 66, 75, 90, 170, 802 }
   45 ↔ 2 : { 24, 2, 45, 66, 75, 90, 170, 802 }
5. 24 ↔ 2 : { 2, 24, 45, 66, 75, 90, 170, 802 }

result = { 2, 24, 45, 66, 75, 90, 170, 802 };

# Pseudocode

arr: array
tmp: temp value

test()
    for i is arr.size() to 1 do:
    	for j is 1 to i - 1 do:
            if arr[j - 1] is greater than arr[j]
                tmp := arr[j - 1]
                arr[j - 1] := arr[j]
                arr[j] := tmp
         end for
     end for
end

# Computation in C

# Time Complexity

• Worst complexity: O(n²)
• Average complexity: O(n²)
• Best complexity: O(n)

# Space complexity

• O(1)

Quick Sort is quite easy to be implemented and has a good average performance (N log N).

However, this algorithm is not very stable since the performance in the worst case is N * N (N^2).

The basic idea of Quick Sort is to apply "divided-and-conquer" paradigm like Merge Sort, which works based on the mechanism to partition the file into two parts, then recursively sort the parts independently. The detailed procedure is as follows:

1. Choose a pivotal (central) element
   For example, first, last or middle element
2. Elements on either side are then moved so that the elements on one side of the pivot are smaller and those on the other side are larger
3. Apply the above procedure to the two parts until the whole file is sorted in the proper order

2021.08.24 - [Algorithms] - [Sorting] Merge Sort 합병 정렬

# Example

array = { 10, 80, 30, 90, 40, 50, 70 };

1. Pivot: 70
   array_left = { 10, 30, 40, 50 }
   array_right = { 90, 80 }
2. Pivot: 50 and 80 respectively
   array_left = { 10, 30, 40 }
   array_right = { 90 }
3. Pivot: 40 and null
   array_left = { 10, 30 }
   array_right = { }
4. Pivot: 30 and null
   array_left = { 10 }
   array_right = { }
5. Finally, there is only one value to be considered: 10

result = { 10, 30, 40, 50, 70, 80 };

# Pseudocode

arr: original array
n: array size
pi: mid index

pivot: pivot value
i: index

quick_sort(low, high)
    n := buf.size()	
    
    if low is less than high
    	pi := partition(low, high)
        
        quick_sort(low, pi - 1)
        quick_sort(pi + 1, high)
end

partition(low, high)
    pivot := buf[high]
    i := low - 1
    
    for j is low to high - 1 do:
    	if buf[j] is less than pivot
            swap(++i, j)
    end for
    
    swap(++i, high)
end

# Computation in C

# Time Complexity

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

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 :)