[Algorithm] 정렬 알고리즘(1) - 버블정렬, 선택정렬, 삽입정렬

"정렬 알고리즘"은 일련의 원소들에 대해 정해진 규칙에 맞게 재배열하는 알고리즘이다. 

정렬 알고리즘은 현대까지도 계속 발명 될 정도로, 많은 알고리즘이 존재하지만 이중 대표적으로 몇가지만 살펴볼것이다. 

 

 

정렬 알고리즘 분류 기준

정렬 알고리즘은 여러 기준으로 분류된다. 

 

안정 정렬 vs. 불안정 정렬 

"안정 정렬"이란, 정렬조건이 동일한 원소가 여러개 있을 때, 입력 때와 동일한 순서로 정렬되는 정렬 알고리즘이다.

반면, "불안정 정렬" 입력 때와 동일한 순서로 졍렬되는 것을 보장하지 않는다. 

 

"안정 정렬"은 정렬조건이 동일한 원소들의 순서를 보장해야할 때, 유용하게 사용될 수 있다. 

예를 들어, 온라인 쇼핑몰에서 구매자의 구매 요청이 요청 순서대로 쌓인다고 가정해보자. 

이때, 등급이 높은 회원부터 배송하기 위해서 등급순으로 정렬했을때,

불안정 정렬은 등급이 같은 회원일 경우, 먼저 구매했더라도 나중에 배송되는 상황이 발생할 수 있다. 

이럴 경우 안정 정렬은 유용하게 사용될 수 있다.

 

제자리 정렬인지 아닌지 

"제자리 정렬(In-place)" 추가적인 자료구조를 사용하지 않고 정렬이 가능한 정렬 알고리즘이다. 다만, 추가적인 변수를 위해 약간의 추가 공간은 허용한다. 

 

제자리 정렬은 다음과 같은 장점을 갖는다. 

우선, 추가적인 메모리 공간을 필요로하지 않는다는 점에서 메모리 측면으로 이득이 있다. 

또한, 거의 모든 정렬 알고리즘은 배열을 자료구조로 사용하며, 배열은 메모리 공간에 연속적으로 할당되기 때문에, Cache hit 비율이 높다. 이러한 하나의 배열내에서 정렬알고리즘을 수행할 수 있다면, 공간 지역성에 의해 상대적으로 좋은 성능을 가지게 될 것이다. 

 

 

버블 정렬 

"버블 정렬"은 제자리 정렬로,  두 원소의 대소관계를 비교하여 위치를 변경을 반복하는 정렬 알고리즘이다. 

또한, 인접한 원소와의 대소관계를 비교하기 때문에, 안정정렬이다.

 

자세한 절차는 다음과 같다. 

extension Array where Element: Comparable {
	func bubbleSort(
		sortedBy: (Element, Element) -> Bool = { $0 < $1 }
	) -> [Element] {
		var sortedArray = self
		
		for i in (0..<self.count) {
			var isChanged = false
			
			for j in (0..<self.count-i-1) {
				if !sortedBy(sortedArray[j], sortedArray[j + 1]) {
					sortedArray.swapAt(j, j + 1)
					isChanged = true
				}
			}
			
			if !isChanged { break }
		}
		
		return sortedArray
	}
}

print([2, 5, 3, 1].bubbleSort()) // [1, 2, 3, 5]

• 1번째 원소부터 시작하여, 오른쪽의 원소와 대소관계를 비교한 후 필요하면 위치를 변경한다. 
• 해당 과정을 n번째 원소까지 완료한다. 
• 한번의 순회가 완료되면, 1번과정을 1부터 n-1번째 원소까지 반복한다. 
• 이를 배열에 아무 변화가 없을때까지 반복한다. 

위에서 볼 수 있겠지만, 2중 포문을 돌기 때문에 최악, 평균의 경우 모두 $O(n^2)$이다. 

하지만, 모든 원소가 정렬되어 있다면 for문이 바로 종료되기 때문에, 최선의 경우 $O(n)$이다. 

 

선택 정렬 

"선택 정렬"은 제자리 정렬로, 다음과 같이 수행한다.

• 배열에서 제일 작은 원소를 탐색한다. 
• 그 값을 맨앞에 위치한 값과 swap한다. 
• 맨앞의 위치의 원소를 제외하고 위의 내용을 반복한다. 

즉, 매 시행마다 앞자리가 하나씩 결정난다. 

extension Array where Element: Comparable {
	func selectionSort(
		sortedBy: (Element, Element) -> Bool = { $0 < $1 }
	) -> [Element] {
		var sortedArray = self
		
		for i in 0..<self.count {
			
			var minIndex = i
			for j in i..<self.count {
				sortedBy(sortedArray[i], sortedArray[j]) ? () : (minIndex = j)
			}
			
			sortedArray.swapAt(i, minIndex)
		}
		
		return sortedArray
	}
}

print([2,3,1,4,7].selectionSort(sortedBy: <)) // [1, 2, 3, 4, 7]

위의 코드에서 볼 수 있겠지만, 선택 정렬은 최선, 최악, 평균의 경우 모두 $O(n^2)$이다. 

빈번하게 swap연산이 있었던 버블정렬과 비교해보자면, 매 시행마다 딱 한번 swap연산이 일어나기 때문에, 일반적으로 버블정렬보다 성능이 좋다. 

 

또한, 선택 정렬은 불안정정렬이다.

다음과 같은 원소들이 있다고 가정해보자. 

(이때, 2와 2.은 같은 원소이고, 둘을 구분하기 위해 "!"을 붙였다.)

2 2! 1 3

 

우선, 1과 2의 위치가 변경되게 되면, 정렬은 종료된다. 

1 2! 2 3

이때, 정렬전에는 2 2! 이었지만, 정렬후에는 2! 2로 순서가 변경되었다. 

즉, 정렬 조건이 같은 원소에 대해 입력때와 동일한 순서를 보장하지 않는다. 

 

삽입 정렬

"삽입 정렬"은 제자리 정렬로, 

배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 부분과 비교하여, 자신의 위치를 찾아 삽입하는 정렬알고리즘이다. 

 

즉, 다음과 같다. 

• 2번째 원소부터 시작해, 1번째 원소와 비교해 삽입될 위치를 결정한다. 
• 3번째 원소를 1, 2번째와 비교해 삽입될 위치를 결정한다. 
• 이를 마지막 원소까지 진행하면된다. 

extension Array where Element: Comparable {
	func insertionSort(
		sortedBy: (Element, Element) -> Bool = { $0 < $1 }
	) -> [Element] {
		guard self.count > 1 else { return self }
		var sortedArray = self
		
		for i in 1..<self.count {
			let key = sortedArray[i]
			
			var j = i-1
			// key값보다, 뒤로 밀어야 한다면 뒤로 밀고 남는 공간에 key를 삽입
			while j >= 0 && sortedBy(key, sortedArray[j]) {
				sortedArray[j+1] = sortedArray[j]
				j -= 1
			}
			sortedArray[j+1] = key
		}
		
		return sortedArray
	}
}

print([2,3,1,4,7].insertionSort(sortedBy: <)) // [1, 2, 3, 4, 7]

 

이러한 삽입 정렬은 안정 정렬이며,

다 정렬되어 있는 경우(최선의 경우) $O(n)$이고, 

평균, 최악의 경우 $O(n^2)$이다. 

 

또한, 버블 정렬과 선택 정렬과 비교했을 때 가장 성능이 좋은 정렬 알고리즘이다. 

 

 

References 

위키백과 

• Sorting Algorithm
• Bubble Sort
• Selection Sort
• Insertion Sort