[JAVA] 기본적인 정렬 알고리즘

이 글은 개인의 학습을 목적으로 정리한 글입니다. 이점 참고하고 읽어주세요;)

---

프로그래밍에 있어 정렬(sort)은 정말 중요합니다. 데이터를 찾거나, 분류하거나, 추가하거나, 등등 대부분의 작업에서 정렬은 거의 필수로 가져가는 기능입니다. 이번 포스팅에서는 기본적인 정렬 알고리즘에 대해 알아보겠습니다.

 

정렬 알고리즘의 종류

---

1. Selection sort

가장 큰 값을 맨 끝에 위치한 데이터와 교체하는 게 selection sort의 기본적인 아이디어입니다.

가장 큰 값은 맨 끝자리에 오게 되고, 가장 큰 값은 다음 비교에서 제외합니다.

selection sort는 모든 비교연산에 대해 n^2의 시간 복잡도를 가지게 됩니다.

---

Bubble sort는 가장 큰 값을 맨 뒤에 위치시킨다는 점에서 Selection sort와 동일하지만, 가장 큰 값을 맨 뒤로 이동하는 방식이 selection sort와 차이점을 보입니다.

bubble sort 역시 데이터의 크기에 관계 없이 n^2의 시간 복잡도를 가지게 됩니다.

---

1) 12를 15 앞으로 끼워 넣으면 정렬된 상태

2) 13을 끼워넣어 3개의 데이터를 정렬하려면 12와 15 사이에 13을 끼워 넣어 정렬된 상태

..

 

key1. 이미 k-1 번째 데이터까지 정렬이 되어있을 때, k번째 데이터를 어디에 추가하면 k번째 데이터까지 정렬된 상태를 유지할 수 있을 것인지

 

key2. 위의 예시에서 4를 앞의 데이터들과 비교할 때 두 가지 방법이 있습니다.

앞에 있는 2부터 차례로 4를 비교할 것인지, 아니면 가장 뒤에 있는 8부터 비교할 것인지 이렇게 두 가지 방법입니다.

얼핏 보면 앞에서 비교하나 뒤에서 비교하나 동일해보일 수 있지만, 4를 insert 함으로서 4보다 큰 멤버들을 한 칸 씩 뒤로 미뤄줘야한다는 점을 생각해보면 그렇지 않습니다.

4를 앞에서부터 비교한다면 4보다 작은 2와 3과 비교를 한 다음, 5의 자리에 4를 삽입하기 위해 5부터 8까지의 데이터들을 한 칸씩 뒤로 미뤄줘야하기 때문입니다. 이 말은 즉, 4라는 값을 4보다 큰 5부터 8까지의 값들과 비교할 필요가 없더라도 배열에서의 이동을 위해 5부터 8까지의 값을 한 번씩은 건드려야 한다는 말입니다.

반면 4를 가장 큰 값인 8부터 비교하게 되면, 4보다 작은 값이 처음 등장하는 3까지만 4보다 큰 값들을 한 칸씩 뒤로 미뤄주면서 비교를 하면 앞에 있는 2는 비교 연산에서도, 4를 배열에 삽입하는 연산에서도 건드릴 일이 없어져 컴퓨터의 연산의 부담을 덜어줍니다.

 

key3. 삽입하려는 4는 임시 변수인 tmp에 저장한 다음 k-1번째 데이터와 비교를 시작합니다. 4의 자리에는 비교를 마친 8이 한 칸 뒤로 이동하기 때문입니다.

Insertion Sort의 시간 복잡도는 최악의 경우에만 n^2의 시간 복잡도를 가지게 됩니다.

때문에 평균적으로는 bubble sort나 selection sort보다 좋은 효율을 가지게 됩니다.