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]

 

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

 

 

 

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 앞에 위치하게 된다.

 

 

 

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]