인프런 커뮤니티 질문&답변
작성한 질문수
버블정렬
작성
·
22
0
function bubbleSort(array) {
const n = array.length
for (let i=0; i<n; i++){
for (let j=0; j<n; j++) {
if (array[j] > array[j+1]) {
[array[j], array[j+1]] = [array[j+1], array[j]]
}
}
}
return array
}
console.log(bubbleSort([77, 42, 6, 4, 3, 5, 1, 35, 222]))수업에서 사용하신 코드인데 버블정렬의 브레이크 포인트와 이미 정렬된 뒷 부분까지 비교할 필요가 없지 않나요? 저렇게 사용하신 다른 이유가 있으신 지 여쭤보고 싶습니다!
function bubbleSort(array) {
const n = array.length
for (let i=0; i<n-1; i++){
let swapped = false;
for (let j=0; j<n- i; j++) {
if (array[j] > array[j+1]) {
[array[j], array[j+1]] = [array[j+1], array[j]]
swapped = true;
}
}
if (!swapped) break;
}
return array
}
console.log(bubbleSort([77, 42, 6, 4, 3, 5, 1, 35, 222]))답변 1
0
안녕하세요, 인프런 AI 인턴입니다. 이민재님.
버블 정렬은 간단하면서도 기본적인 정렬 알고리즘 중 하나입니다. 위에 질문해주신 내용과 관련하여, 버블 정렬의 효율성을 높이기 위한 몇 가지 최적화 방안에 대해 설명 드릴게요.
기존 버블 정렬의 문제점
버블 정렬은 기본적으로 매번 모든 요소를 비교하므로 최악의 경우 (O(n^2))의 시간복잡도를 가집니다. 특별한 최적화가 없으면, 정렬된 배열에서도 불필요한 비교가 계속될 수 있습니다.
제안한 최적화 요점
스왑 여부 체크:
swapped변수를 사용하여 각 패스에서 요소들이 교환되었는지를 확인합니다. 만약 교환되지 않았다면 배열이 이미 정렬되어 있으므로 반복을 멈출 수 있어 보다 효율적입니다.순회 범위 축소: 각 패스 후 가장 큰 요소가 올바른 위치를 찾게 되므로, 내부 루프는 마지막 요소까지 갈 필요가 없습니다. 내부 루프의 종료 조건을
n-i로 설정하여 이미 정렬된 뒤의 요소들은 비교하지 않습니다.
관련 질문 링크
이와 관련된 버블 정렬의 효율성과 최적화에 대한 과정 및 분석을 더 알고 싶다면, 다음 링크를 참고해 보세요:
- 버블 정렬 알고리즘의 작동 원리와 최적화에 대한 질문
이 설명이 도움이 되셨길 바랍니다. 추가적으로 궁금한 점이 있으시면 언제든지 질문해 주세요.
저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.