'sort' 태그의 글 목록

서로 인접한 두 원소의 대소를 비교하고, 조건에 맞지 않다면 자리를 교환하며 정렬하는 알고리즘. 가장 큰 값을 배열의 맨 끝에 이동시키면서 정렬하고자 하는 원소의 개수 만큼을 두 번 반복하게 된다. 정렬 과정에서 원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 Bubble Sort라 지어졌다고 한다. 구현 시간 복잡도 (n - 1) + (n - 2) + ... + 2 + 1 = n(n-1)/2이므로 O(n^2) 정렬이 되어있든지 안되어있든지 2개의 원소를 비교하기 때문에 최선, 평균, 최악의 경우 모두 시간 복잡도가 O(n^2)으로 동일하다. 공간 복잡도 주어진 배열 안에서 교환(swap)을 통해 정렬이 수행되므로 O(n) 장점 구현이 매우 간단하고 소스코드가 직관적이다. 추가적인 메모..

Algorithm 2021. 10. 18. 20:14

이전 1 다음