Algorithm › 여러 정렬 알고리즘에 대해(Week1_Day3)

오늘은 정렬에 대해서 공부를 해보았다.

정렬

정렬은 말그대로 오름차순 내림차순 등의 정렬이다. 그 중 같은 데이터의 순서가 유지되는 정렬은 안정적인 정렬 그렇지 못하면 안정적이지 않은 것이다. 원소를 비교하고 교환하는 과정을 패스라고 한다.

버블정렬

거품이 올라오는 것과 같이 정렬된다고 해서 버블정렬이라고 부른단다. 오름차순 정렬을 기준으로 끝원소에서 첫번 째 원소까지 두 개씩 비교하면서, 작은 원소를 왼쪽으로 자리를 바꿔가는 정렬 방법이다. 그렇게 n - 1번 정렬을 수행하면 (마지막 원소는 비교할 것 없이 이미 정렬 된 것이나 마찬 가지니까)완료된다. 하지만 이 때 무조건 n - 1번 수행을 한다면 쓸데없는 반복을 하게 될 수 있다. 만약 중간 단계의 패스에서 이미 정렬이 완료되었다면 더 이상 정렬을 할 필요가 없기 때문이다. 이걸 확인 하기 위해 각 패스별 교환 횟수를 기록 할 수 있는 변수를 추가하여 마지막 패스 종료 시 교환 횟수가 0이면 종료하도록 하여 개선 할 수 있다. 여기서 더 개선을 하려면 일단 첫 번째 패스를 수행 한 이후, 이 때 마지막 교환이 일어난 곳을 기록해 둔다면 그 원소보다 앞쪽에 있는 원소들은 정렬이 되어있기 때문에 더 이상 수행하지 않아도 된다. 이를 이용해 다음 패스 부터는 마지막 교환 위치까지는 제외하고 정렬을 수행하는 것이다. 이를 바탕으로 개선한 것이 셰이커 정렬이다.

• 셰이커 정렬

  홀수 패스에서는 가장 작은 원소를 맨 앞으로 이동, 짝수 패스에서는 가장 큰 원소를 맨 뒤로 이동시키며 번갈아가면서 정렬을 진행해서 비교 횟수의 감소를 꾀하는 방법이다. 물론 이때도 마지막 교환위치를 기억하는 방법은 똑같이 유지한다.

단순선택정렬

이름처럼 단순하게 가장 작은 원소를 선택해서 원하는 위치로 옮기는 정렬 방법이다. 이를 좀 더 상세히 생각하면 정렬되지 않은 범위에서 가장 작은 원소를 선택하고, 정렬 하지 않은 부분의 맨 앞의 원소와 교환하는 것이다. 이 방법은 이웃하지 않은 원소를 정렬하기 때문에 안정적이지 못한 방법이다.

단순삽입정렬

선택한 원소를 더 앞쪽에서 알맞은 위치에 삽입하는 정렬법이다. 이렇게만 말하면 이걸 어떻게 하라는건가 싶지만, 1번 인덱스부터 시작해서 선택한 값을 temp로 저장해놓고, 왼쪽의 이웃 원소가 선택 값보다 크다면 선택 값의 자리에 왼쪽의 이웃 원소를 삽입하고, 앞으로 진행하면서 반복한다. 그러다 더 작은 원소를 만나게 되면 그 자리에 선택값을 다시 삽입한다. 하지만 이는 시간복잡도가 O(n^2)으로 좋지 않기 때문에, 이진 탐색을 이용해서 삽입할 위치를 찾음으로 개선할 수 있다. 이를 이진삽입 정렬이라고 부른다. 이웃 원소를 정렬하기 때문에 안정적이다.

• 이진삽입정렬

  선택 값을 삽입 할 위치를 찾는과정에서 이진탐색을 사용하여, 탐색 범위를 반으로 줄여서 진행하는 정렬법이다. 정확히는 검색 범위의 반 보다 아래인지 위인지를 나눠서 생각을 하는 것이다.

셸정렬

단순삽입정렬의 삽입 할 위치가 멀리 떨어져있으면 이동 횟수가 많아진다는 단점을 보완하기 위해 만들어진 방법으로, 서로 h칸 씩 떨어진 위치의 원소끼리 그룹을 만들어 크기를 비교하고 이동한다. h를 줄여가면서 이를 반복하고, 마지막에는 정렬에 가까워진 형태가 되어 단순삽입정렬을 1회 수행하면 정렬이 완료되는 개념이다. 이 때 h값의 선택이 성능에 영향을 미치는데, h값이 서로 배수가 되게 되면 각각의 그룹이 서로 섞이지 않게 되기 때문에 원소를 더 효율적으로 정렬하기가 어려워진다. 대표적으로 Hibbard 방식이 있는데, 1부터 시작하여 3배한 값이 1을 더하는, 즉 수식으로 2^i - 1이 되게 하는 방법이다. 허나 h의 초기 값이 지나치게 크면 효과가 없기 때문에, 예제에서는 배열의 원소 수 n을 9로 나눈 몫보다 작은 값으로 제한을 두었는데 이는 sedgewick 간격과 관련이 있다고 한다.(시간관계상 넘어간 부분)

퀵정렬

일반적으로 가장 빠른 정렬 알고리즘으로 알려져 있다. 특정 기준을 정해서 정렬 할 리스트를 기준보다 작거나 큰 2개의 그룹으로 나누는 것을 반복하여 모든 그룹이 하나의 원소를 가지면 정렬이 완료되는 개념이다. 왼쪽 커서와 오른쪽 커서가 서로 가운데로 이동하며 왼쪽커서는 기준값보다 큰 값을 찾을 경우, 오른쪽 커서는 기준값보다 작은 값을 찾을 경우 서로 교환하여 정렬을 하고 왼쪽 커서와 오른쪽 커서가 교차되었을 때 그룹 나누기가 완료되는 것이다. 이 때 왼쪽 커서와 오른쪽 커서가 기준값에서 만나는 경우가 있는데 이 때도 불필요하지만 교환을 해준다. 이때 교환을 하지 않기 위해 매번 같은 위치에 있는지 체크 하는 것 보다 1번 교환 하는게 비용이 적게 들기 때문이다. 이를 완료하고, 왼쪽 그룹과 오른쪽 그룹에 대해서 재귀 호출을 해주면 퀵 정렬 알고리즘이 완성되는 것이다. 물론 이는 불안정한 정렬이다.

병합정렬

병합 정렬은 배열을 앞부분과 뒷 부분으로 나누어 각각 정렬 한 후 병합 하는 개념이다. 이게 무슨 뜻이냐면, 가운데을 기준으로 나눈다고 생각했을 때, 앞쪽 배열의 인덱스 i와 뒷쪽 배열의 인덱스 k에 대해서 해당 인덱스의 원소의 크기를 비교하고 작은 원소를 새로운 배열에 추가하고, 해당 인덱스를 1증가시켜 다음 원소를 가리키게 하는 방식으로 진행된다. 이렇게 앞,뒤 배열에서 크기순으로 새로운 배열에 원소를 넣다 보면, 둘 중 한 배열이 바닥나게 된다. 이때, 나머지 배열의 원소를 새로운 배열에 추가하면 정렬이 완료되는 것이다. 이 방법은 이웃원소를 정렬하기 때문에 안정적 정렬이다.

이후 힙 정렬과 도수 정렬이 있지만 아직 힙과 스택을 공부하지 않아서 남겨뒀다. 내일은 빅오표기법과 시간복잡도에 대해 공부했던 내용을 정리해 볼 생각이다.