공hannah부
정렬 (버블정렬, 삽입정렬, 퀵정렬, 병합정렬) 본문
버블정렬
- 인접한 두 원소를 순서대로 보면서 정렬해 나가는 알고리즘
- 오름차순 예시
- A[i]와 A[i+1]을 비교할 때
- A[i] > A[i+1] 이면 A[i]와 A[i+1]를 교환(swap)한다.
- 위 과정을 i=1~N-1까지 순서대로 한번 수행 하는 것을 순회라고 한다. (N은 배열의 길이)
- 버블 정렬은 순회를 N-1번 반복한다.
- ex) [4, 5, 2, 3, 1]
- i=1) [4, 5, 2, 3, 1]
- i=2) [4, 2, 5, 3, 1]
- i=3) [4, 2, 3, 5, 1]
- i=4) [4, 2, 3, 1, 5]
- 첫 번째 과정을 수행하면 가장 큰 수 5가 맨 뒤에 위치
- i=1) [2, 4, 3, 1, 5]
- i=2) [2, 3, 4, 1, 5]
- i=3) [2, 3, 1, 4, 5]
- 두 번째 과정을 수행하면 두번째로 큰 수 4가 맨 뒤에서 두번째에 위치
- i=1) [2, 3, 1, 4, 5]
- i=2) [2, 1, 3, 4, 5]
- 세 번째 과정을 수행하면 세번째로 큰 수 3이 맨 뒤에서 세번째에 위치
- i=1) [1, 2, 3, 4, 5]
- 정렬 끝.
- 시간 복잡도
- 길이가 N인 배열을 한 번 순회할 때
- 비교 N-1번(최대)
- 교환 N-1번(최대)
- i번째 순회에서 i번째로 큰 값이 뒤에서 i번째 위치로 이동
- 순회를 N-1번 반복하면 모든 수가 올바른 위치로 이동
- 즉, (N-1)^2번 연산을 수행하므로 O(N^2)
삽입정렬
- 적절한 위치에 원소를 삽입함으로써 정렬해 나가는 알고리즘
- i=2~N인 i에 대해서 순서대로 다음 과정을 수행
- i번째 작업: A[i]를 부분 배열 [1,i]가 정렬된 상태가 되도록 적절한 위치에 삽입
- ex) [4, 5, 2, 3, 1]
- i=2) [4, 5, 2, 3, 1]
- i=3) [2, 4, 5, 3, 1]
- i=4) [2, 3, 4, 5, 1]
- i=5) [1, 2, 3, 4, 5]
- i번째 과정을 수행하면 부분배열 [1,i]가 정렬된 상태
- 시간 복잡도
- best: O(N)
- worst: O(N^2)
- average: O(N^2)
퀵정렬
- 배열이 주어지면 다음 작업을 수행하는 함수 sort를 정의
- sort(int A[])
- 배열 A의 길이가 0또는 1이면, 이미 정렬된 배열이므로 함수 종료
- 배열A에 있는 아무 원소를 pivot으로 잡은 후, pivot보다 작은 원소를 pivot의 왼쪽으로 옮기고 pivot보다 큰 원소를 pivot의 오른쪽으로 옮긴다.
- pivot을 기준으로 왼쪽에 있는 배열에 대해 다시 sort 호출.(왼쪽 배열을 다시 정렬)
- pivot을 기준으로 오른쪽에 있는 배열에 대해 다시 sort 호출.(오른쪽 배열 다시 정렬)
- ex) [4, 5, 2, 3, 1]
- [4, 5, 2, 3, 1] //4를 pivot으로 설정
- [2, 3, 1, 4, 5]
- [2, 3, 1] //왼쪽배열 다시 정렬, 2를 pivot으로 설정
- [1, 2, 3]
- [1, 2, 3, 4, 5]
- 정렬 끝.
- 시간 복잡도
- best / average: O(NlogN) //매번 고르는 pivot이 왼쪽과 오른쪽 배열을 정확히 절반씩 나누는 경우
- worst: O(N^2) //매번 고르는 pivot이 불균형하게 나누는 경우
병합 정렬
- 배열이 주어지면 다음 작업을 수행하는 함수 sort를 정의
- sort(int A[])
- 배열 A의 길이가 0또는 1이면, 이미 정렬된 배열이므로 함수 종료
- 배열 A를 다음 두 배열로 나눔
- 왼쪽 절반을 L, 오른쪽 절반을 R이라고 하면,
- sort(L)을 호출 (왼쪽 배열을 정렬)
- sort(R)을 호출 (오른쪽 배열을 정렬)
- 정렬된 두 배열 L과 R을 합쳐서 정렬된 배열 A를 반환
- ex) [4, 5, 2, 3, 1]
- 배열을 나누는 과정
- [4, 5, 2, 3, 1]
- [4, 5, 2] [3, 1]
- [4, 5] [2] [3] [1]
- [4] [5]
- 배열을 합치는 과정
- [4, 5]
- [2, 4, 5] [1, 3]
- [1, 2, 3, 4, 5]
- 각 배열의 앞 숫자 비교해서 합치기
- 배열을 나누는 과정
- 시간 복잡도
- best / average / worst : O(NlogN) //퀵 정렬의 best 경우와 동일
'공부 > 알고리즘' 카테고리의 다른 글
거듭제곱 (0) | 2023.08.03 |
---|---|
최대공약수(gcd)와 최소공배수(lcm) / 유클리드 호제법 (0) | 2023.08.03 |
선형 자료 구조 (배열, 연결 리스트, 스택, 큐, 덱) (0) | 2023.07.31 |
비교 함수 / STL sort (0) | 2023.07.31 |
C++기초, C++ STL (0) | 2023.07.25 |