Sort
정렬은 데이터들이 있을 때 이를 정해진 순서대로 나열하는 문제이다.
컴퓨터 분야에서 다양한 데이터, 문제에는 데이터의 정렬이 필요한 경우가 아주 많은데 이를 효율적으로 해결하기 위한 알고리즘이다.
이제는 C++ STL이나 파이썬 내장 함수를 비롯해서 언어 대부분에 sort 기능이 구현이 되어있기 때문에 문제 풀 때 정렬을 구현하는 일은 거의 없다.
특정 조건에 따른 정렬이 필요하다면 bool compare 비교 함수만 위에 만들어서 sort 함수 안에 넣어주면 되기 때문이다.
그래도 정렬은 많은 문제에 사용되는 근본적인 알고리즘이기 때문에 어느정도 정리가 필요하다는 생각이 들었다.
가장 처음 정렬을 배울 때 O(N^2)인 버블, 삽입, 선택 정렬을 알려주는데 현실에서 쓸 일이 거의 없다.
O(NlogN)인 퀵과 병합 정렬, 힙 정렬이 존재하기에 대부분의 경우에서 안 좋은 알고리즘을 사용할 이유가 없기 때문이다.
또 이런 정렬들을 하이브리드로 합쳐서 사용하는 현재 라이브러리에 구현되어 있는 정렬은 어떤 것인지 봐야겠다.
O(N^2)인 정렬
버블 정렬
정렬 과정에서 데이터가 이동하는 모습이 마치 물속의 거품이 위로 올라오는 것과 같다고 해서 버블 정렬이다.
방법은 맨 앞부터 시작해서 1번째와 2번째, 2번째와 3번째.. n-1번째와 n번째를 순서대로 비교하며 정렬한다.
이렇게 한 번 돌고나면 가장 큰 값이 n번째에 들어가기에 다음 사이클에서는 처음부터 n-2번째 <-> n-1번째 까지만 비교한다.
이렇게 모든 사이클을 돌아 정렬을 하고 시간은 n(n-1)/2가 걸리게 된다.
매번 swap을 하기 때문에 O(N^2)인 정렬 알고리즘 중에서도 보통의 경우 가장 느리다.
선택 정렬
모든 데이터를 쭉 돌면서 가장 작은 값을 선택해서 그걸 1번째에 넣고, 다시 2번째부터 끝까지 돌면서 가장 작은 값을 찾고..
를 반복한다. 역시 n(n-1)/2번 정도의 연산을 하게 된다.
조금 더 개선을 시켜보면 일단 모든 데이터를 돌며 최솟값을 찾는 것이기에, 이 때 최솟값과 최댓값을 둘 다 찾은 다음
최솟값은 맨 앞으로, 최댓값은 맨 끝으로 보내면 연산 횟수를 반으로 줄일 수는 있다.
삽입 정렬
사람이 정렬을 할 때 자연스럽게 사용하는 방법인 것 같고, 정렬되지 않은 원소부분에서 값을 하나 골라 정렬된 부분과
조건을 비교해서 적절한 위치에 삽입하는 과정을 반복해서 정렬한다.
1~k번째 까지 정렬이 되어있다면 k+1번째 원소를 정렬된 부분에 집어 넣는 것이다.
이 때 이분 탐색을 사용하면 O(logk)에 삽입할 곳을 찾을 수 있지만 삽입하며 뒤의 데이터를 밀어내야 하기 때문에
O(N)의 시간이 소요 된다.
이미 정렬이 되어 있는 배열에서 데이터를 삽입하거나 삭제할 때는 가장 좋은 효율을 보이고 O(N^2) 알고리즘 중에서
데이터의 조건(정렬이 어느정도 되었는지, 데이터의 크기가 작은지)에 따라서 꽤나 좋은 효율을 보여주는 정렬 방법이다.
안정 정렬과 불안정 정렬
만약 같은 값을 가진 데이터가 있을 때는 어떻게 정렬을 해야할까?
같은 값일 때 입력 받은 순서를 지켜서 정렬을 하면 안정(stable)정렬, 무시하면 불안정(unstable) 정렬이라고 부른다.
대표적으로 삽입 정렬, 병합 정렬 등이 stable하고 선택 정렬, 힙 정렬은 unstable 하다.
예를 들어 두 가지의 key를 기준으로 정렬한다면 맨 처음 key로 정렬을 하고 다음 key로 정렬 할 때 앞의 정렬이 깨지면
안되기 때문에 이 때는 stable한 정렬을 사용해야 하므로 데이터와 상황에 따라서 구분해서 사용을 해야한다.
배열에서의 search와 insert, delete
따로 글 하나를 쓰기는 애매한 내용인데 있으면 좋을 것 같아서 추가적으로 적는 내용
우선 search, insert, delete는 자료구조에 있어서 가장 중요한 연산이다.
크게 배열을 4가지 상태로 나눠 수행하는 방법을 볼 수 있다.
- Packed vs Unpacked (값이 모여 있는지)
- Sorted vs Unsorted (값이 정렬되었는지)
Packed and Sorted
index [0][1][2][3][4][5][6]
value [1][3][4][5][6][X][X]
값이 모여있고 정렬이 되어 있는 배열로 X는 빈 공간이다.
가장 자주 볼 만한 조건으로 값이 모여있고, 정렬이 되어있다.
search는 이분 탐색으로 찾을 수 있으므로 O(logN)
insert는 삽입 될 공간은 이분 탐색으로 찾지만 값을 넣을 때 뒤의 value를 밀어야하므로 O(N)
delete도 지울 데이터의 위치는 이분 탐색으로 찾지만 삭제할 때 값을 당겨야하므로 O(N)이다.
Packed and Unsorted
index [0][1][2][3][4][5][6]
value [5][3][6][7][4][X][X]
값은 모여있지만 정렬은 안 되어 있는 배열이다.
search는 정렬이 안 되어있으면 선형 탐색밖에 할 수 없기에 O(N)
insert는 위의 배열을 기준으로 보면 빈 공간인 index 5에 넣으면 되므로 O(1)이다.
delete도 값을 지운 다음 (예를 들어 value 6을 지운다고 하면) index 2가 지워지고 가장 뒤의 값인 index 4를
빈공간인 index 2에 옮기면 된다. 그러면 삭제 자체는 O(1)만에 할 수 있다.
하지만 delete할 때 특정 값을 지운다고 하면 search가 동반될 것이기에 O(N)만큼이 사전에 소요된다.
Unpacked and Sorted
Unpacked는 사용하지 않는 값을 Mark 배열로 확인하는 형태로 저장된다.
index [0][1][2][3][4][5][6]
value [1][3][4][5][6][8][9]
mark [O][O][X][O][O][X][O]
mark 배열이 X라는 것은 지워진 값으로 볼 수 있다.
search는 배열이 정렬되어 있기에 지워진 값을 포함해도 이분 탐색으로 찾을 수 있으므로 O(logN)
insert는 삽입 될 공간은 이분 탐색으로 찾고 만약 value에 값은 있는데 mark가 X인 상태면 mark를 O로 바꾸면 된다.
위의 경우에는 search한 다음 O(1)로 처리할 수 있지만 value에 없다면 packed and sorted와 똑같이 뒤의 데이터를 밀어야한다.
그러므로 O(N)이 소요된다.
delete는 지울 데이터의 위치는 이분 탐색으로 찾고서 mark 배열의 값을 O에서 X로 바꾸면 되므로 search 후 O(1)에 처리한다.
Unpacked and Unsorted
index [0][1][2][3][4][5][6]
value [5][3][6][7][4][9][8]
mark [O][O][X][O][O][X][O]
값도 떨어져있고 정렬도 안되어 있는 배열이다.
search는 효율적인 방법이 없이 전부 봐야하므로 O(N)
insert는 삽입할 위치인 mark가 X인 곳을 찾아야 하는데 이 때 사용할 수 있는 테크닉이 있다.
head라는 변수를 하나 만들어서 mark가 X인 가장 앞의 index를 저장한다. (예시에서는 2)
그 다음 index 2의 value에는 다음 mark가 X인 index를 저장한다.(예시에서는 5)
그러고서 index 5 다음의 mark가 X인 곳은 없으므로 value에 -1을 저장한다.
이렇게 chain으로 관리하면 다음에 insert할 곳을 O(1)만에 관리할 수 있게 된다.
index [0][1][2][3][4][5][6]
value [5][3][5][7][4][-1][8]
mark [O][O][X][O][O][X][O]
insert 연산을 할 때 원래 head값에 index head에 저장되어있는 value를 넣고, index head value에 삽입할 값을 넣는다.
그러고서 mark 배열을 O로 바꿔주면 된다. 이러면 O(1)만에 insert가 가능하다.
그러면 delete는 mark 배열과 chain을 연결해주는 것만 신경써주면 된다.
value 3을 지운다고 하면 search를 통해서 우선 찾고,
index [0][1][2][3][4][5][6]
value [5][3][5][7][4][-1][8]
mark [O][O][X][O][O][X][O]
의 배열에서 index 1의 값을 지우는 것이므로 -1로 되어있는 곳을 찾아서 1을 넣어주고, index 1의 value을 -1로 바꾼다.
이러면 mark가 X인 chain을 관리할 수 있게 되고, index 1의 mark를 X로 바꿔주면 된다. 이 역시 O(1)의 연산이다.
[변경]
index [0][1][2][3][4][5][6]
value [5][-1][5][7][4][1][8]
mark [O][X][X][O][O][X][O]
insert, delete의 시간 복잡도는 사전에 걸리는 search의 시간은 제외하고 정리한 것에 주의하자.
다음은 O(NlogN) 정렬과 하이브리드 방법을 알아보자.