#C2 [정보처리기사] 정렬에 대하여

정보처리기사 정리글입니다.
2021 시나공/수제비 정보처리기사 필기 책 기반 작성하되, 주관적인 해석을 첨가하였습니다.

 

'시간복잡도'나 '빅오 표기법'이 어색한 분들은 시간복잡도 - 실생활 예시로 개념잡기를 추천드립니다.

 

0. 필기 문제 예시(요약)

• (중) 다음 자료에 대하여 00 정렬 2회전 후 결과는?
• (중) 시간 복잡도 O(N^2)의 시간이 소요되는 정렬 알고리즘은? 
• (중) 00 정렬의 시간 복잡도는?
• (상) 00 정렬에 대한 설명으로 틀린 것은?

다양한 영역에서 출제되고 있다.

 

1. 혼자 궁금했던 것

머릿속에 알고리즘에 대한 개념이 없을 때, '모든 정렬에 그냥 시간복잡도가 가장 낮은 알고리즘을 사용하면 안되나?'라는 생각을 했었다.

좀 더 공부해보니 정렬 알고리즘을 선택하는 요인에는 시간복잡도 말고도 크게 2가지가 더 있었다.

1. 공간복잡도 - 해당 정렬 로직을 수행하는 동안 사용하는 자원의 양으로 선택정렬의 경우 n이 커짐에 따라 변수가 추가되거나 하는 등 메모리 공간을 더 사용하지 않는다. 따라서 선택정렬은 공간복잡도가 O(1)이며 제한된 메모리자원에서 사용하기 좋은 정렬방식이다.
2. 데이터 특성(데이터의 정렬정도) - 실무에서는 다양한 데이터 특성에 따른 정렬 알고리즘이 요구될텐데, 이 데이터 특성에 따라서도 정렬 로직을 선택해야한다. 예를들어 정렬이 거의 완료된 데이터 나열이 있다고 하자. (1 2 3 4 5 6 8 7 9 10) 우리는 이 데이터가 '거의' 정렬된 상태라는 것을 알고 일부 정렬이 덜 된 수들을 정렬하고 싶다. 이럴 때 무턱대고 O(NlogN)인 퀵정렬을 사용하면 logN으로 분할하는 이점을 가져오기 힘들고 오히려 삽입 정렬로 정렬하는 것이 시간적 물리적 자원에 유리하다.

 

2. (중) 문제 대비 상세 정렬 로직 외울 것들

중 문제는 이 표 선에서 정리가능

• 기출 몇 개 풀어보니 n^2 복잡도 3형제가 가장 많이 나오더라.. 그래서 상세 정렬 로직은 위 3개만 학습

1. 삽입 정렬

71493 시작

1회전 : 2번째 값 (1)을 7과 비교하여 삽입 → 17493

2회전 : 3번째 값 (4)를 1,7과 비교하여 삽입 → 14793

3회전 : 4번째 값 (9)를 1,4,7과 비교하여 삽입 → 14793

4회전 : 5번째 값 (3)을 1,4,7,9와 비교하여 삽입 → 13479

 

2. 선택 정렬

 - 위 표에는 'n개 레코드 중 최솟값을 찾아 첫 번째에 놓고 ...' 라고 되어있다. 이는 개념적으로 n회전 정렬 후 n번째 자리의 값까지 정렬이 됐음을 의미할 뿐이다. 각 회전간 상세 정렬 로직을 알아보자

71493 시작

1회전 : 1번 자리의 최소값을 찾는 상세 과정

1번(7)과 2번(1)을 비교하여 작은 값을 1번에 둠 → 17493

1번(1)과 3번(4)을 비교하여 작은 값을 1번에 둠 → 17493

1번(1)과 4번(9)을 비교하여 작은 값을 1번에 둠 → 17493

1번(1)과 5번(3)을 비교하여 작은 값을 1번에 둠 → 17493

 --  1번 값 정렬 완료  --

 

2회전 : 2번 자리의 최솟값을 찾는 상세 과정

1회전 후 값인 17493 시작

2번(7)과 3번(4)을 비교하여 작은 값을 2번에 둠 → 14793

2번(4)과 4번(9)을 비교하여 작은 값을 2번에 둠 → 14793

2번(4)과 5번(3)을 비교하여 작은 값을 2번에 둠 → 13794

 --  2번 값 정렬 완료  --

 

3회전 : 3번 자리의 최소값을 찾는 상세 과정

2회전 후 값인 13794 시작

3번(7)과 4번(9)을 비교하여 작은 값을 3번에 둠 → 13794

3번(7)과 5번(4)을 비교하여 작은 값을 3번에 둠 → 13497

 --  3번 값 정렬 완료  --

 

4회전 : 3번 자리의 최소값을 찾는 상세 과정

2회전 후 값인 13497 시작

4번(9)과 5번(7)을 비교하여 작은 값을 3번에 둠 → 13479

 --  4,5번 값 정렬 완료  --

 

 

3. 시간복잡도 별 (중) 문제 대비 표

복잡도별

• 복잡도별 문제는 정말 많이 나오는 것 같다.

4. 기타 - (상) 문제 대비 키워드

정렬	키워드
삽입 정렬	n ... n-1 ... 얘기 나옴
쉘 정렬	"매개변수" 어쩌고 ... 부분적으로 정렬되면 유리...
선택 정렬	n개의 레코드 중 '최소값'을 찾아서...
버블 정렬	인접한 두 개의 레코드 ...
퀵 정렬	1. 작은 값은 왼쪽 큰 값은 오른쪽에 모이도록... 2. 많은 자료이동을 없애고 하나의 파일을 부분적으로...
힙 정렬	전이진 트리, 완전 이진트리
합병(병합)정렬	이미 정렬된 두 개의파일...
기수 정렬	"버킷" 어쩌고
출처 : 시나공