swift로 구현한 선택(Selection Sort), 버블(Bubble Sort), 삽입(Insertion Sort) 정렬

데이터의 값을 순서대로 정렬하는 정렬 알고리즘(Sort Algorithm) 중 가장 기본이 되는 3가지 정렬에 대해 살펴보겠다.

 

 

1) 선택정렬(Selection Sort)

첫번째 인덱스부터 순차적으로 검사하여 해당 인덱스의 값과 그 뒤의 숫자 중 가장 작은 수를 swap해주는 정렬 방식이다. 비교 기준이 되는 값은 첫번째 인덱스부터 순차적으로 들어가게 된다.

 

예를 들어 [5, 8, 3, 1] 배열이 있을 때,

제일 먼저, 5(index 0)와 1(index0번 뒤로 가장 작은 수)의 크기를 비교해서 위치를 바꿔주고 [5, 8, 3, 1] -> [1, 8, 3, 5]

그 다음 8(index 1)과 3(index1번 뒤로 가장 작은 수)을 비교한 뒤 위치를 바꿔주고 [1, 8, 3, 5] -> [1, 3, 8, 5]

그 다음 8(index 2)과 5(index2번 뒤로 가장 작은 수)을 비교하고 위치를 바꿔준다 [1, 3, 8, 5] -> [1, 3, 5, 8]

 

코드로 구현하면 아래와 같다.

 

	func selectionSort<T: Comparable>(array: inout [T]) {
	for arrIndex in 0..<array.count { // array배열 순환
	var minNumber = array[arrIndex] // 가장 작은 수 저장(초기값으로 순환이 시작되는 첫번째 인덱스 값을 저장)
	var minIndex = arrIndex // 가장 작은 수의 인덱스 저장(초기값으로 순환이 시작되는 첫번째 인덱스를 저장)
	for index in arrIndex+1..<array.count { // arrIndex의 다음 index부터 순환
	if minNumber > array[index] { // 가장 작은 수와 그 인덱스 찾기
	minNumber = array[index]
	minIndex = index
	}
	}
	array.swapAt(arrIndex, minIndex) // 가장 작은수와 위치 바꿔주기
	}
	}
	var numberArr = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
	var stringArr = ["z", "x", "p", "c", "b", "a"]
	selectionSort(array: &numberArr)
	selectionSort(array: &stringArr)

view raw SelectionSort.swift hosted with ❤ by GitHub

 

 

2) 버블정렬(Bubble Sort)

인접한 값 2개씩 비교하여 작은수는 앞으로, 큰 수는 뒤로 보내는 정렬 방식이다. 

반복 1번이 끝날 때 마다 가장 큰 수가 제일 뒤로 가는 식으로 정렬 된다.

 

예를 들어, [5, 8, 3, 1]이 있을 때,

제일 먼저 5, 8을 비교한다. 5는 8보다 작으므로 swap이 일어나지 않는다. [5, 8, 3, 1]

그 다음 8, 3을 비교하여 3이 더 작으므로 swap을 해준다 [5, 8, 3, 1] -> [5, 3, 8, 1]

그 다음 8과 1을 비교하여 1이 더 작으므로 swap을 해준다 [5, 3, 8, 1] -> [5, 3, 1, 8]

이렇게 반복문 1번이 끝나게 되고 가장 큰 수가 제일 뒤로 가게 된다.

2번째 반복문이 끝나면 두번째로 큰 수인 5가 8 앞에 위치하게 된다.

 

	func bubbleSort<T: Comparable>(input: inout [T]) {
	// 반복 1회당 가장 큰 수가 맨 뒤에 정렬되므로 배열의 요소 개수 만큼 반복문을 실행한다
	for i in 0...count {
	// flag : swap이 일어날 경우 true를 할당해 준다
	// 만약 반복 1회가 완료되는 동안 swap이 한차례도 일어나지 않을 경우 모든 숫자가 정렬된 상태이므로 함수를 종료한다
	var flag = false
	// 정렬된 숫자는 반복문에서 제외해도 되므로 (i+1)만큼 빼준 횟수를 반복해준다
	// i는 0부터 시작하므로 i+1을 해준다
	for j in 0..<input.count-(i+1) {
	if input[j] > input[j+1] { // 앞의 값과 그 다음 값을 비교
	input.swapAt(j, j+1) // 앞의 값이 클 경우 swap해준다
	flag = true // swap이 실행되었으므로 flag는 true로 바꿔준다
	}
	}
	if flag == false { // flag가 false인 경우 swap이 한차례도 일어나지 않았으므로 모든 값이 정렬된 상태이다
	return // 함수를 종료해준다
	}
	}
	}
	var numberArr = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
	var stringArr = ["z", "x", "p", "c", "b", "a"]
	bubbleSort(input: &numberArr)
	bubbleSort(input: &stringArr)

view raw BubbleSort.swift hosted with ❤ by GitHub

 

 

3) 삽입정렬(Insertion Sort)

배열을 순회하며 현재 위치의 값을 이전의 값들 중 적절한 위치에 삽입해 나가는 방식이다.

 

예) [8, 5, 3, 1]을 정렬해보자

먼저, 정렬되는 값은 8, 5, 3, 1 순서대로 진행이 된다.

8은 첫번째 값이므로 이전 값이 없으니 넘어가면 된다.  [8, 5, 3, 1]

5는 8과 비교했을 때 8보다 작으므로  8과 위치를 바꿔준다. [8, 5, 3, 1] -> [5, 8, 3, 1]

3은 먼저 8과 비교하고 위치를 바꿔준다. 그 뒤 다시 5와 비교하고 위치를 바꿔준다

 [5, 8, 3, 1] -> [5, 3, 8, 1] -> [3, 5, 8, 1]

1도 같은 방식으로 앞의 값들과 하나씩 비교하여 위치를 적절히 바꿔주면 된다

 [3, 5, 8, 1] -> [3, 5, 1, 8] -> [3, 1, 5, 8] -> [1, 3, 5, 8]

 

	func insertionSort<T: Comparable>(input: inout [T]) {
	// 배열 요소 수만큼 반복문을 실행한다
	for index in 0..<input.count {
	var i = index
	// 0번 index는 비교할 필요가 없으므로 0보다 큰 값만 비교해준다.
	while i > 0, input[i-1] > input[i] {
	// 현재 값과 이전 값을 비교하여 이전 값이 더 클 경우 값들의 위치를 바꿔준다
	input.swapAt(i-1, i)
	i -= 1
	}
	}
	}
	var numberArr = [5, 2, 4, 6, 1, 3]
	var stringArr = ["z", "x", "p", "c", "b", "a"]
	insertionSort(input: &numberArr)
	insertionSort(input: &stringArr)

view raw InsertionSort.swift hosted with ❤ by GitHub