버블정렬.md

버블 정렬

문제

원소 n개로 이루어진 정렬되지 않은 배열이 주어졌을 때, 배열을 정렬하는 함수를 작성하라

접근방식

• 배열의 첫 번째 원소를 선택한다.
• 다음 원소와 비교한다.
• 다음 원소보다 크다면 교환한다.
• 아니라면 아무것도 하지 않는다.
• 배열의 모든 인덱스에 이 작업을 진행한다.
• 위의 과정을 n번 반복한다.

시간 복잡도

O(n^2) 최악의 경우

O(n) 최선의 경우

O(n^2) 평균 복잡도

공간 복잡도

O(1) 최악의 경우

만든 사람

• “Bubble Sort”라는 용어는 1962년 Iverson, K에 의해 처음 사용되었다.

예시

배열 = {10, 80, 40, 30}
인덱스들: 0   1   2   3

1. 인덱스 = 0, 숫자 = 10
2. 10 < 80, 아무것도 하지 않고 다음 단계로 넘어간다.

3. 인덱스 = 1, 숫자 = 80
4. 80 > 40, 80과 40을 교환한다.
5. 현재 배열은 {10, 40, 80, 30}

6. 인덱스 = 2, 숫자 = 80
7. 80 > 30, 80과 30을 교환한다.
8. 현재 배열은 {10, 40, 30, 80}

위 단계를 다시 반복한다.

배열 = {10, 40, 30, 80}
인덱스들: 0   1   2   3

1. 인덱스 = 0, 숫자 = 10
2. 10 < 40, 아무것도 하지 않고 다음 단계로 넘어간다.

3. 인덱스 = 1, 숫자 = 40
4. 40 > 30, 40과 30을 교환한다.
5. 현재 배열은 {10, 30, 40, 80}

6. 인덱스 = 2, 숫자 = 40
7. 40 < 80, 아무것도 하지 않는다.
8. 현재 배열은 {10, 30, 40, 80}

위 단계를 다시 반복한다.

배열 = {10, 30, 40, 80}
인덱스들: 0   1   2   3

1. 인덱스 = 0, 숫자 = 10
2. 10 < 30, 아무것도 하지 않고 다음 단계로 넘어간다.

3. 인덱스 = 1, 숫자 = 30
4. 30 < 40, 아무것도 하지 않고 다음 단계로 넘어간다.

5. 인덱스 = 2, 숫자 = 40
6. 40 < 80, 아무것도 하지 않는다.

위 단계에서 교환이 없기 때문에 배열이 정렬되었음을 의미하고, 여기서 멈출 수 있다.

코드 구현

• 자바
• C++
• 파이썬
• C#
• 고
• 루비
• C
• 스칼라
• 자바스크립트

영상 설명

버블정렬 알고리즘에 대한 영상 설명

그 외

버블 정렬은 싱킹 정렬이라고도 한다.

애니메이션 설명

• 튜트 보드