지나공 : 지식을 나누는 공간
[3] C++ 정렬 알고리즘 시간 복잡도 이것이 코딩테스트다 chapter6 정리 - 선택 정렬, 삽입 정렬, 퀵 정렬, 계수정렬, 두 배열의 원소 교체 본문
[3] C++ 정렬 알고리즘 시간 복잡도 이것이 코딩테스트다 chapter6 정리 - 선택 정렬, 삽입 정렬, 퀵 정렬, 계수정렬, 두 배열의 원소 교체
해리리_ 2020. 12. 29. 16:10정렬이란?
- 데이터를 특정한 기준에 따라서 순서대로 나열하는 것
- 정렬이 되면 이진 탐색이 가능해진다.
- 선택정렬, 삽입정렬, 퀵정렬, 계수 정렬에 대하여
선택 정렬
[소개]
가장 원시적인 방법으로 매번 '가장 작은 것을 '선택'하는 정렬
[방법]
데이터가 무작위로 여러 개 있을 때, 이 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 반복한다.
[그림]
[코드]
#include <iostream>
using namespace std;
int n = 5; //정렬할 개수
int arr[10] = { 7, 4, 5, 9. 8, 2, 1 };
int main(void) {
for (int i = 0; i < n; i++) {
int min_index = i; //가장 작은 원소가 와야 할 위치 인덱스
for (int j = i + 1; j < n; j++) {//하나씩 비교하면서 가장 작은 값의 위치 찾음
if (arr[min_index] > arr[j]) {
min_index = j;
}
}
swap(arr[i], arr[min_index]);
}
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
}
[시간복잡도]
1. arr[0]과 나머지 (n-1)개를 각각 비교하므로 연산을 (n-1)번 수행 -> arr[0] 세팅 완료
2. arr[1]과 나머지 (n-2)개를 각각 비교하므로 연산을 (n-2)번 수행 -> arr[1] 세팅 완료
3. arr[2]와 나머지 (n-3)개를 각각 비교하므로 연산을 (n-3)번 수행 -> arr[2] 세팅 완료
4. 이하 동일.
따라서, 연산 횟수는 (n-1) + (n-2) + ... + 2 + 1, 즉 n(n-1)/2 번 연산한다.
시간복잡도는 O(n^2)이다.
삽입정렬
[소개]
선택정렬에 비해 구현 난이도가 높지만 선택 정렬에 비해 실행 시간 측면에서 더 효율적인 알고리즘이다. 특히 필요할 때에만 위치를 바꾸므로 '데이터가 거의 정렬되어 있을 때' 훨씬 효율적이다.
특정한 데이터를 적절한 위치에 '삽입'한다는 의미에서 삽입 정렬이라고 불린다.
[방법]
특정한 데이터가 적절한 위치에 들어가기 이전에, 그 앞까지의 데이터는 이미 정렬되어 있다고 가정한다.
정렬되어 있는 데이터 리슽트에서 적절한 위치를 찾은 뒤에, 그 위치에 삽입된다.
[그림]
삽입 정렬에서 첫 번째 데이터는 그 자체로 이미 정렬되어 있다고 판단하기 때문에, 두 번째 데이터부터 시작한다.
두 번째 원소인 3부터 보면 이미 정렬되어 있는 첫 데이터 '4'와 비교해서 이것의 오른쪽에 들어갈지 왼쪽에 들어갈지를 판단해야 한다.
세 번째 원소인 2의 경우도 이어서 적절한 위치를 찾으면 되는데 2가 들어갈 수 있는 위치는 아래와 같이 3개다.
삽입 정렬에서 정렬이 이루어진 원소는 항상 오름차순을 유지하고 있다. 이런 특징 때문에 삽입 정렬에서는 특정한 데이터가 삽입될 위치를 선정하기 위해 왼쪽으로 한 칸씩 이동할 때, 삽입될 데이터보다 작은 데이터를 만나면 그 위치에서 멈추면 된다.
즉, 특정 데이터의 왼쪽에 있는 데이터들은 이미 정렬이 된 상태이므로 자기보다 작은 데이터를 만났을 때 더 이상 데이터를 살펴볼 필요 없이 그 자리에 삽입하면 된다.
[코드]
#include <iostream>
using namespace std;
int n = 8;
int arr[10] = { 4, 3, 2, 10, 12, 1, 5, 6 };
int main(void) {
for (int i = 1; i < n; i++) { //두 번째 원소부터 적정 위치 찾기
// 자기 자신부터 왼쪽으로 한칸씩 움직임
for (int j = i; j > 0; j--) { //swap이 있으니 [0]이 아닌 [1] 인덱스까지만 순회
if (arr[j] < arr[j - 1]) {
swap(arr[j], arr[j - 1]);
}
else break;
}
}
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
}
[시간복잡도]
for문에서 두 번 중첩되므로 O(N^2)이다. 선택정렬과 시간복잡도가 동일하다.
하지만 삽입정렬은 현재 리스트의 데이터가 거의 정렬되어 있는 상태람련 매우 빠르게 동작한다.
최선의 경우 O(N)의 시간복잡도를 가진다.
바로 아래에서 볼 퀵정렬과 비교할 때 보통은 삽입 정렬이 더 비효율적이지만 정렬이 거의 되어 있는 상태라면 퀵 정렬보다 삽입 정렬이 더 효율적이다. 거의 정렬된 채로 주어진 문제에서는 삽입 정렬을 이용하는 게 좋다.
퀵 정렬
[소개]
소개한 위의 알고리즘과 비교할 때 가장 많이 사용되는 알고리즘임.
그리고 퀵 정렬과 비교될 정도로 빠른 알고리즘으로 병합 정렬 알고리즘이 있다.
[방법]
기준을 설정한 다음 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 방식, 퀵 정렬은 큰 수와 작은 수를 교환할 때 사용하는 기준인 pivot이 사용된다. 이 pivot을 어떻게 설정할 것인지 미리 명시해야 한다. 여기선 호어 분할 방식을 본다. (pivot을 리스트에서 첫 번째 데이터로 설정)
[그림]
1. pivot은 첫 번째 데이터인 54이다. 54를 기준으로 왼쪽 끝과 오른쪽 끝에서 각각 더 큰 수와 더 작은 수를 찾아 둘의 위치룔 교환한다.
2. leftmark는 기준에 대해 더 큰 수를 찾으므로 처음에는 93에서 멈추고, rightmark는 20에서 멈춘다. 이제 둘의 자리를 바꾼다.
3. 다시 leftmark는 오른쪽 방향으로 이동하면서 54보다 큰 수를 찾아서 77에 멈춘다. rightmark는 왼쪽 방향으로 이동하면서 54보다 작은 수를 찾아서 44에서 멈춘다. 둘의 위치를 다시 바꿔준다.
4. 현재 rightmark는 54보다 작은 수를 찾기 위해 다시 왼쪽으로 이동하던 중에 31을 만나 멈추고, leftmark는 54보다 큰 수를 찾기 위해 다시 오른쪽으로 이동하던 중에 77을 만나 멈춘다. leftmark가 rightmark보다 항상 왼쪽에 있었다가 둘의 위치가 전복되었으니(?) 이런 경우에는 작은 수 데이터와 pivot의 위치를 바꿔준다. 그러면 아래와 같은 그림이 된다.
pivot이던 54를 기준으로 왼쪽 리스트와 오른쪽 리스트를 보면, 왼쪽은 모두 54보다 작은 수, 오른쪽은 모두 54보다 큰 수이다. 위처럼 데이터가 위치하도록 피벗보다 작으면 왼쪽, 크면 오른쪽에 위치하게 하는 작업이 파티션이다.
이제 나눠진 양쪽 리스트에 대해서 위와 같은 작업을 반복한다. (재귀함수 사용)
재귀함수를 사용할 것이므로 종료 조건이 필요하다.
퀵 정렬의 종료 조건은 현재 리스트의 데이터 개수가 1개일 때다.
[코드]
#include <iostream>
using namespace std;
int n = 9;
int arr[9] = { 54, 26, 93, 17, 77, 31, 44, 55, 20 };
void quickSort(int* arr, int start, int end) {
if (start >= end) return; //원소가 1개일 때 종료
int pivot = start;
int left = start + 1;
int right = end;
while (left <= right) {//전복되기 전까지 반복
while (left <= end && arr[left] <= arr[pivot])
left++; //pivot보다 큰 걸 찾을 때까지 계속 오른쪽으로 이동
while (right > start && arr[right] >= arr[pivot])
right--;
if (left > right) //엇갈렸을 때 pivot과 작은 데이터의 위치 변경
swap(arr[pivot], arr[right]);
else //엇갈리지 않았으면 큰 수와 작은 수 위치 변경
swap(arr[left], arr[right]);
}
//분할하여 오른쪽과 왼쪽 각각을 실행
quickSort(arr, start, right - 1); //현재 right위치에 pivot이 있으니 그 왼쪽
quickSort(arr, right + 1, end);
}
int main(void) {
quickSort(arr, 0, n - 1);
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
}
[시간복잡도]
선택 정렬과 삽입 정렬은 최악의 경우에도 항상 시간 복잡도 O(N^2) 을 보장한다. 삽입 정렬은 최선의 상태에서 O(N)이고.
퀵 정렬의 시간복잡도는 O(NlogN)이다. 하지만 최악의 경우 시간복잡도가 O(N^2)이다.
퀵 정렬에서 최선의 경우는 언제인가?
pivot의 위치가 변경되면서 분할이 일어날 때마다 정확히 왼쪽 리스트와 오른쪽 리스트를 절반씩 분할하게 된다면 속도가 조금 다를 수 있다. 데이터가 8개라고 가정할 때 절반씩 나뉜다고 생각하면 연산의 높이가 logN 이다.
이런 경우라면 분할이 이루어지는 횟수가 기하급수적으로 감소한다.
퀵 정렬은 삽입 정렬과 달리 데이터가 정렬되어 있을 때가 더 느리게 동작한다.
그래서 C++처럼 퀵 정렬로 구현된 라이브러리를 제공하는 언어에서는 최악의 경우이더라도 O(NlogN)이 되도록 pivot을 설정할 때 추가 로직이 있다.
지금까지 본
- 선택 정렬 : O(n^2)
- 삽입 정렬 : O(n^2) , 거의 정렬되어 있는 최선의 경우에 O(n)
- 퀵 정렬 : O(nlogn), 거의 정렬되어 있는 최악의 경우에 O(n^2)
들은 직접 데이터의 값을 비교한 뒤에 위치를 변경하면서 정렬하는 '비교 기반의 정렬 알고리즘'이다.
계수 정렬
[소개]
데이터의 개수가 매우 많더라도 빠르게 동작하는 정렬 알고리즘이다. 데이터 개수가 N, 데이터 중 최댓값이 K일 때 계수 정렬은 최악의 경우에도 수행시간 O(N+K)를 보장한다.
다만,
데이터의 크기 범위가 정수 형태로 표현 가능할 때만 사용할 수 있다. 만약 데이터 값이 무한한 범위를 가질 수 있는 실수형 데이터가 주어지면 계수정렬을 사용하기 어렵다. 또한 가장 큰 데이터와 가장 작은 데이터의 차이가 너무 커도 이 정렬을 사용할 수 없다.
왜냐하면, 계수정렬을 이용할 때는 '모든 범위를 담을 수 있는 크기의 배열을 선언해야 하기 때문이다.'
별도의 배열을 선언하고 정렬에 대한 정보를 담는 특징이 있다.
[방법과 그림]
주어진 배열이 아래와 같다고 하자.
가장 큰 데이터와 가장 작은 데이터의 범위가 모두 담길 수 있도록 하나의 리스트를 생성한다.
각 인덱스의 값에 해당 값이 나온 개수를 저장할 것이다.
이제 Array의 맨 앞에서부터 값을 보면서 count array의 해당 인덱스의 값을 하나씩 증가시킨다.
맨 첫 번째 데이터가 5이므로 Count Array의 5번째 인덱스의 값이 1이 된다.
두 번째 데이터가 2이므로 Count Array의 2번째 인덱스의 값이 1이 된다.
세 번째 데이터가 5이므로 Count Array의 5번째 인덱스 값이 또 증가해서 2가 된다.
위의 과정을 반복하면 Count Arrya가 아래와 같아진다.
이제 Count Array의 맨 앞에서부터 인덱스를 인덱스 값(개수)만큼 출력하면 된다.
1 2 33 555 66 9
[코드]
#include <iostream>
#define MAX_VALUE 9
using namespace std;
int n = 10;
//모든 원소의 값이 0보다 크거나 같다고 가정함 (인덱스로 쓰여야 하니까)
int arr[10] = { 5, 2, 5, 3, 6, 1, 5, 3, 9, 6 };
//모든 범위를 포함하는 배열 선언(모든 값은 0으로 초기화)
int cnt[MAX_VALUE + 1]; //인덱스 값 중 MAX는 9지만 배열 크기는 10임
int main(void) {
for (int i = 0; i < n; i++) {
cnt[arr[i]] += 1; // 각 데이터를 만나면 해당 인덱스 값을 증가시킴
}
for (int i = 0; i <= MAX_VALUE; i++) {
for (int j = 0; j < cnt[i]; j++) {
cout << i << ' '; //등장한 횟수만큼 인덱스를 출력
}
}
}
[시간복잡도]
계수 정렬은 앞에서부터 데이터를 하나씩 확인하면서 배열에서 적절한 인덱스의 값을 1씩 증가시키고 추후에 배열의 각 인덱스에 해당하는 값들을 확인하면서 그 갯수만큼 반복문을 수행해야 하기 때문에 데이터의 개수를 N, 데이터 중 최댓값의 크기를 K라고 하면 시간복잡도는 O(N+K)이다.
따라서 데이터의 범위만 한정되어 있다면 효과적으로 사용할 수 있고 빠르게 동작한다. 현존하는 정렬 알고리즘 중 기수 정렬과 계수 정렬이 가장 빠르다.
[공간복잡도]
계수정렬의 공간복잡도는 O(N+K)이다.
데이터가 0과 999,999 로 두 개라면 계수정렬은 심각한 비효율성을 초래할 수 있다. 리스트의 크기가 100만이 되도록 선언해야 하기 때문이다. 계수 정렬은 성적과 같이 100점이 여러 명일 수 있는 경우에 효과적이다. 반면 일반적인 경우(정렬이 잘 안되어있거나 특징을 알기 어려운 배열)에 퀵 정렬을 사용하는 것이 빠르다.
데이터가 한정적일 때 사용할 수 있고 중복이 많을 수록 유리하다. 하지만 데이터가 한정적이어야 한다는 조건만 맞으면 데이터 개수가 매우 많아도 효과적이다.
코딩테스트에서는 입력 데이터의 개수를 1000만 개 미만으로 주로 출제한다.
C++ 정렬 라이브러리 사용에 대해서는 다음 포스팅에서..
C++로 정렬 알고리즘 sort 사용법, 내림차순, 특정 변수 기준 정렬(연산자 오버로딩, compare 함수 활
알아볼 내용은, sort 기본 함수 알아보기 내림차순 정렬하기 특정 변수 기준으로 정렬하기 compare 함수 구현 연산자 오버로딩으로 구현 특정 변수 기준 내림차순 정렬하기 연산자 오버로딩 + compare
eocoding.tistory.com
위 포스팅은 sort 사용법이고 다른 교재의 문제는 여기에 추가하려고 한다.
두 배열의 원소교체
[문제]
두 배열 A, B를 가지고 있고 이들은 N개의 원소를 가진 배열이다. 배열의 원소는 모두 자연수이다. 동빈이는 최대 K번의 바꿔치기 연산을 수행할 수 있는데, 바꿔치기 연산이란 배열 A에 있는 원소 하나와 배열 B에 있는 원소 하나를 골라서 두 원소를 서로 바꾸는 것을 말한다. 동빈이의 최종 목표는 배열 A의 모든 원소의 합이 최대가 되도록 하는 것이며 여러분은 동빈이를 도와야 한다.
N, K 그리고 배열 A,B의 정보가 주어졌을 때 최대 K번의 바꿔치기 연산을 수행하여 만들 수 있는 배열 A의 모든 원소의 합의 최댓값을 출력하는 프로그램을 작성하시오.
예시가 너무 길어서 생략.
[풀이] - 주석에 달았음
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int>a;
vector<int>b;
int sum;
bool compare(int a, int b) {
return a > b;
}
int main(void) {
int n, k;
cin >> n >> k;
for (int i = 0; i < n; i++) {
int e;
cin >> e;
a.push_back(e);
}
for (int i = 0; i < n; i++) {
int e;
cin >> e;
b.push_back(e);
}
sort(a.begin(), a.end());
sort(b.begin(), b.end(), compare);
//최대 k번이므로 a원소가 b원소보다 큰 상태면 굳이 바꾸지 않는다.
//k번 이하로 바꿔도 되니까
//그리고 이미 정렬된 상태이니 a가 b보다 큰 상태면 그 뒤로 쭉 그런거니까 바로 break
for (int i = 0; i < k; i++) {
if (a[i] < b[i]) {
swap(a[i], b[i]);
}
break;
}
for (int i : a) {
sum += i;
}
cout << sum;
return 0;
}
if문을 빼먹으면 안된다. K번 바꿔치기가 아니라 최대 K번인거니까 순회하다가 어느 시점에서 A의 원소가 더 큰 상태라면 정렬된 상태니까 그 이후는 쭉 A가 더 크다. 따라서 이때부터는 바꾸지말고 반복문을 break 해야한다.
'Algorithm > 알고리즘들' 카테고리의 다른 글
| [4] C++ 이진탐색 이것이 코딩테스트다 chapter7 정리 (0) | 2021.01.06 |
|---|---|
| [2] C++ 탐색 알고리즘 이것이 코딩테스트다 chapter5 BFS/DFS 정리 - 스택, 큐, 재귀함수, DFS, BFS, 유클리드 호제법 (0) | 2020.10.18 |
| [1] C++ 구현 알고리즘, 문제에 적용하기, 이것이 코딩테스트다 chapter4 구현 문제풀이 (0) | 2020.10.05 |
| [0] 그리디 알고리즘, 문제에 적용하기(Greedy Algorithm, 탐욕) - C++ (0) | 2020.09.20 |
