Hoon222y

정렬 알고리즘의 종류에는 여러가지가 있는데 이번 포스팅에서는 각 정렬 알고리즘에 대해 알아보도록 하겠다. [버블정렬 (bubble sort)] - 버블 정렬의 경우 두 인접합 원소를 비교하여 정렬하는 방법이다. 시간복잡도가 O(n^2) 이기 때문에 그냥은 잘 사용하지 않지만 단순구현하지 좋기때문에 사용하기도 한다. 해당 과정처럼 가장 인접한 두 원소들을 비교하고 바로 옆칸으로 이동하여 끝까지 이동하면서 비교를 하게된다. 버블소트의 경우 다른 정렬들과는 다르게 비효율적이라고 했는데 그 이유는 해당과 같다. 간단하게 총정리 느낌으로 본다면 [선택정렬 (selection sort)] - 주어진 원소에서 정렬되어지지 않은 부분의 가장 작은 값을 앞으로 보내는 방식이다. 버블소트와 비슷하게 모든 부분에 대해서 비..

https://www.acmicpc.net/problem/1377 버블 소트가 총 몇 회 발생하는지 찾는 문제이다. 하지만 그냥 실제로 버블 소트를 하면서 버블 소트 횟수를 찾게되면 N의 제한이 50만이고 복잡도가 O(N^2)이므로 시간초과이다. 이 문제의 경우 버블 소트의 특성을 잘 이해하면 풀 수 있는 문제이다. 버블 소트의 경우 한번 반복될 때 오른쪽으로는 몇번을 이동하게 되던, 왼쪽으로는 어떤 수이던 딱 한번만 움직이게 된다. 따라서 처음 입력에서 sort한 이후에 인덱스의 차이가 가장 큰 경우를 찾아주면 되는 문제이다. 12345678910111213141516171819202122232425262728293031323334#include #include #include #include #inc..