힙 정렬과 스택 정렬, 그리고 값형과 참조형의 연관성
이전에 값형과 참조형에 대해 정리하면서, 데이터가 메모리에 저장되는 방식이 다르다는 것을 알 수 있었다.
값형은 실제 값 자체를 저장하고, 참조형은 실제 데이터가 있는 위치를 참조한다.
이번 글에서는 그 개념을 조금 더 확장해서 힙 정렬과 스택 정렬을 정리해보려고 한다.
여기서 주의할 점은 힙 정렬의 힙(Heap)과 메모리 영역의 힙(Heap)은 이름은 같지만 완전히 같은 개념은 아니라는 것이다.
힙 정렬에서 말하는 힙은 부모와 자식 사이에 규칙이 있는 자료구조이고, 값형과 참조형에서 말하는 힙은 참조형 데이터가 저장되는 메모리 영역을 의미한다.
또한 스택 정렬의 스택(Stack)과 값형에서 자주 언급되는 스택 메모리(Stack Memory)도 이름은 같지만 의미가 다르다.
스택 정렬의 스택은 나중에 들어간 값이 먼저 나오는 자료구조이고, 스택 메모리는 메서드 호출, 지역 변수, 값형 데이터 등이 저장되는 메모리 영역이다.
즉, 정리하면 다음과 같다.
| 힙 정렬의 힙 | 정렬을 위한 자료구조 |
| 참조형에서 말하는 힙 | 객체가 저장되는 메모리 영역 |
| 스택 정렬의 스택 | LIFO 구조를 가진 자료구조 |
| 값형에서 말하는 스택 | 지역 변수 등이 저장되는 메모리 영역 |
그래서 힙 정렬과 스택 정렬을 공부할 때는 단순히 이름만 보고 메모리의 힙, 스택과 같은 개념이라고 착각하면 안 된다.
하지만 둘 사이에 아예 연관이 없는 것은 아니다.
자료구조로서의 힙과 스택은 데이터를 어떤 규칙으로 관리할지에 대한 개념이고, 값형과 참조형에서의 힙과 스택은 데이터가 메모리 어디에 저장되는지에 대한 개념이다.
즉, 둘 다 결국 데이터를 어떻게 다루는가와 관련되어 있다.
이번 글에서는 힙 정렬과 스택 정렬이 각각 어떤 자료구조를 이용하는지, 어떤 방식으로 정렬되는지, 그리고 둘의 차이가 무엇인지 정리해볼 것이다.
1. 힙 정렬이란?
힙 정렬Heap Sort은 힙Heap이라는 자료구조를 이용해서 데이터를 정렬하는 알고리즘이다.
힙은 보통 완전 이진 트리 형태를 가지며, 부모 노드와 자식 노드 사이에 일정한 규칙이 있다.
대표적으로 두 가지가 있다.
최대 힙: 부모 노드가 자식 노드보다 크거나 같다
최소 힙: 부모 노드가 자식 노드보다 작거나 같다오름차순 정렬을 할 때는 보통 최대 힙을 사용한다.
예를 들어 배열이 있다고 하자.
[4, 10, 3, 5, 1]이 배열을 최대 힙으로 만들면 가장 큰 값이 루트, 즉 맨 위로 올라간다.
10
/ \
5 3
/ \
4 1이후 가장 큰 값인 10을 배열의 뒤쪽으로 보내고, 남은 값들로 다시 힙을 만든다.
이 과정을 반복하면 정렬이 완성된다.
2. 힙 정렬의 동작 과정
힙 정렬은 크게 두 단계로 이루어진다.
첫 번째, 배열을 힙 구조로 만든다
배열의 값들을 힙 조건에 맞게 재배치한다.
[4, 10, 3, 5, 1]최대 힙으로 만들면 가장 큰 값이 루트에 온다.
[10, 5, 3, 4, 1]두 번째, 루트 값을 꺼내면서 정렬한다
최대 힙에서는 루트가 가장 큰 값이다.
그래서 루트 값을 배열의 맨 뒤로 보내고, 다시 힙을 정리한다.
[10, 5, 3, 4, 1]10을 맨 뒤로 보낸다.
[1, 5, 3, 4, 10]그리고 10을 제외한 나머지 부분을 다시 힙으로 만든다.
[5, 4, 3, 1, 10]이 과정을 반복하면 최종적으로 오름차순 정렬이 된다.
[1, 3, 4, 5, 10]3. 스택 정렬이란?
스택 정렬Stack Sort은 스택Stack 자료구조를 이용해서 데이터를 정렬하는 방식이다.
스택은 나중에 들어간 데이터가 먼저 나오는 구조이다.
이것을 LIFO라고 한다.
LIFO = Last In, First Out즉, 마지막에 넣은 값이 가장 먼저 나온다.
예를 들어 스택에 다음 순서대로 값을 넣는다고 하자.
1 넣기
2 넣기
3 넣기스택 내부는 이런 느낌이다.
[1, 2, 3]꺼낼 때는 마지막에 넣은 3부터 나온다.
3 → 2 → 1스택 정렬은 이 특성을 이용해서 데이터를 임시로 저장하고, 조건에 맞게 다시 꺼내면서 정렬한다.
4. 스택 정렬의 간단한 예시
스택 정렬은 보통 보조 스택을 하나 더 사용해서 구현한다.
정렬할 데이터가 있다고 하자.
[3, 1, 4, 2]하나의 스택에서 값을 꺼내고, 다른 스택에 정렬된 상태가 되도록 넣는다.
간단히 말하면:
기존 스택에서 값 꺼내기
보조 스택의 값과 비교하기
위치가 맞을 때까지 다시 옮기기
보조 스택에 넣기이런 방식으로 보조 스택 안의 값들이 정렬되게 만든다.
5. 힙 정렬과 스택 정렬의 가장 큰 차이
가장 큰 차이는 사용하는 자료구조이다.
힙 정렬은 힙을 사용하고, 스택 정렬은 스택을 사용한다.
힙 정렬 → 힙 자료구조 사용
스택 정렬 → 스택 자료구조 사용힙은 트리 구조에 가깝고, 스택은 한쪽에서만 데이터를 넣고 빼는 구조이다.
6. 시간 복잡도 차이
힙 정렬의 시간 복잡도는 보통 다음과 같다.
최선: O(n log n)
평균: O(n log n)
최악: O(n log n)즉, 데이터가 많아져도 비교적 안정적인 성능을 가진다.
반면 스택 정렬은 구현 방식에 따라 다르지만, 보통 보조 스택을 이용하는 방식은 최악의 경우 다음과 같다.
O(n²)왜냐하면 값을 넣을 때마다 이미 들어간 값들과 계속 비교하고 옮기는 과정이 생길 수 있기 때문이다.
7. 공간 복잡도 차이
힙 정렬은 배열 자체를 힙처럼 사용해서 정렬할 수 있다.
그래서 추가 공간을 많이 사용하지 않는다.
힙 정렬 공간 복잡도: O(1)물론 구현 방식에 따라 조금 달라질 수 있지만, 일반적인 힙 정렬은 제자리 정렬이 가능하다.
반면 스택 정렬은 보통 보조 스택이 필요하다.
스택 정렬 공간 복잡도: O(n)즉, 데이터 개수만큼 추가 공간이 필요할 수 있다.
8. 안정성 차이
정렬 알고리즘에서 안정성Stable이란 같은 값을 가진 데이터들의 기존 순서가 유지되는지를 말한다.
예를 들어 다음과 같은 데이터가 있다고 하자.
(점수 90, 철수)
(점수 80, 영희)
(점수 90, 민수)점수를 기준으로 정렬했을 때 철수와 민수는 둘 다 90점이다.
정렬 후에도 철수가 민수보다 앞에 있으면 안정 정렬이다.
힙 정렬은 일반적으로 안정 정렬이 아니다.
힙 정렬: 불안정 정렬스택 정렬은 구현 방식에 따라 다르지만, 일반적인 단순 구현에서는 안정성이 보장되지 않는 경우가 많다.
9. 실제 사용 차이
힙 정렬은 컴퓨터 과학에서 대표적인 정렬 알고리즘 중 하나이다.
시간 복잡도가 항상 O(n log n)으로 안정적이기 때문에 알고리즘 공부에서 자주 등장한다.
하지만 실제 프로그래밍에서는 퀵 정렬, 병합 정렬, 팀 정렬 같은 알고리즘이 더 자주 사용되는 경우도 많다.
스택 정렬은 실무에서 일반 정렬 목적으로 많이 쓰이지는 않는다.
보통은 다음과 같은 상황에서 학습용으로 많이 다룬다.
스택 자료구조 이해
보조 자료구조를 이용한 정렬 연습
알고리즘 문제 풀이즉, 힙 정렬은 정식 정렬 알고리즘에 가깝고, 스택 정렬은 스택을 활용한 정렬 문제 해결 방식에 가깝다.
힙 정렬과 스택 정렬 비교표
| 사용하는 자료구조 | 힙 | 스택 |
| 구조 | 완전 이진 트리 기반 | LIFO 구조 |
| 대표성 | 대표적인 정렬 알고리즘 | 표준 정렬보다는 응용 방식 |
| 시간 복잡도 | O(n log n) | 보통 O(n²) |
| 공간 복잡도 | O(1) 가능 | 보통 O(n) |
| 안정 정렬 여부 | 불안정 정렬 | 구현에 따라 다름 |
| 실사용 | 알고리즘에서 중요 | 학습용, 문제 풀이용 |
| 특징 | 큰 값 또는 작은 값을 빠르게 찾음 | 마지막에 넣은 값이 먼저 나옴 |
최종 정리
힙 정렬과 스택 정렬은 모두 자료구조를 이용해 데이터를 정렬한다는 공통점이 있다.
하지만 둘은 사용하는 자료구조와 성능에서 큰 차이가 있다.
힙 정렬은 힙 자료구조를 이용하는 대표적인 정렬 알고리즘이며, 시간 복잡도가 항상 O(n log n)으로 안정적이다. 또한 추가 공간을 거의 사용하지 않고 정렬할 수 있다는 장점이 있다.
반면 스택 정렬은 스택의 LIFO 구조를 이용해 데이터를 정렬하는 방식이다. 보통 보조 스택을 사용하며, 구현 방식에 따라 성능이 달라진다. 일반적인 경우 시간 복잡도는 O(n²)이 될 수 있어, 힙 정렬보다 효율이 떨어지는 경우가 많다.
따라서 정리하면 다음과 같다.
힙 정렬 = 힙을 이용한 대표적인 고성능 정렬 알고리즘
스택 정렬 = 스택을 이용한 정렬 응용 방식그래서 알고리즘 공부에서는 힙 정렬을 정식 정렬 알고리즘으로 배우고, 스택 정렬은 스택 자료구조를 이해하기 위한 응용 예제로 보는 것이 좋다.