알고리즘7 삽입 정렬 (Insertion Sort) 삽입 정렬 삽입 정렬은 자신의 위치를 찾아서 삽입하여 정렬을 완성하는 알고리즘 입니다. 선택 정렬의 순서는 다음과 같습니다. 두 번째 자료에서 시작하여 앞의 원소들과 비교해 삽입할 위치를 정합니다. 삽입될 위치가 정해지면, 뒤쪽의 원소들을 한 칸씩 뒤로 이동시킵니다. 원소를 정해진 위치에 삽입합니다. 앞쪽의 원소들과 비교 후, 자신의 위치를 정하고 그 위치에 삽입하는 방법으로 정렬을 합니다. 시간 복잡도 최악의 경우 selection sort와 마찬가지로, $O(n^2)$의 시간 복잡도를 가집니다. 수식으로 나타내면 아래와 같습니다. $$ (n-1) + (n-2) + ... + 2 + 1 = {n(n-1)} / {2} $$ 그러나 모두 정렬이 되어 있는 경우, 한 번씩만 비교하기 때문에 $O(n)$의 시.. 2021. 9. 13. 선택 정렬 (Selection sort) 선택 정렬 선택 정렬은 데이터의 순서에 따라 위치는 이미 정해져 있고, 그 위치에 들어갈 원소를 선택하는 알고리즘입니다. 선택 정렬의 진행 과정은 다음과 같습니다. 먼저, 데이터들 중에 최소값을 찾습니다. 찾은 최소값을 맨 앞에 위치한 데이터와 교화합니다. 정렬된 맨 앞의 값을 제외하고 위와 같은 방식으로 데이터의 위치를 교환합니다. 선택 정렬은 버블 정렬과 반대로 회전마다 맨 앞의 데이터를 제외합니다. 선택 정렬은 n번의 회전 마다 n번째 데이터의 위치가 정해집니다. 시간 복잡도 선택 정렬은 버블 정렬과 마찬가지로 $O(n^2)$ 입니다. 한 번의 회전에 데이터 하나를 제외하기 때문에, 데이터가 n개 일 때, n-1 번의 순회가 필요합니다. 이를 수식으로 나타내면 아래와 같습니다. $$ (n-1) + .. 2021. 9. 10. 버블 정렬 (Bubble Sort) 버블 정렬 버블 정렬(bubble sort)은 인접한 두 수를 비교하여 조건에 맞지 않으면 두 수의 자리를 교환하여 정렬하는 알고리즘입니다. 오름차순으로 정렬하는 위의 그림을 보면, 첫 번째 데이터와 두 번째 데이터를 비교하여 크기가 큰 데이터를 오른쪽의 자리로 교환하는 것을 볼 수 있습니다. 이후 두 번째와 세 번째, 다시 세 번째와 네 번째 ... 한 칸씩 이동하면서 조건이 맞지 않으면 서로의 자리를 교환합니다. 1회전이 끝나면 가장 큰 수가 맨 뒤에 위치하기 때문에 맨 끝 데이터는 정렬에서 제외됩니다. n회전에서 n개의 데이터가 정렬이 되었다고 판단하기 때문에, 뒤에서 n개의 데이터를 정렬에서 제외합니다. 시간 복잡도 버블 정렬은 최악의 경우에 $O(n^2)$의 시간 복잡도를 가집니다. 버블 정렬은.. 2021. 9. 10. 이전 1 2 다음
