5. 버블정렬, 선택정렬

p. 99~112(5일차)

강의:  04-1, 04-2

---

1. 버블정렬

- 데이터 인접 요소끼리 비교하고, swap 연산을 수행하여 정렬하는 방식 

- 만약 특정한 루프의 전체 영역에서 swap이 한 번도 발생하지 않으면? 

     => 영역 뒤에 있는 데이터가 모두 정렬됐다는 뜻 ! 프로세스 종료 가능

* 정렬된 영역은 빼고 루프 실행

 

✔ 핵심 이론

- 인접한 데이터의 크기를 비교해 정렬하는 방식

- 시간 복잡도는  O(n²)

- 정렬 알고리즘보다 속도는 느린 편

- 인접한 데이터 간의  swap 연산으로 정렬

 

✔백준 2750번 - 수 정렬

✔ 배열 A의 값보다 1칸 오른쪽의 값이 더 작으면 두 수 바꾸기 (반복)

 

 

---

2. 선택정렬 *테스트 빈도가 높지는 않음, 구조만 이해하기

 

- 최대나 최소 데이터를 나열된 순으로 찾아가며 선택하는 방법

- 구현방법이 복잡하고 시간복잡도도 효율적이진 않음

 

✔ 핵심 이론

- 최솟값 또는 최대값을 찾는다

- 남은 정렬 부분의 가장 앞에 있는 데이터와 swap하는 것이다.