버블정렬, 삽입정렬, 퀵정렬, 병합정렬

버블정렬 (Bubble Sort)

1) 앞뒤로 데이터를 비교하며 가장 큰 데이터를 가장 뒤로 보내며 정렬하는 방식이다. 거품이 보글보글 올라가는 모습과 비슷하다.

2) 가장 구현하기 쉬우나 비효율적인 알고리즘이다.

3) 네이버 지식백과 [버블정렬] 참조

삽입정렬 (Insert Sort)

1) 아직 정렬되지 않은 임의의 데이터를 이미 정렬된 부분의 적절한 위치에 삽입해 가며 정렬하는 방식이다.

2) 정렬된 위치에 삽입하는 방식은 LinkedList를 통해 쉽게 구현할 수 있다. 만약 ArrayList를 사용할 경우 삽입시 모든 원소를 한칸씩 이동하여야 하기 때문에 비효율적이고 속도가 느리다.

3) 네이버 지식백과 [삽입정렬] 참조

퀵정렬 (Quick Sort)

1) pivot값을 기준으로 작은 값은 앞으로, 큰 값은 뒤로 가도록 하여 작은 값과 큰 값을 서로 분리해가며 정렬하는 방식이다.

2) 이 알고리즘은 재귀(recursive)적이다.

3) 버블정렬이나 삽입정렬보다 훨씬 효율적인 성능을 발휘한다.

4) 네이버 지식백과 [퀵정렬] 참조

병합정렬 (Merge Sort)

1) 분할정복(Divide and Conquer) 알고리즘이다.

2) 여러개의 데이터를 재귀적으로 반으로 나누어 정렬처리하며, 최종적으로 결합(Combine)을 하는 방식이다.

※ 참고자료

- 자바 프로그래밍 면접, 이렇게 준비한다