Notepad

C++/Algorithm

[Algorithm/C++] 퀵 정렬(Quick Sort) - 분할과 재귀

1. 설명 퀵 정렬(Quick Sort)란 분할과 재귀를 사용하여 최종적으로 정렬된 리스트를 얻는 정렬 방식 중 하나이다. 여기서 분할이란 처음의 1개 문제가 있었다면 이를 2개 혹은 3개처럼 더욱 작은 문제로 나누어서 문제를 각각 해결한 후 합하여 처음의 복잡하였던 1개의 문제의 해답을 구하는 방법이다. 재귀란 간단하게 함수 속에서 해당 함수를 호출하는 형태라고 할 수 있으며, 계속 반복하여 실행되기 때문에 반복하여 실행되는 중 실행을 중단하는 조건을 포함해야만 하며 그렇지 않으면 무한 루프에 빠지게 된다. 퀵 정렬은 분할과 재귀를 사용한다고 하였는데, 우선 분할을 수행하여 동일한 형태이지만 작은 문제 2개로 만들고 동일한 형태이기 때문에, 재귀를 통하여 나누어진 작은 문제에서도 앞서 수행한 분할 작업..

C++/Algorithm

[Algorithm/C++] 삽입 정렬(Insertion Sort) - 비교 후 삽입

1. 설명 삽입 정렬(Insertion Sort)란 리스트의 값들을 순차적으로 인접한 원소와 비교를 하여 위치를 교환해주며 정렬을 하는 방법 중 하나이다. 한 원소를 선택하여 위치를 변경해준다는 점에서 선택 정렬(Selection Sort)과 유사하다고 할 수도 있으며 인접한 원소 간 비교를 통하여 위치를 교환해주므로 거품 정렬(Bubble Sort)과도 유사하다고 할 수도 있다. 동작 예시를 살펴보면 오름차순 정렬을 위해서는 리스트의 첫 번째 위치에는 리스트에서 가장 작은 값이 위치하여야 한다. 시작은 두 번째 Index부터 시작하며 왼쪽에 있는 원소들과 비교를 통하여 더 큰 값이 왼쪽에 위치하고 있다면 교환하는 작업을 수행한다. 이 작업을 반복하여 수행함으로써 가장 작은 원소는 가장 왼쪽의 위치하게 ..

C++/Algorithm

[Algorithm/C++] 선택 정렬(Selection Sort) - 선택하여 교환

1. 설명 선택 정렬(Selection Sort)란 리스트를 순차적으로 반복하면서 해당 위치에 해당하는 값을 탐색 후 선택하여 교체함으로써 정렬을 하는 정렬 방법 중 하나이다. 동작 예시를 살펴보면 오름차순 정렬을 위해서는 리스트의 첫 번째 위치에는 리스트에서 가장 작은 값이 위치하여야 한다. 따라서 탐색을 통하여 리스트에서 가장 작은 값의 인덱스를 선택한 후 첫 번째에 있는 값과 교환을 한다. 이 같은 과정을 한 번 수행하게 되면 리스트의 첫 번째 원소는 정렬이 된 상태가 되는 것이다. 이 과정을 마찬가지로 두 번째, 세 번째 원소에도 반복하여 수행하다 보면 결국 최종적으로 정렬된 리스트를 얻을 수 있게 된다. 특징 ▶ 시간 복잡도는 O(N^2)이다. 가장 작은 원소를 탐색하는데 (N - 1), (N ..

C++/Algorithm

[Algorithm/C++] 버블 정렬(Bubble Sort) - 거품 정렬

1. 설명 버블 정렬(Bubble Sort)란 거품 정렬이라고도 하며 인접한 원소 간 비교하는 작업을 반복적으로 수행함으로써 정렬된 리스트를 얻는 정렬 방법 중 하나이다. 동작 예시를 보면 인접한 원소끼리 비교하여 왼쪽의 원소가 오른쪽의 원소보다 클 경우 위치를 교환해주고, 그다음 원소와도 이 작업을 반복하여 수행함으로써 가장 큰 원소가 가장 오른쪽으로 이동하게 된다. 이 과정을 또 반복하여 수행함으로써 가장 큰 값을 갖는 원소가 오른쪽에 차곡차곡 위치하게 되므로, 최종적으로 정렬된 리스트를 얻을 수 있게 된다. 특징 ▶ 시간 복잡도는 O(N^2)이다. 정렬이 되어 있는 상태 이어도 각 원소끼리 비교를 수행하여야 하기 때문에 동일하다. ▶ 공간 복잡도는 O(1)이다. 추가적인 삽입, 삭제 없이 위치만 변..