[Data Structure / Algorithms] Bubble, Selection, Insertion Sort

주제: 시간복잡도 O(n^2) 의 정렬 알고리즘

---

• $O(n^2)$ 시간 복잡도는 좋은 성능은 아니지만, 아래의 정렬 알고리즘은 이해하기 쉬운 알고리즘들에 속한다.
• 이 알고리즘들은 O(1)의 공간 복잡도를 나타낸다.
• 작은 데이터의 경우 이러한 정렬 방식을 사용할는 것이 좋다.

Bubble Sort

• 이 알고리즘은 인접한 값들을 반복적으로 비교하며 필오하다면 서로 교환하여 정렬을 수행한다.
• 그러므로, 집합 내에 큰 값들은 컬렉션 마지막으로 "bubble up" 된다.
• 마지막부터 채워진다.

public func bubbleSort<Element>(_ array: inout[Element]) where Element: Comparable { 
	guard array.count >= 2 else { 
		return
	}
	
	for end in (1..<array.count).reversed() { 
		var swapped = false
		
		for current in 0..<end { 
			if array[current] > array[current + 1] { 
				array.swapAt(current, current + 1)
				swapped = true
			}
		}
		if !swapped { 
			return 
		}
	}
}

var array1 = [9,4,10,3]
bubbleSort(&array1)

[3,4,9,10]

Selection Sort

• 선택 정렬은 버블 정렬과 비슷하지만 swapAt 작업의 수가 버블 정렬보다 줄여진 상태이다.
• 선택 정렬은 각 단계에서 한 번만 swapAt을 수행한다.
• 첫번째 부터 채워진다.

public func selectionSort<Element>(_ array: inout [Element]) where Element: Comparable { 
	guard array.count >= 2 else { 
		return
	}
	
	for current in 0..<(array.count - 1) { 
		var lowest = current
		
		for other in (current + 1)..<array.count { 
			if array[lowest] > array[other] { 
				lowest = other 
			}
		}
		if lowest != current { 
			array.swapAt(lowest, current)
		}
	}
}

var array2 = [9,4,10,3]
selectionSort(&array2)

[3,4,9,10]

Insertion Sort

• 삽입 정렬은 bubble, selection 정렬보다 좀 더 유용한 정렬이다. 삽입 정렬은 평균 시간 복잡도는 $O(n^2)$ 이지만, 배열이 거의 정렬되어있다면 시간 복잡도는 O(n)이 된다. 즉, 삽입 정렬의 최상 시간은 O(n)이다.
• Swift standard 정렬 알고리즘은 하이브리드 정렬 접근법을 활용하는데, 작은양의 데이터 (<20 element)는 삽입 정렬을 활용한다.

public func insertionSort<Element>(_ array: inout [Element]) where Element: Comparable { 
	guard array.counr >= 2 else { 
		return 
	}
	
	for current in 1..<array.count { 
		for shifting in (1...currnet).reversed() { 
			if array[shifting] < array[shifting - 1] { 
				array.swapAt(shifting, shifting - 1)
			} else { 
				break
			}
		}
	}
}

출처(참고문헌)

• https://www.kodeco.com/books/data-structures-algorithms-in-swift/v4.0/chapters/26-o-n-sorting-algorithms

제가 학습한 내용을 요약하여 정리한 것입니다. 내용에 오류가 있을 수 있으며, 어떠한 피드백도 감사히 받겠습니다.

감사합니다.