swift ) 버블정렬 vs 선택정렬 vs 삽입정렬, 코드 효율성 생각해보기

 

버블정렬과 선택정렬, 삽입정렬을 비교해보고, 빅오의 개념과 코드의 효율성에 대해 생각해보기

 

 

우선 오름차순으로 정렬하는 경우의 처리과정과 각각의 예제를 정리해봄

 

버블정렬 

연속된 항목 비교 -> 정렬 -> 포인터를 한 칸 옮김 -> 반복

패스스루가 끝나면 다시 처음부터 정렬, 교환이 일어나지 않는 경우 루프 종료

 

버블정렬 예시

//오름차순으로 정렬 - bubble sort
var arr = [2,1,3,4,5]
var temp = 0
while true {
	var count = 0
    for i in 0..<arr.count-1 {
        if arr[i] > arr[i+1] {
            temp = arr[i]
            arr[i] = arr[i+1]
            arr[i+1] = temp
            count += 1
        }
    }
    if count == 0 {
		break
    }
}

 

-> 버블정렬의 효율성은 O(N^2)이다.

 

 

선택정렬

배열을 순서대로 읽어가면서 최소값을 기록 -> 시작 인덱스의 값과 최소값을 교환 -> 시작했던 인덱스의 다음 인덱스부터 반복

 

선택정렬 예시

var arr = [4,1,2,5,3]

for i in 0..<arr.count-1 {
	var min = i
    for j in i+1..<arr.count {
    	if j < arr[min] {
        	min = j
        }
    }
    if min != i {
        let temp = arr[i]
        arr[i] = arr[min]
        arr[min] = temp
    }
}

-> 선택정렬의 효율성도 O(N^2)이다.

 

 

 

삽입정렬

1. 두 번째 인덱스의 값(=현재인덱스라고 적겠음)을 임시변수에 저장 -- 이후의 패스스루에서 삭제하는 현재인덱스의 위치는 1씩 증가

2. 현재인덱스의 왼쪽에 있는 값들과 임시변수의 값을 비교,

왼쪽의 값이 더 클 경우 해당 값을 오른쪽으로 이동 & 현재인덱스의 위치가 왼쪽으로 옮겨짐

2단계의 과정을 반복할건데

임시변수의 값보다 작은 값을 만나거나, 현재인덱스의 위치가 왼쪽 끝에 도달할 경우 2단계 종료

3. 임시변수의 값을 현재인덱스의 위치에 삽입

-> 1에서 삭제하려는 인덱스의 값이 배열의 마지막 인덱스가 될 때까지 1,2,3을 반복

 

삽입정렬 예시

var arr = [5,1,3,2,4]

for i in 1..<arr.count {
	let temp = arr[i]
	var currentIndex = i - 1
	while currentIndex >= 0 {
		if arr[currentIndex] > temp {
			arr[currentIndex+1] = arr[currentIndex]
			currentIndex -= 1
		} else {
			break
		}
	}
	arr[currentIndex+1] = temp
}

-> 삽입정렬의 효율성도 O(N^2)이다.

 

 

 

세 가지 정렬의 효율성을 빅오로 나타내면 모두 O(N^2)가 된다.

결론부터 말하자면 실제 알고리즘의 속도는 같지 않다.

왜 빅오로 표기하면 같은데 실제 속도가 다를까?

빅오란

데이터의 크기에 따라 알고리즘의 단계가 어떻게 달라지는지를 나타내는 척도인거고,

어떤 카테고리에 속해있나? 정도를 나타내는 척도이기 때문이다.

 

 

먼저 버블정렬과 선택정렬을 비교해보면

버블정렬의 경우 0부터 마지막 인덱스까지 반복해서 비교를 하는 반면

선택정렬의 경우 비교하는 인덱스의 시작지점이 패스스루를 반복할 때마다 뒤로 옮겨지기 때문에 비교하는 횟수가 더 적다.

실제로 거치는 단계수를 비교해보면 동일한 배열을 기준으로 2배 차이가 나게 된다.

 

 

삽입정렬을 자세히 살펴보자

특정 인덱스의 값을 임시변수에 저장, 비교, 이동, 삽입의 각 과정을를 거친다.

임시변수에 저장하는 과정에서 N-1만큼의 단계를 거치고

비교하는 과정 , 이동하는 과정에서 각각 N^2/2의 단계를 거치며

삽입과정에서 N-1의 단계를 거친다.

따라서 총 N^2+2N-2 단계를 거치는 알고리즘이 되는 것이다.

 

빅오에서 여러 차수가 섞여있을 경우, 가장 높은 차수만 고려하기 때문에 

삽입정렬을 O(N^2)의 효율성을 갖는 알고리즘으로 표기하는 것이다.

 

 

언뜻 보기에 삽입정렬이 가장 느리거나, 버블정렬과 비슷한 정도로 느릴 것이라고 생각할 수 있다.

하지만 여기서 또 생각할 점이 생긴다.

빅오로 나타내는 경우는 대게 최악의 경우를 가정한다 (주어지는 배열이 역순으로 정렬되어 있다던지 하는 이유로 루프를 많이 타는 경우?)

하지만 삽입정렬은 이미 정렬이 많이 되어있는 배열이 주어질 경우 많은 단계가 생략되게 된다.

가령, 비교하는 과정에서 현재 값보다 작은 경우를 바로 만난다면 이하 과정들이 다 생략되고 1로 돌아간다던지.. 하는 식으로

실제 수행되는 단계가 줄어들 수 있는 여지가 있다.

실제로 삽입정렬의 효율성을 계산해보면 평균적으로 N^2/2 단계 정도가 걸리기도 하고, 심지어 이미 정렬된 배열이 주어지면 O(N)을 갖기도 한다.

다른 정렬의 경우 정렬된 배열이 주어지더라도 똑같은 단계들을 거쳐야 한다.

따라서 어떤 데이터를 다루냐에 따라 삽입정렬이 빠를 수 있다는 것이다.

 

 

결론은..

알고리즘의 효율성을 분석하기 위해 빅오를 이용하는 것이 맞지만,

같은 빅오 내에서 실제 효율성은 다를 수 있기 때문에 여러 가지를 고려해서 알고리즘을 선택할 수 있다는 것이다