/* 본 게시물은 ' 뇌를 자극하는 알고리즘 | with 박성현 ' 의 내용을 토대로 작성되었습니다. */
참고 자료
[BoostCourse - CS50 - 버블 정렬 / 선택 정렬] : https://www.boostcourse.org/cs112
이번에 공부할 내용은 데이터를 일련의 명령이나 반복되는 절차에 의해 정렬을 수행하는 정렬 알고리즘이다. 우리는 그중 버블 정렬, 선택 정렬, 삽입 정렬, 퀵 정렬에 대해 알아보겠다. 각 알고리즘의 구조와 성능을 중점적으로 비교해가며 공부해보자.
'왜 우리는 데이터들을 정렬해야될까?'
위 질문에 대한 답은 앞서 검색 알고리즘을 배우면서 알아보았다. 우리가 데이터를 정렬하는 이유는 정렬을 하면 데이터를 빠르게 찾을 수 있기 때문이다! 단, 데이터를 정렬하는 작업도 시간이 많이 걸리는 작업이므로 데이터를 여러번 검색할 경우에 정렬을 해주는 것이 효율적이다.
1. 버블 정렬
버블 정렬은 두 개의 인접한 자료 값을 비교하면서 위치를 교환하는 방식으로 정렬하는 방법을 말한다.
(cf> 버블 정렬은 알고리즘이 데이터를 정렬하는 과정이 마치 물 속 깊은 곳에서 일어난 거품이 수면을 향해 올라오는 모습과 같다고 해서 붙여졌다.)
위 사진을 보면 이해가 될 것이다. 이 예시에서는 오른쪽부터 값을 비교한다. 만약 왼쪽 값이 오른쪽 값보다 크다면 둘의 자리를 바꿔준다. 이 과정을 반복하다보면 왼쪽 끝에는 제일 작은 값(1)이 오게 될 것이다. 그 다음 시행에서는 제일 작은 값을 구했기 때문에 제일 작은 값을 제외한 부분만 다시 과정을 시행한다. 이렇게 하면 두 번째로 작은 값이 올 것이다.
버블 정렬 예시
object SortAlgorithm {
fun bubbleSort(arr : Array<Int>) : Array<Int>{
var temp: Int = 0
// n-1 번 시행
for (i in arr.indices){
// i 회차 때 바꾸는 횟수 ex) 1회 차 때 n - 1, 2회 차 때 n-2
for (j in 1 until arr.size - i){
// 만약 오른쪽 값이 왼쪽 값보다 작을 경우
if (arr[j] < arr[j-1]){
//교환
temp = arr[j]
arr[j] = arr[j-1]
arr[j - 1] = temp
}
}
}
return arr
}
}
@ExperimentalTime
fun main(){
// [10,9,...,1]
var array: Array<Int> = Array<Int>(10){ i -> i + 1 }.reversedArray()
val sortedArray = SortAlgorithm.bubbleSort(array)
sortedArray.forEach {
print(it)
print(",")
}
}실행 결과
버블 정렬 성능
이제 교환 횟수에 집중하자. 첫 번째로 작은 값을 찾는 횟수는 7번, 그 다음은 6번, 5번.. 1번 이 될 것이다. 즉 전체 교환횟수로는 1+2+...+n-1 즉, n(n-1)/2 이 될 것이다.
만약 데이터(n)의 값이 커지면 교환횟수는 어떻게 될까? 예시로 n의 값이 10000이라 할 때, 전체 시행 횟수는 49,995,000이다! 결국 버블 정렬의 단점은 정렬이 되어 있는지 여부에 관계 없이 루프를 돌며 비교를 해야한다. 이를 통해 버블 정렬이 '왜' 비효율적인 지 알 수 있다.
@ExperimentalTime
fun main(){
// [100000,99999...,1]
var array: Array<Int> = Array<Int>(10000){ i -> i + 1 }.reversedArray()
//bubblesort measureTime
val measuredTime = measureTimedValue {
SortAlgorithm.bubbleSort(array)
}
println("measured time ==>${measuredTime.duration}")
}
cf> 버블 정렬 개선
버블 정렬은 미리 정렬되어 있어도 모든 루프를 돌며 비교를 수행하는 미련한 알고리즘이다. 정렬되어 있는 경우에는 루프를 취소하고 빠져나오도록 알고리즘을 개선시켜 성능을 높일 수 있다...
2. 선택 정렬
선택정렬은 배열 안의 자료 중 가장 작은(혹은 가장 큰 수)를 찾아 첫 번째 위치(혹은 가장 마지막 위치)의 수와 교환해주는 방식의 정렬이다. 선택 정렬은 교환 횟수를 최소화하는 반면 각 자료를 비교하는 횟수는 증가한다.
위의 예시에서는 숫자를 비교하여 가장 작은 값을 맨 왼쪽 값과 교환한다.
선택 정렬 예시
fun selectSort(arr: Array<Int>) : Array<Int>{
var temp: Int = 0
// 작은 값의 index 를 담을 변수이다
var tempIndex: Int = 0
var lastIndex: Int = 0
// n-1 번 실행
for (i in arr.indices){
temp = arr[i]
tempIndex = i
// 비교
for (j in 1 until arr.size - i){
// temp 에 저장된 값보다 작은 경우
if (temp > arr[j + i]) {
//temp, tempIndex 에 최솟값 및 최솟값 index 값 저장
temp = arr[j + i]
tempIndex = j + i
}
}
// 최솟값과 arr[i] 교환
// 최솟값 위치에 arr[i] 값 대입
arr[tempIndex] = arr[i]
// arr[i] 자리에 temp 값 대입
arr[i] = temp
}
return arr
}위 예시는 최솟값을 맨 왼쪽부터 정렬하는 코드이다.
선택 정렬 성능
버블 정렬과 동일한 조건으로 실행한 결과이다.
버블 정렬보다 높은 성능을 보여준다. 그 이유를 생각해보면 버블 정렬은 n*(n-1)/2 만큼 교환이고, 선택 정렬은 비교하는 작업 후 값이 조건에 따라 작거나 클 때만 교환한다. 교환하는 작업은 비교하는 작업보다 오래 걸리기 때문에 버블 정렬 성능이 더 낮게 측정되었다.
1일 1알고리즘 - 버블 정렬 / 선택 정렬
