정보처리기사 필기(데이터 입.출력 구현)정렬

※본 내용은 스스로 공부하며 중요하다고 생각하는 부분만 정리한 내용입니다. 

---

공부 서적(시나공 정보처리기사 필기책)

시나공 정보처리기사 필기

〈2022 시나공 정보처리기사 필기〉는 출제기준에 포함된 125개의 학습 모듈을 완전 분해하여 정보처리기사 수준에 맞게 205개 섹션으로 엄선하여 정리하였습니다. 비전공자들이 쉽게 학습 방향을 잡을 수 있도록 NCS 학습 모듈을 가이드 삼아 자세한 설명과 충분한 예제를 더했고, 책에 수록된 내용은 어떠한 변형 문제가 나오더라도 대처할 수 있도록 최대한 자세하고 쉽게 설명했습니다.〈기억상자&기출 CBT〉 ‘기억상자’ 암기 프로그램으로 반복 학습을 통해 틀린 문제는 틀리지 않을 때까지, 맞혔던 문제는 안전하게 머릿속에 담아 시험장에 가지고 갈 수 있도록 해주고, 실제 시험장과 똑같은 기출문제 CBT로 마무리 학습 및 시험 전 현장 감각을 키울 수 있습니다(WWW.MEMBOX.CO.KR).

book.naver.com

출처: 시나공 정보처리기사 필기

저자: 김정준,강윤석,김용갑,김우경

출판사 : 길벗

---

정렬

---

삽입 정렬

• 가장 간단한 정렬 방식, 순서에 맞게 삽입하여 정렬
• 최악,평균 시간 복잡도 n의 제곱

쉘 정렬

• 삽입 정렬 확장한 개념, 매개변수 도입
• 부분적 정렬되어 있으면 유리함
• 평균 시간 복잡도 n의 1.5곱, 최악은 n의 제곱

선택 정렬

• 레코드 중 최소값을 찾아서 첫 번째 레코드에 놓고 다음 최소값 찾아서 다음 레코드에 놓는다.
• 평균,최악 시간복잡도 n의 제곱

버블 정렬

• 인접한 두 개의 레코드 값을 비교하여 서로 교환하는 방식
• 정렬 여부를 파악하기 위해 플래그 비트 사용
• 평균 및 최악 시간 복잡도 n의 제곱

퀵 정렬

• 많은 자료 이동 없애고, 부분적으로 나누어 가면서 정렬, 가장 빠른 방식
• 스택 사용, 분할(피봇 중심으로 2개로 나눔)과 정복(작은 원소 왼쪽 큰 원소 오른쪽)으로 정렬
• 평균 시간 복잡도 nlog2n, 최악은 n의 제곱

힙 정렬

• 전이진 트리 사용하여 정렬
• Heap Tree로 변환하여 정렬
• 평균, 최악 시간복잡도 nlog2n

2-Way 합병 정렬

• 이미 정렬된 두 개의 파일을 한 개의 파일로 합병하여 정렬
• 두 개의 값들을 쌍으로 묶어서 순서를 정하고 쌍들을 정렬한 뒤 합병하는 것을 반복한다.
• 평균과 최악 시간복잡도 모두 nlog2n

기수 정렬

• Queue이용하여 자리수별로 정렬
• 평균과 최악 시간복잡도 모두 dn이다.