1. 선택 정렬 (Selection Sort)
정렬 되지 않은 데이터들에 대해 가장 작은 데이터를 찾아 가장 앞의 데이터와 교환해 나가는 방식이다.
과정)
- 주어진 리스트 중 최소 값을 찾는다. (전체를 순회하여 최소 값을 찾는다.)
- 그 값을 맨 앞에 위치한 값과 교체한다.
- 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다.
예)
[7,8,9,3,6]
라는 배열이 있을 때
왼쪽에서 부터 전체 순회하여 최소 값 3을 찾고, 3은 제일 처음과 교체한다. 그러면 아래와 같은 사진이 될 것이다.
[3,8,9,7,6]
계속 과정을 이어가보면
[3,6,9,7,8] -> [3,6,7,9,8] -> [3,6,7,8,9] 이렇게 정렬이 될 것이다.
시간복잡도로는 n개의 데이터 갯수가 있을 때 2번의 for 루프로 정렬시키기 때문에 O(n^2) 이 된다. 최선으로 정렬 하게 되었을 때는 O(n) 이다.
2. 삽입 정렬 (Insertion Sort)
배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여 자신의 위치를 찾아 삽입함으로 정렬을 하는 알고리즘이다.
과정)
- 삽입정렬은 2번째 요소부터 시작하여 앞쪽과 비교하여 위치를 지정한다.
- 해당 Index 앞쪽의 모든 원소와 비교하면서 자리를 이동하며 비교하였을 때 맞는 위치에 해당 원소를 교체한다.
예)
[7,8,9,3,6]
라는 배열이 있을 때
8부터 시작하면
[7,8,9,3,6]
그대로 일 것이다. 그리고나서 9를 검사한다.
[7,8,9,3,6]
그래도 일 것이다. 그리고나서 3을 검사한다.
[3,7,8,9,6]
으로 교체된다.
(좀 더 부연 설명을 하면 3은 먼저 앞쪽에 있는 9랑 비교하며 9보다 낮기 때문에 9를 뒤로 미뤄주며 다시 8이랑 비교하며 8보다 낮기 때문에 8을 뒤로 미뤄주면서 그렇게 7까지 비교하면서 3은 제일 앞자리로 오게 되고 7,8,9는 한자리씩 밀리게 된다.)
[3,6,7,8,9]
6이 3을 제외한 맨 앞으로 오고 7,8,9까지 다 돌면 정렬을 완성된다.
시간복잡도로는 최악으로 O(n^2) 이며 최적일 때는 O(n)이 된다.
3. 버블 정렬 (Bubble Sort)
서로 인접한 두 원소를 검사하여 정렬하는 알고리즘 이다.
과정)
- 인접한 두 원소를 비교하여 크기가 순서대로 되어 있지 않으면 서로 교체한다.
예)
[7,4,5,1,3]
라는 배열이 있다.
1회전에는 [4,5,1,3,7] 의 결과가 나온다.
7,4를 비교하여 교체, [4,7,5,1,3] 에서 7,5를 비교하여 교체 이렇게 순회하며 결국 1회전에는 7은 맨뒤로 가게 된다.
2회전에는 [4,1,3,5,7] 의 결과가 나온다.
[4,5,1,3,7] 이라는 배열에서 4,5를 비교하지만 4가 낮기에 교체를 안하며 5,1를 비교 후 교체 5,3을 비교하여 교체 해서 7을 제외한 원소를 비교하여 교체해서 5는 7앞에 놓일 것이다.
3회전에는 [1,3,4,5,7] 의 결과가 나온다.
[4,1,3,5,7]에서 4,1 비교하여 교체 4,3 비교하여 교체 해서 5와 7을 제외한 원소를 비교하여 5앞에 4가 놓인다.
4회전에는 [1,3,4,5,7] 의 마지막 결과가 나온다.
4까지의 정렬된 원소를 제외한 1,3을 비교하여 1이 작기 때문에 교체하지 않는다. 이로서 정렬이 완성된다.
시간복잡도는 해당 정렬할 원소가 역순으로 되어 있으면 최악이며 최악일때와 최적일 때 둘다 O(n^2) 이다.
4. 합병 정렬 (Merge Sort)
하나의 리스트를 두 개의 균등한 크기로 분할하고 분할 된 부분 리스트를 정렬한 다음 두 개의 정렬 된 리스트를 합하여 전체가 정렬된 리스트가 되는 알고리즘이다.
과정)
- 분할 단계 : 입력 배열을 같은 크기의 2개의 부분 배열로 분할한다.
- 정복 단계 : 부분 배열을 정렬한다. 부분 배열의 크기는 충분히 작지 않으면 순환 호출을 이용하여 다시 분할 정복을 적용
- 결합 단계 : 정렬된 부분 배열들을 하나의 배열에 합병한다.
예)
[5,4,1,9,3,7,2,6]
라는 리스트가 있다.
먼저 이 리스트를 크기가 같은 두개의 리스트로 분할 한다.
[5,4,1,9] [3,7,2,6]
그리고 나서 이 것들을 크기가 1이 될때 까지 분할한다.
[5,4] [1,9] [3,7] [2,6]
[5] [4] [1] [9] [3] [7] [2] [6]
그러면 이제 부터 크기가 1인 분할된 부분리스트들을 합치면서 정렬을 시작하게 된다.
[4,5] [1,9] [3,7] [2,6]
[1,4,5,9] [2,3,6,7]
그리고 마지막으로 하나로 합치는 과정을 겪게 된다.
[1,2,3,4,5,6,7,9]
시간복잡도는 O(nlogn) 이다. 그 이유는 분활과정에 있다.
분할 과정은 한번 실행 할 때마다 리스트의 크기가 1/2 씩 감소하게 된다. 그래서 처음 N개 요소를 한번 분할 하면
n/2개의 리스트를 2개 얻는다. 그 상태에서 분할을 또 수행하고, n/4 크기의 서브리스트 4개를 얻는다.
이렇게 크기가 1이 될 때 까지 반복하는데
리스트의 크기가 2라면 분할은 1번 4개라면 2번 처럼 리스트의 개수가 총 8개라면 3번을 반복해야 크기가 1인 부분리스트를 얻을 수 있다.
5. 퀵 정렬 (Quick Sort)
퀵정렬은 이름 그대로 매우 빠르게 정렬을 수행하는 알고리즘이다. 기본적으로 합병 정렬 (Merge sort) 처럼 분할정복의 성격을 가지고 있고, 실제로도 많이 사용되는 대표적인 정렬 알고리즘이다.
과정)
- 주어진 배열에서 하나의 요소를 선택하고 이를 pivot(피벗) 으로 삼는다.
- 배열 내부의 모든 값을 검사하면서 피벗 값보다 작은 값들은 왼쪽에, 큰 값들은 오른쪽에 배치한다.
- 이렇게 하면 배열이 두 부분으로 나뉜다. 나뉜 이 두개의 배열에서 각각 새로운 피벗을 만들어서 두개의 배열로 다시 쪼개어 준다.
- 더이상 배열을 쪼갤 수 없을 때 까지 진행한다.
피벗을 정하는 기준은 보통 첫번째 값이나 마지막 값을 피벗으로 선정하거나 중간값을 선정하거나 무작위 값을 선정하는 3가지 방법이 있다.
예)
[5,2,9,7,3,1,6]
피벗을 5로 선정하고, 피벗을 제외한 low와 high를 양끝 점에 둔다.
그럼
[5,2,9,7,3,1,6] 이렇게 5는 피벗 2는 low 6은 high 가 된다.
low를 계속 움직이면서 배열 요소를 검사한다. 5보다 큰지 작은지 비교해서 작으면 넘어가고 크면 거기서 low를 멈춘다.
그리고 이제 high를 움직이면서 5랑 비교해서 high는 크면 넘어가고, 작으면 멈춘다.
low와 high가 모두 정지된 상황에서 만약 low랑 high가 서로 위치가 역전된 상태가 아니라면 중단된 지점에 있던 두 요소를 교환한다. 따라서 1과 9가 교환이 된다.
[5,2,1,7,3,9,6]
그리고 다시 low를 이동 시킨다. 다시 low가 피벗보다 큰 값을 가지면 중단한다. 그리고 high를 이동 시킨다.
high는 피벗보다 작은 값을 가지면 중단한다.
그래서 현 중단 점은
[5,2,1,7,3,9,6]
이렇게 됐을 것이다.
그럼 아까처럼 모두가 정지된 상황에서 비교하여 교환한다. 그러면
[5,2,1,3,7,9,6]
이 됐다.
low와 high가 교차하지 않았기 때문에 비교하여 교차한 것이고, 그 다음 low가 한번 더 이동하면 피벗보다 크면서 중단
high도 피벗보다 더 작은 값을 만나서 중단
하지만 이번의 경우
[5,2,1,3,7,9,6]
이렇게 high와 low가 서로 위치가 역전 됐기 때문에 교환하지 않고 정렬을 끝낸다.
그리고 1차로 정렬이 끝나면 피벗으로 설정된 배열요소를 high가 가리키는 배열요소와 교환해준다. 이제 피벗을 중심으로 왼쪽과 오른쪽에 피벗보다 작고 큰 값들이 위치했음을 확인할 수 있다.
[3,2,1,5,7,9,6]
이렇게 다시 3을 피벗으로 같은 과정을 반복 하면 된다.
[3,2,1,5,7,9,6]
시간복잡도는 최악의 경우 O(n^2) 이며, 평균 O(nlogn)이기 때문에 피벗 값을 잘못 선정하면 버블 정렬이나 다름없는 성능을 보여준다.
'알고리즘 이론' 카테고리의 다른 글
| 탐색 알고리즘 (선형, 이진) (0) | 2024.08.06 |
|---|