정렬(Sort)

정렬은 데이터를 정해진 기준에 따라 배치해 의미 있는 구조로 재설정하는 것을 말한다.

안정정렬과 불안정 정렬

안정정렬

정렬을 수행하고 난 뒤에도 같은 key값을 가진 원소들의 순서가 유지되는 정렬

불안정 정렬

정렬을 수행하고 난 뒤에도 같은 key값을 가진 원소들의 순서가 보장되지가 않는다.

정렬 알고리즘의 종류

1. 버블정렬

데이터의 인접 요소끼리 비교하고, swap 연산을 수행하며 정렬하는 방식

시간복잡도를 계산하면,O(n^2) 이다. 또한, Bubble Sort는 정렬이 돼있던 안돼있던, 2개의 원소를 비교하기 때문에 최선, 평균, 최악의 경우 모두 시간복잡도가 O(n^2) 으로 동일하다.

버블 정렬 과정
1. 비교 연산이 필요한 루프 범위를 설정
2. 인접한 두 개의 데이터 값을 비교한다
3. Swap조건(내림차순 / 오름차순)에 부합하면 Swap한다.
4. 루프 범위가 끝날 때까지 2~3번 과정을 반복한다.
5. 정렬 영역을 설정한다. 다음 루프를 실행할 때는 이 영역을 제외한다.
6. 비교 대상이 없을 때까지 1~5번 과정을 반복

장점

• 구현이 매우 간단하고, 소스코드가 직관적이다.
• 정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않다. => 제자리 정렬(in-place sorting)
• 안정 정렬(Stable Sort) 이다.

단점

• 시간복잡도가 최악, 최선, 평균 모두 O(n^2)으로, 굉장히 비효율적이다.
• 정렬 돼있지 않은 원소가 정렬 됐을때의 자리로 가기 위해서, 교환 연산(swap)이 많이 일어나게 된다.

2. 선택정렬

대상 데이터에서 최대나 최소 데이터를 데이터가 나열된 순으로 찾아가며 선택하는 방법이다.
선택 정렬은 구현 방법이 복잡하며, 시간 복잡도도 O(n^2)로 효율적이지 않아 코팅테스트에서는 많이사용되지 않는다

선택정렬은 최솟값 또는 최댓값을 찾고, 남은 정렬 부분의 가장 앞에 있는 데이터와 swap하는것이 선택정렬의 핵심이다/

선택 정렬 과정
1. 남은 정렬부분에서 최소값 또는 최대값을 찾는다.
2. 남은 정렬 부분에서 가장 앞에 있는 데이터와 선택된 데이터를 swap 한다.
3. 가장 앞에 있는 데이터의 위치를 변경해 남은 정렬 부분의 범위를 축소한다.
4. 전체 데이터 크기만큼 index가 커질때 까지, 즉 남은 정렬 부분이 없을때 까지 반복한다.

장점

• 선택정렬 또한 버블정렬과 마찬가지로 구현이 쉬운편에 속하는 정렬법이다.
• 정렬을 위한 비교 횟수는 많지만 실제로 교환하는 횟수는 적기 때문에 많은 교환이 일어나야 하는 자료상태에서 효율적으로 사용될 수 있다.
• 버블정렬과 비교했을 때, 똑같이 O(n^2)이라는 시간복잡도를 갖지만, 실제로 시간을 측정해보면 버블정렬에 비해서는 조금 더 빠른 정렬 방식이다.

• 안정 정렬(Stable Sort) 이다.

단점

• 선택정렬 또한 항상 O(n^2)이라는 시간복잡도를 갖기 때문에 시간이 오래걸리는 정렬 방식이다.