하루 하루는 성실하게
인생 전체는 되는대로

[공부 노트] #7

3 minute read

Q1. getline()

c++에는 getline()함수가 두 가지 있는데, 하나는 char* 형식으로 마지막에 ‘/0’값을 가지는 c언어 방식의 문자열이 있고, std::string을 따르는 문자열이 있다. istream 라이브러리에 속한 getline()함수는 다음과 같이 사용한다.

#include <iostream>

using namespace std;

cin.getline(char* s, streamsize n);
cin.getline(char* s, streamsize n, char delim);

받고자 하는 크기인 n은 마지막 ‘/0’을 포함하므로 주의하자.

#include <string>

using namespace std;

getline(istream* is, string& str);
getline(istream* is, string& str, char delim);

Q2. sort

c++ algorithm 헤더의 기본 sort를 사용하는 것이 아닌 stable_sort를 사용해야하는 문제를 풀고 정렬에 대해 한번 정리해볼 필요가 있을 것 같아서 공부하였다.

Bubble Sort

  • 최선 : O($n^2$)
  • 최악 : O($n^2$)
  • 공간복잡도 : O(n)
  • 안정 정렬

인접한 두 원소의 대소 관계를 비교하여 위치를 교환하는 과정을 반복한다. (n-1) + (n-2) + … + 1 번의 비교가 필요하므로 (n^2)/2의 비교가 일어난다.

Selection Sort

  • 최선 : O($n^2$)
  • 최악 : O($n^2$)
  • 공간복잡도 : O(n)
  • 불안정 정렬

순서대로 해당 위치에 있어야 할 원소를 찾아 선택하는 알고리즘이다. 현재 인덱스부터 마지막 인덱스까지의 최소값을 찾아 현재 인덱스와 교체해주고, 인덱스를 증가시키는 과정을 반복한다. bubble sort와 시간 복잡도는 산술적으로 같지만, 실제로 원소의 교환이 일어나는 횟수는 더 작으므로 조금 더 효율적이다.

Insertion Sort

  • 최선 : O(n) (이미 정렬된 배열)
  • 최악 : O($n^2$)
  • 공간복잡도 : O(n)
  • 안정 정렬

2번째 원소부터 시작하여 그 앞의 원소와 비교하여 삽입위치를 찾을 때 까지 한 칸씩 원소를 뒤로 미루는 방법이다. 대부분의 원소가 정렬되어 있는 경우 매우 효율적일 수 있다. selection sort와 비교하여, k번째 순회 이후 앞의 k개의 원소는 정렬된 상태라는 공통점이 있지만, 이후 k+1번째 원소를 찾기위해 selection sort는 남은 모든 원소를 찾아야하는 반면, insertion sort는 필요한 만큼의 요소만 탐색하여 조금 더 효율적이다.

Quick Sort

  • 최선 : O($n\log_{2}n$)
  • 최악 : O($n^2$) (이미 정렬된 배열)
  • 공간복잡도 : O(n)
  • 불안정 정렬

분할정복(divide and conquer)방식을 이용해 배열을 정렬한다. 분할정복이란, 문제를 작은 문제로 분할하여 해결한 뒤, 답을 모아서 해결하는 방식이다.

1. 피벗을 고른다.
2. 피벗 앞에는 피벗보다 작은 값들이 오도록 하고, 피벗 뒤에는 피벗보다 큰 값들이 오도록 한다.
3. 피벗을 기준으로 배열을 둘로 나누고, 1부터 반복한다.

평균적으로 아주 빠르지만, 이미 정렬된 배열을 정렬할 때 최악의 시간복잡도를 보여준다. 이는 이미 정렬된 배열에서 피벗을 골라 다시 배열을 나눌 때, 크기 n의 배열이 1과 n-1크기의 배열로 나누어지기 때문에 n번 반복되고, 비교 또한 n번 이루어진다. 불필요한 데이터의 이동을 줄이고, 결정된 피벗들은 이후 연산에서 제외된다.

Merge Sort

  • 최선 : O($n\log_{2}n$)
  • 최악 : O($n\log_{2}n$)
  • 공간복잡도 : O(n)
  • 안정 정렬

분할정복 방식을 이용한다.

1. 배열을 가능한 잘게 쪼갠다.(divide)
2. 쪼개진 배열을 합병(merge)하면서 정렬시킨다. 두 배열은 이전 단계에 의해 이미 정렬된 상태이므로, 두 배열을 순서대로 비교하면 된다.

quick sort는 정렬 -> 분할 의 과정이라면, merge sort는 분할 -> 정렬 의 과정이라는 처이가 있다. 또한 분할 과정이 균등하므로, quick sort와 다르게 최악의 경우에도 시간복잡도가 그대로다. 또한, 비교하여 정렬하는 과정이 순차적이므로 linked list기반의 자료구조 정렬에 효율적이다. 지금까지의 정렬 알고리즘과는 달리 추가적인 메모리 공간이 필요한(not in place)정렬 방법이다. c++ algorithm헤더의 stable_sort함수가 merge sort를 사용한다.

Q3. Why Quick Sort

merge sort를 사용하면 최악의 경우에도 O($n\log_{2}n$)를 유지할 수 있는데, 왜 quick sort가 더 자주 쓰이는 것 일까?

  1. 추가적인 공간: quick sort는 in-place sort지만, merge sort는 정렬된 배열을 저장할 임시적인 공간이 따로 필요하다.
  2. Worst case : 최악의 시간복잡도인 O($n^2$)를 해결하는 방법으로 피벗을 랜덤하게 선택하면, 확률적으로 최악의 시간복잡도가 나오기 매우힘들다.
  3. 참조 지역성 : quick sort는 한정적인 배열에서 피벗을 중심으로 데이터들을 움직여 참조 지역성이 좋으므로 성능이 더 좋다. 즉, 정렬하려는 데이터들이 지역적으로 밀집되어 있으면 cache hit의 비중이 높아져 더 효율적이라는 것이다.

Q4. C++ sort

c++ algorithm 헤더의 sort는 quick sort 기반이라는 내용을 어디선가 보고 ‘그렇구나 ㅇㅇ’ 하고있었는데, 더 자세히 찾아보니 [intro sort]라는 개념을 찾게되었다. intro sort의 작동 방식은 다음과 같다.

1. 리스트의 크기가 16 이하라면 삽입 정렬을 한다.
2. 전체 리스트에 대해 퀵 정렬을 수행한다.
3. 수행 도중 재귀 호출의 깊이가 2⌈log⁡n⌉을 넘어가게 되면 4번 항목으로 넘어간다.
4. 쪼개진 부분 리스트의 크기가 16 이하라면 그대로 놔둔다.
   16보다 크다면 해당 부분 리스트에 대해 힙 정렬을 수행한다.
5. 3, 4번 항목이 모두 완료된 후, 대부분 정렬이 된 전체 리스트에 대해 삽입 정렬을 수행한다.

큰 틀은 quick sort가 맞지만, 데이터가 적을 때는 quick sort보다 insertion sort가 더 빠르므로 이러한 과정을 거친다고 한다. 또한 ‘16’이라는 값은 휴리스틱하게 구해진 값이라고 한다. quick sort를 2⌈log⁡n⌉ 까지만 수행하기 때문에 최악의 경우에도 O($n^2$)는 나오지 않는다.

참고문헌

https://gyoogle.dev/blog/algorithm/
https://www.geeksforgeeks.org/quicksort-better-mergesort/
https://justicehui.github.io/medium-algorithm/2019/03/24/IntroSort/

Leave a comment

You may also enjoy