[자료구조] stable & unstble sort

Stable sort & UnStable sort

소팅을 할 때 같은 Key 값을 가진 node들이 소팅 전과 소팅 후에 순서가 뒤바뀌게 되면 그것을 unstable sort 라고 하며 순서가 뒤바뀌지 않는다면 그것은 stable sort 라고 한다.

배열이 있으면 해당 노드로 들어온 순서가 있을 것이다. 만약 소팅을 할 때 Key 값을 기준으로 소팅을 하되 같은 Key값을 가진 노드는 들어온 순서에 따라 다시 소팅이 되야 한다는것 -> 이것이 바로 stable이다.

이제 각 정렬 알고리즘별로 stable인지 아닌지를 분류해보자.

1. Bubble Sort

• Stable
• 서로 인접한 두 원소의 대소를 비교하고, 조건에 맞지 않다면 자리를 교환하며 정렬 하는 알고리즘이다.
• 만약 같은 값이 나올 경우 두 수를 변경하지 않고 다음 단계로 넘어가기 때문에 중복되는 수에 대한 key값(들어온 순서) 는 변경되지 않는다. 따라서 stable sort 라고 할 수 있다.

2. Selection Sort

• Unstable
• 해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘 이다.
• 주어진 배열에서 최소값을 찾은 뒤 맨 앞 값이랑 변경한다. 이후 최소값이 결정된 곳은 제외하고 그 다음부터 다시 정렬을 반복한다.
• 예를 들어서 5(1) 4 5(2) 2 3 이런 배열이 있다 치면 최소값으로 인해 2와 첫번째 5의 위치가 변경되게 된다. 이렇게 되면 정렬을 마친 후 5값의 순서가 변경되게 된다. 따라서 unstable sort 이다.

3. Insertion Sort

• Stable
• 2번째 원소부터 시작하여 그 앞(왼쪽)의 원소들과 비교하여 삽입할 위치를 지정한 후, 원소를 뒤로 옮기고 지정된 자리에 자료를 삽입 하여 정렬하는 알고리즘이다.
• 앞에서부터 확인하고 크거나 같은 값이 나올 경우 그 뒤에서 멈추는 알고리즘이기 때문에 순서는 변경되지 않는다. 따라서 stable sort 이다.

4. Quick Sort

• Unstable
• 분할 정복(divide and conquer) 방법 을 통해 주어진 배열을 정렬 하는 알고리즘이다. ```
• [분할 정복(divide and conquer) 방법] 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략이다. ```
• 퀵 소트는 피벗값을 기준으로 피벗보다 낮은 값은 왼쪽 높은 값은 오른쪽으로 분할하면서 정렬하는 알고리즘이다. 예를 들어서 3 5 5 1 3 2(1) 2(2) 5 이런 배열이 있고 피벗이 3이면 정렬을 하였을때 1 2(2) 2(1) 3 3 5 5 5 이렇게 먼저 나온 값은 피벗값과 가까이 위치하게 된다.
• 따라서 퀵소트는 빠르다는 장점은 있지만 stable하지 못하다는 단점이 있다.

5. Merge Sort

• Stable
• 어찌보면 Quick Sort하고 유사할 수 있지만 이 정렬은 피벗값을 기준으로 쪼개는게 아닌 반으로 계속 쪼개 나가는 정렬이다.
• 합병의 대상이 되는 두 영역이 각 영역에 대해서 정렬이 되어있기 때문에 단순히 두 배열을 순차적으로 비교하면서 정렬 할 수가 있다.
• 따라서 Merge Sort 는 앞쪽부터 순서대로 비교해서 정렬되는 것이기 때문에 Stable 하다고 볼 수 있다.

6. Heap Sort

• Unstable
• 완전 이진 트리를 기본으로 하는 힙(Heap) 자료구조를 기반으로한 정렬 방식이다.
• 먼저 주어진 instance를 min heap 으로 구성한 후 root node를 하나씩 pop하는 방식으로 이루어진다.
• 값이 pop될때마다 리프노드에서 값이 하나씩 올라온다. 그렇게 되면 먼저 들어온 노드가 나중에 들어온 노드보다 차수가 높았더라도 어느순간 같아지는 순간이 올 수 있다. 그렇게 되면 root->left == root->right 이렇게 되고 left가 right보다 나중에 들어온 node가 될 수도 있다. 따라서 나중에 들어온 node가 먼저 pop되는 상황이 발생하게 된다. 따라서 힙 소트는 Unstable 하다고 볼 수 있다.

Summary

• 그림으로 설명하면 더 좋을 것 같지만 저는 그러지 못했습니다… Reference 를 확인해주시면 감사하겠습니다.

Reference

naver 블로그

baeldung

규글님 블로그