Welcome To Sora Park

The basic idea is as follows:

1. Select successive elements in ascending order and place them into their proper position.
2. Find the smallest element from the array, and exchange it with the first element.
   Find the second smallest element, and exchange it with the second element;
   and so on.
3. Repeat these procedures until the data is sorted in the proper order.

# Example

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

1. Smallest value 2:
   170 ↔ 2 { 2, 45, 75, 90, 802, 24, 170, 66 }
2. Smallest value 24:
   45 ↔ 24 { 2, 24, 75, 90, 802, 45, 170, 66 }
3. Smallest value 45:
   75 ↔ 45 { 2, 24, 45, 90, 802, 75, 170, 66 }
4. Smallest value 66:
   90 ↔ 66 { 2, 24, 45, 66, 802, 75, 170, 90 }
5. Smallest value 75:
   802 ↔ 75 { 2, 24, 45, 66, 75, 802, 170, 90 }
6. Smallest value 90:
   802 ↔ 90 { 2, 24, 45, 66, 75, 90, 170, 802 }
7. Smallest value 170:
   170 ↔ 170 { 2, 24, 45, 66, 75, 90, 170, 802 }
8. Smallest value 802:
   802 ↔ 802 { 2, 24, 45, 66, 75, 90, 170, 802 }

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

# Pseudocode

arr: array
min: index of minimum value (target)
tmp: temp value

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

# Computation in C

# Time Complexity

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

# Space complexity

• O(1)

Insertion Sort is almost as simple as Selection Sort, but a little more flexible!

The basic idea is to sort a collection of records by inserting them into an already sorted file. The process can be described as follows:

1. Take elements one by one
2. Insert the element in its proper position among those already taken and sorted in a new collection
3. Repeat these processes until all elements are taken and sorted in the proper order

# Example

array = { 12, 11, 13, 5, 6 };

1. Current value 11:
   12 > 11 { 11, 12, 13, 5, 6 }
2. Current value 13:
   12 < 13 and 11 < 13
3. Current value 5:
   13 > 5 { 11, 12, 13, 13, 6 },
   12 > 5 { 11, 12, 12, 13, 6 },
   11 > 5 { 11, 11, 12, 13, 6 }, and
   assign the current value to the first one { 5, 11, 12, 13, 6 }
4. Current value 6:
   13 > 6 { 5, 11, 12, 13, 13 },
   12 > 6 { 5, 11, 12, 12, 13 },
   11 > 6 { 5, 11, 11, 12, 13 },
   5 < 6 { 5, 11, 11, 12, 13 }, and
   assign the current value to the second one { 5, 6, 11, 12, 13 }

result = { 5, 6, 11, 12, 13 };

# Pseudocode

buf: array
tmp: temp value

for i is 1 to buf.size() - 1 do:
	tmp := buf[i]
    
    for j is i - 1 to 0 when buf[j] > tmp && j > -1 do:
    	buf[j + 1] := buf[j]
    end for
    
    buf[j + 1] := tmp
end

# Computation in C

# Time Complexity

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

# Space complexity

• O(1)

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