boostcource
모두를 위한 컴퓨터 과학 (CS50 2019) : David J. Malan
www.boostcourse.org/cs11
실습환경 : CS50 Sandbox & CS50 IDE
정렬되지 않은 리스트를 탐색하는 것보다는 정렬한 뒤에 탐색하는 것이 더 효율적이며
이 정렬 방법들에 대해서 알아보자.
버블 정렬
버블 정렬이란 두 개의 인접한 자료 값을 비교하면서 위치를 교환하는 방식으로 정렬하는 방법이다.
단 두개의 요소만 정렬해주는, 좁은 범위의 정렬에 집중한다.
때문에 간단하지만 너무 많은 교환이 일어나는 낭비가 발생할 수도 있다.
만일 1부터 8까지의 숫자로 구성된
[6, 3, 8, 5, 2, 7, 4, 1] 이라는 임의의 배열이 존재하고
이를 오름차순으로 정렬하려고 한다.
왼쪽부터 두개의 요소를 선택해 둘의 크기를 비교한 뒤
값이 더 큰 요소가 오른쪽에 위치하도록 값을 서로 변경해주고 다음 요소로 넘어가는 절차를 밟는다.
처음 한 바퀴를 돌고나면 위와 같이 [3, 6, 5, 2, 7, 4, 1, 8] 로 순서가 변경된다.
아직은 완전한 오름차순이 되지 않았기 때문에 다시 한 번 과정을 반복한다.
두 바퀴째에서 만들어진 배열은 [3, 5, 2, 6, 4, 1, 7, 8] 이다.
이렇게 완전한 오름차순이 될 때까지 반복하면
최종적으로 아래의 [1, 2, 3, 4, 5, 6, 7, 8] 에 도달한다.
이 과정은 의사코드로 아래와 같이 나타낼 수 있으며
Repeat n–1 times (n-1번 반복)
For i from 0 to n–2 (i부터 n-2까지 반복)
If i'th and i+1'th elements out of order (i요소와 i+1요소의 순서가 잘못됐다면)
Swap them (서로 교환)
n개의 값이 주어졌을 때 각 루프가 각각 n-1번, n-2번 반복되기 때문에
(n−1)∗(n−2)=n2−3n+2 번의 비교와 교환이 필요하고
실행 시간의 상한은 O(n^2) 이고,하한도 정렬 여부와 관계없이 루프를 돌아야 하기 때문에 동일하게 Ω(n^2) 이다.
하지만 만일 정렬이 모두 되어 있는 숫자 리스트가 주어진다면?
바깥쪽 루프를 "교환이 일어나지 않을 때" 까지만 수행하도록 의사코드를 수정할 수 있다.
Repeat until no swaps (교환이 일어나지 않을 때까지 반복)
For i from 0 to n–2 (i부터 n-2까지 반복)
If i'th and i+1'th elements out of order (i요소와 i+1요소의 순서가 잘못됐다면)
Swap them (서로 교환)
이렇게 하면 최종적인 버블 정렬의 하한은 Ω(n) 이 된다.
특정 정보를 찾는 경우가 빈번하게 일어나는 프로그램이라면
버블 정렬을 해서 이진탐색이 가능하게 하는 것이 유리하고 (이진탐색의 상한 O(log n) < 선형탐색의 상한 O(n))
그렇지 않으면 굳이 버블 정렬을 할 필요는 없다고 판단할 수 있다.
선택 정렬
선택 정렬이란 배열 안의 자료 중 가장 작은 수(혹은 가장 큰 수)를 찾아
첫 번째 위치(혹은 가장 마지막 위치)의 수와 교환해주는 방식의 정렬이다.
교환 횟수를 최소화하는 반면, 각 자료를 비교하는 횟수는 증가한다.
버블 정렬에서 했던 것과 같이
1부터 8까지의 숫자로 구성된 [6, 3, 8, 5, 2, 7, 4, 1] 이라는 임의의 배열이 존재하고
이를 오름차순으로 정렬하려고 한다.
배열의 모든 요소 중 가장 작은 값을 찾아 리스트의 가장 앞 자리인 첫 번째 값과 교환한다.
그리고 다음으로 작은 값을 찾아, 정렬되지 않은 남은 숫자들 중 가장 앞인 리스트의 두 번째 값과 교환한다.
더 이상 교환이 일어날 때까지 이를 반복하면
최종적으로 [1, 2, 3, 4, 5, 6, 7, 8] 에 도달해 오름차순 정렬이 완성된다.
이 과정은 의사코드로 아래와 같이 나타낼 수 있으며
For i from 0 to n–1 (0부터 n-1까지 반복)
Find smallest item between i'th item and last item (i번째~끝 요소 중 가장 작은 요소 검색)
Swap smallest item with i'th item (i번째 요소와 교환)
n개의 값이 주어졌을 때 두 번의 루프가 돌기 때문에
실행 시간의 상한은 O(n^2), 하한도 Ω(n^2)가 된다.
선택 정렬을 조금 더 효율적으로 사용하기 위한 방법을 찾아보자면
안쪽 루프에서 최소값만 탐색하는 것이 아닌 최대값을 동시에 탐색해
배열의 양 끝에 두 값을 두는 이중 선택 정렬 등의 답안을 제안해볼 수 있을 것이다.
복습 퀴즈
Q1. 5 6 7 3 2 과 같은 숫자 리스트가 주어졌다. 오름차순 정렬을 위해 버블 정렬을 왼쪽 처음부터 오른쪽 끝까지 '한 번' 수행했을 때의 리스트는?
답: 5 6 3 2 7
버블 정렬은 인접한 두 개의 요소의 크기를 비교하며 교체하는 정렬 방법이다.
5 6 7 3 2 의 경우 한 번 수행 시, "5 6 7 3 2 -> 5 6 3 7 2 -> 5 6 3 2 7" 순으로 변화한다.
Q2. 5 6 7 3 2 과 같은 숫자 리스트가 주어졌다. 오름차순 정렬을 위해 선택 정렬을 통해 교환을 '한 번' 수행했을 때의 리스트는?
답: 2 6 7 3 5
선택 정렬은 가장 작은 값을 찾아 맨 앞에 놓여있는 값과 교체하는 정렬 방법이다.
5 6 7 3 2 의 경우 한 번 수행 시, "5 6 7 3 2 -> 2 6 7 3 5" 로 변화한다.
'CS > CS50' 카테고리의 다른 글
[CS][CS50] 메모리 - 메모리 주소 / 포인터 (1) | 2023.06.18 |
---|---|
[CS][CS50] 알고리즘 - 재귀 / 병합 정렬 / 정렬 알고리즘의 실행시간 (0) | 2023.06.18 |
[CS][CS50] 알고리즘 - 검색 알고리즘 / 알고리즘 표기법 / 선형 검색 (0) | 2023.06.10 |
[CS][CS50] 배열 - 명령행 인자 (1) | 2023.06.09 |
[CS][CS50] 배열 - 문자열과 배열 / 문자열의 활용 (0) | 2023.06.08 |