[Sorting] Bubble Sort 버블정렬

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)