정렬의 안정적 특성
정렬의 안정적 특성은 정렬되지 않은 상태에서 같은 키 값을 가진 원소의 순서가 정렬 후에도 유지되는 것이다.
여기서 정렬 후에도 순서가 보장 되는 것이 안정 정렬, 되지 않는다면 불안정 정렬로 구분할 수 있다.
만약 우리가 포커 카드 4장을 숫자 크기로 정렬한다. 하지만 같은 값을 가진 모양이 다른 카드가 있다.
예를 들어 하트5 | 스페이스5가 있는데 정렬을 하게 되면 안정 정렬은 하트5 | 스페이스5로 같은 키 값을 가진 카드의 순서가 보장된다.
하지만 불안정 정렬은 스페이스5 | 하트5로 정렬되고 같은 키 값을 가진 카드들의 순서가 보장되지 않는다.
선택정렬
정렬에 대해 설명하면서 배열을 기준으로 설명하므로 0번 째가 제일 먼저 있는 원소라고 가정하겠다.
배열에서 가장 작은 값을 찾아 저장하고, 0번 째 원소부터 비교하여 작은 값부터 오름차순으로 정렬하는 방법이다.
- 배열 중 최소값을 찾는다.
- 그 값을 맨 앞에 위치한(0번 째) 원소와 index를 교체한다.
- 0번 째를 제외한 배열 원소 중 최소값을 찾는다.
- 1번 째에 위치한 원소와 교체한다.
- 위 과정을 반복한다.
사실 글로 설명하는 것보다 사진이나 동영상으로 이해하는 것이 훨씬 쉽다.
선택정렬의 장점
- 알고리즘이 단순하다.
- 배열 안에서 교환하는 방식(제자리 정렬)이므로 별도의 배열이 필요하지 않아 메모리 공간이 더 필요하지 않다.
선택정렬의 단점
- 최선, 평균, 최악의 시간복잡도가 모두
O(n^2)로 비효율적이다. 불안정 정렬이다.
버블정렬
배열의 0번 째 원소부터 1번 째 원소의 값을 비교하여 큰 값이 계속해서 뒤로 밀려난다. 배열의 0번 째 부터 정렬됐던 선택졍렬과 달리 배열의 끝에서 부터 정렬이 된다.
- 배열의 0번 째 원소와 1번 째 원소를 비교한다.
- 0번 째가 1번 째 값보다 크다면 0번 째 값이 1의 index와 교체된다.
- 1번 째 원소가 2번째 원소보다 작으면 아무 일도 일어나지 않는다.
- 2번 째 원소와 3번째 원소와 비교하고 2번째 원소가 더 크다면 둘의 위치를 바꾼다.
- 위 과정을 반복한다.
버블정렬의 장점
- 알고리즘이 단순하다.
- 배열 안에서 교환하는 방식(제자리 정렬)이므로 별도의 배열이 필요하지 않아 메모리 공간이 더 필요하지 않다.
안정 정렬이다.
버블정렬의 단점
- 정렬 돼있지 않은 원소가 정렬 됐을때의 자리로 가기 위해서, 교환 연산(swap)이 많이 일어나게 된다.
- 최선, 평균, 최악의 시간복잡도가 모두
O(n^2)로 비효율적이다.
삽입정렬
삽입 정렬은 여러 개의 섞인 숫자가 있을 때, 그 숫자를 작은 순서부터 큰 순서로 정렬 하는 것이다. 삽입 정렬은 1번 째 자리 숫자부터 뽑아서 그 숫자가 0번 째보다 크면 1번 째 오른쪽에, 작으면 왼쪽에 넣는다. 2번 째 자리 숫자를 뽑아서 앞의 두 숫자와 크기를 비교해서 알맞은 자리에 넣는다. 이렇게 끝까지 계속하면 정렬된다.
- 1번 째 원소를 저장한다.
- 0번 째 원소와 크기를 비교하고 1번이 더 크면 0번과 index를 바꾼다.
- 1번 째 원소와 2번 째 원소의 크기를 비교하고 2번 째가 더 작다면 1번과 index를 바꾼다.(만약 2번 째가 더 크다면 바꾸지 않고 그대로 있는다.)
- 위 과정을 반복한다.
삽입정렬의 장점
- 알고리즘이 단순하다.
- 대부분의 원소가 이미 정렬되어 있는 경우(
최선의 경우O(n)), 매우 효율적일 수 있다. - 배열 안에서 교환하는 방식(제자리 정렬)이므로 별도의 배열이 필요하지 않아 메모리 공간이 더 필요하지 않다.
- 안정 정렬이다.
- 선택정렬과 버블정렬에 비해 상대적으로 빠르다.
삽입정렬의 단점
- 평균과 최악의 시간복잡도가 O(n^2)으로 비효율적이다.
- 버블 정렬와 선택 정렬과 마찬가지로, 배열의 길이가 길어질수록 비효율적이다.
Reference
느리지만 확실하게