지난 주에는 면접과 취업 코칭 등 (+ 정처기 필기 공부 시작) 다양한 이슈로 인해 블로그 포스팅을 건너뛰게 되었다. ^_ㅠ 다시 블로그를 꾸준히 하자고 다짐하며 쓰는 5월의 첫 번째 글은 바로 정렬 알고리즘이다. 이번 달은 기본적인 정렬 알고리즘들을 공부해보려고 한다.
버블 정렬 구현 & 최적화하기
버블 정렬이란
서로 인접한 데이터의 크기를 비교해서 더 작은 값을 왼쪽에, 더 큰 값을 오른쪽에 정렬하는 알고리즘이다.
버블 정렬 구현하기 (JavaScript)
기본 코드
이 아이디어를 자바스크립트로 구현하면 다음과 같다.
function bubbleSort(arr) {
// 전체 반복 횟수는 배열의 길이 만큼 반복
for (let i = 0; i < arr.length; i++){
// 1회당 전체 배열의 요소를 모두 검사
for (let j = 0; j < arr.length; j++){
// j번째 요소가 j + 1번째 요소보다 크다면 위치를 서로 바꿈
if (arr[j] > arr[j + 1]) {
let temp = arr[j]
arr[j] = arr[j + 1]
arr[j + 1] = temp
}
}
}
return arr
}기본 코드의 문제점
가장 기본적인 형태로 구현했으니 이제 최적화해보자.
우선 해당 코드가 어떤 식으로 값을 정렬하는지 console.log 코드를 내부에 추가해서 확인해보면 결과가 다음과 같이 나온다.
function bubbleSort(arr) {
for (let i = 0; i < arr.length; i++){
for (let j = 0; j < arr.length; j++){
console.log(arr, arr[j], arr[j + 1] // 값 출력용
if (arr[j] > arr[j + 1]) {
let temp = arr[j]
arr[j] = arr[j + 1]
arr[j + 1] = temp
}
}
}
return arr
}콘솔로 정렬 과정을 확인해본 결과 이 코드에는 두 가지 문제점이 있다.
[ 1, 4, 7, 2, 3, 10 ] 1 4
[ 1, 4, 7, 2, 3, 10 ] 4 7
[ 1, 4, 7, 2, 3, 10 ] 7 2
[ 1, 4, 2, 7, 3, 10 ] 7 3
[ 1, 4, 2, 3, 7, 10 ] 7 10
[ 1, 4, 2, 3, 7, 10 ] 10 undefined
[ 1, 4, 2, 3, 7, 10 ] 1 4
[ 1, 4, 2, 3, 7, 10 ] 4 2
[ 1, 2, 4, 3, 7, 10 ] 4 3
[ 1, 2, 3, 4, 7, 10 ] 4 7
[ 1, 2, 3, 4, 7, 10 ] 7 10
[ 1, 2, 3, 4, 7, 10 ] 10 undefined
[ 1, 2, 3, 4, 7, 10 ] 1 2
[ 1, 2, 3, 4, 7, 10 ] 2 3
[ 1, 2, 3, 4, 7, 10 ] 3 4
[ 1, 2, 3, 4, 7, 10 ] 4 7
[ 1, 2, 3, 4, 7, 10 ] 7 10
[ 1, 2, 3, 4, 7, 10 ] 10 undefined
[ 1, 2, 3, 4, 7, 10 ] 1 2
[ 1, 2, 3, 4, 7, 10 ] 2 3
[ 1, 2, 3, 4, 7, 10 ] 3 4
[ 1, 2, 3, 4, 7, 10 ] 4 7
[ 1, 2, 3, 4, 7, 10 ] 7 10
[ 1, 2, 3, 4, 7, 10 ] 10 undefined
[ 1, 2, 3, 4, 7, 10 ] 1 2
[ 1, 2, 3, 4, 7, 10 ] 2 3
[ 1, 2, 3, 4, 7, 10 ] 3 4
[ 1, 2, 3, 4, 7, 10 ] 4 7
[ 1, 2, 3, 4, 7, 10 ] 7 10
[ 1, 2, 3, 4, 7, 10 ] 10 undefined
[ 1, 2, 3, 4, 7, 10 ] 1 2
[ 1, 2, 3, 4, 7, 10 ] 2 3
[ 1, 2, 3, 4, 7, 10 ] 3 4
[ 1, 2, 3, 4, 7, 10 ] 4 7
[ 1, 2, 3, 4, 7, 10 ] 7 10
[ 1, 2, 3, 4, 7, 10 ] 10 undefined
[ 1, 2, 3, 4, 7, 10 ]
- 버블 정렬의 특성상 턴이 끌날 때마다 마지막 요소들에는 가장 큰 수가 온다. 따라서 매번 요소 끝까지 정렬할 필요가 없는 데도 정렬하고 있다.
- 이미 정렬된 요소들도 다시 비교한다. (ex. 가장 첫 번째 요소와 두 번째 요소인 1, 4를 매 회마다 반복함)
문제 1 개선: 반복 횟수 줄이기
먼저, 1번 문제를 해결하기 위해서는 1턴 비교가 끝나고 나면 그 다음 턴에서는 그 전보다 횟수를 1회씩 더 줄이며 비교를 해야 한다.
이는 반복문의 변수인 i와 j를 수정해서 개선할 수 있다.
function bubbleSort(arr) {
for (let i = arr.length; i > 0; i--){
for (let j = 0; j < i - 1; j++){
console.log(arr, arr[j], arr[j+1])
if (arr[j] > arr[j + 1]) {
let temp = arr[j]
arr[j] = arr[j + 1]
arr[j + 1] = temp
}
}
}
return arr
}i를 배열의 길이로부터 시작해서 1씩 줄이는 코드로 변경한다.
이렇게 하면 j의 최대값을 i - 1 미만으로 수정해서 i가 반복될 때마다 j의 반복 횟수를 1씩 더 줄일 수 있다. 수정된 코드로 i와 j의 값을 대입해보면 다음과 같다.
i = 6일 때, j = 0, 1, 2, 3, 4
i = 5일 때, j = 0, 1, 2, 3
i = 4일 때, j = 0, 1, 2
i = 3일 때, j = 0, 1
i = 2일 때, j = 0이런 식으로 반복하여 총 15번 반복하게 된다.
실제로 콘솔에 출력해보면 다음과 같이 나타난다.
[ 1, 4, 7, 2, 3, 10 ] 1 4
[ 1, 4, 7, 2, 3, 10 ] 4 7
[ 1, 4, 7, 2, 3, 10 ] 7 2
[ 1, 4, 2, 7, 3, 10 ] 7 3
[ 1, 4, 2, 3, 7, 10 ] 7 10
[ 1, 4, 2, 3, 7, 10 ] 1 4
[ 1, 4, 2, 3, 7, 10 ] 4 2
[ 1, 2, 4, 3, 7, 10 ] 4 3
[ 1, 2, 3, 4, 7, 10 ] 4 7
[ 1, 2, 3, 4, 7, 10 ] 1 2
[ 1, 2, 3, 4, 7, 10 ] 2 3
[ 1, 2, 3, 4, 7, 10 ] 3 4
[ 1, 2, 3, 4, 7, 10 ] 1 2
[ 1, 2, 3, 4, 7, 10 ] 2 3
[ 1, 2, 3, 4, 7, 10 ] 1 2
[ 1, 2, 3, 4, 7, 10 ] // 최종 정렬된 결과문제 2 개선: 이미 정렬된 요소 다시 비교하지 않기
그럼 2번 문제인 이미 정렬된 요소를 다시 비교하지 않으려면 어떻게 해야 할까?
오름차순으로 정렬이 완료됐다면 더는 정렬을 수행하지 말아야 한다.
정렬이 완료되었는지 판단하는 변수를 bool 값으로 할당해서 개선할 수 있다.
function bubbleSort(arr) {
for (let i = arr.length; i > 0; i--){
let noSwaps;
for (let j = 0; j < i - 1; j++){
noSwaps = true;
console.log(arr, arr[j], arr[j+1])
if (arr[j] > arr[j + 1]) {
let temp = arr[j]
arr[j] = arr[j + 1]
arr[j + 1] = temp
noSwaps = false
}
}
if (noSwaps) break
}
return arr
}noSwaps라는 변수를 선언한다.
외부 반복문에서는 noSwaps = true로 할당한 후, 내부 반복문에서 정렬이 일어나면 false로 값을 할당한다.
만약 정렬이 완료되었다면 noSwaps = true로 할당된 후 반복문을 빠져나가고, if (noSwaps) 문으로 처리되어 반복문이 break 된다.
참고 자료
JavaScript 알고리즘 & 자료구조 마스터클래스 (유데미 강의)
