Java 코테 핵심이론 (버블정렬, 선택정렬)

04 정렬

정렬에는 버블정렬, 선택정렬, 삽입정렬, 퀵정렬, 병합정렬, 기수정렬등이 있음.

 

4-1 버블 정렬

버블 정렬은 인접한 데이터의 크기를 비교해 정렬하는 방법으로 구현은 간단하지만 시간복잡도가 O(n^2)로 다른 정렬보다 느린 편이다. loop를 돌면서 인접한 데이터끼리 swap해서 정렬한다.

 

버블 정렬 과정

1. 비교 연산이 필요한 루프 범위를 설정하고 인접한 데이터 값을 비교한다.
2. swap 조건에 부합하면 swap 연산을 수행한다.
3. 루프 범위가 끝날 때까지 위를 반복한다.
4. 정렬 영역을 설정하고 다음 루프를 실행할때는 이 영역을 제외한다 (이미 정렬된 영역임)
5. 비교 대상이 없을 때 까지 위를 계속 반복한다.

만약 특정한 루프의 전체 영역에서 swap이 한 번도 발생하지 않았다면 그 영역 뒤에 있는 데이터가 모두 정렬됐다는 뜻이므로 프로세스를 종료해도 됩니다.

 

 

4-2 선택 정렬

코테에서 빈번하게 나오진 않지만 어떤 문제 일부로 나오거나 기술면접에서 물어 볼 수 있음.

대상 데이터에서 최대나 최소 데이터를 찾아가며 선택하는 방법이다. 시간 복잡도는 O(n^2)이다.

 

선택 정렬 과정

1. 남은 정렬 부분에서 최솟값 또는 최댓값을 찾고 남은 정렬 부분중 가장 앞에 있는 데이터와 swap한다.
2. 가장 앞에 있는 데이터의 위치를 변경해 (index++) 남은 정렬 부분의 범위를 축소한다.
3. 남은 정렬 부분이 없을 때 까지 반복한다.