본문 바로가기

알고리즘12

[C++] 퀵 정렬 (Quick Sort) 이번 시간에는 퀵 정렬에 대해 알아보도록 하겠다. 저번 시간까지 배웠던 선택 정렬, 버블 정렬, 삽입 정렬 모두 시간 복잡도가 O(n ^ 2)였다. 이러한 복잡도를 가지는 알고리즘은 데이터의 갯수가 10만개만 넘어가도 일반적인 상황에서 사용하기가 매우 어려운 알고리즘이다. 그렇기 때문에 더욱 빠른 정렬 알고리즘이 필요하고, 대표적인 빠른 알고리즘이 퀵 정렬로, O(N * logN)의 시간 복잡도를 가진다. 퀵 정렬(Quick Sort)는 하나의 큰 문제를 두 개의 작은 문제로 분할하는 식으로 빠르게 정렬한다. 특정한 값을 기준으로 큰 숫자와 작은 숫자를 서로 교환한 뒤에 배열을 반으로 나눈다. 일반적으로 퀵 정렬에서는 기준값이 있고, 이를 피벗(pivot)이라고 하는데, 보통 첫 번째 원소를 피벗 값으로.. 2020. 5. 6.
[C++] 삽입 정렬(Insertion Sort) 이번 시간에는 삽입 정렬에 대해 알아보도록 하겠다. 삽입 정렬은 각 숫자를 적절한 위치에 삽입하는 방법으로 문제를 해결한다. 다른 정렬 방식들은 무조건 위치를 바꾸는 방식이었다면 삽입 정렬은 필요할 때만 위치를 바꾼다. 삽입 정렬은 비교적 느린 정렬 알고리즘에 속하지만 쉽게 생각할 수 없는, 조금은 복잡한 구조를 가지고 있다. 하지만 삽입 정렬은 앞서 소개했던 버블 정렬과 선택 정렬에 비해서는 더 효율적인데, 매 차례에 바로 앞 원소와 비교하면서 자신의 위치까지만 swap 연산을 하고, 자신의 위치를 찾으면 멈추기 때문이다. 코드로 구현해 보면, #include int main() { int i, j, temp; int array[10] = { 1, 10, 5, 8, 7, 6, 4, 3, 2, 9 }; .. 2020. 5. 6.
[C++] 버블 정렬(Bubble Sort) 이번 시간에는 버블 정렬에 대해 알아보도록 하겠다. 버블 정렬은 가까이에 있는 두 숫자끼리 비교를 해서 당장 더 작은 숫자를 앞으로 보내주는 것을 반복하는 것이다. 정렬 알고리즘 중 가장 쉽지만 가장 비효율적인 정렬 방법이다. 앞서 배웠던 선택 정렬과 다르게 뒤에서부터 정렬이 된다. 코드로 구현해보면 #include int main() { int i, j, temp; int array[10] = { 1, 10, 5, 8, 7, 6, 4, 3, 2, 9 }; for (i = 0; i array[j + 1]) { temp = array[j]; array[j] = array[j + 1]; arr.. 2020. 5. 6.
[C++] 선택 정렬 (Selection Sort) 알고리즘 정리에서는 알고리즘에 대해 공부하면서 배운 내용을 정리해보겠다. 먼저 선택 정렬에 대해 알아보겠다. 선택 정렬은 가장 작은 것을 하나 뽑아서 맨 앞에 두고, 남은 것 중에서 또 작은 것을 뽑아서 두번째에 두면서 계속 진행하여 결국 모든 원소들을 정렬하는 방법이다. 코드로 구현해보면 #include int main() { int i, j, min, index, temp; int array[10] = { 1, 10, 5, 8, 7, 6, 4, 3, 2, 9 }; for (i = 0; i < 10; i++) { min = 9999; for (j = i; j < 10; j++) { if (array[j] < min) { min = array[j]; index = j; } } temp = array[i].. 2020. 5. 6.