정보처리기사 실기(데이터 입·출력 구현) 정렬(Sort)

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

---

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

시나공 정보처리기사 실기

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

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

출판사 : 길벗

---

정렬

---

 

삽입 정렬

• 이미 순서화된 파일에 새로운 하나의 레코드를 순서에 맞게 삽입시켜 정렬하는 방식
• 평균과 최악 모두 시간 복잡도 O(n²)

선택 정렬

• 최소값을 찾아 첫 번째 레코드 위치에 놓고, 다시 최소값을 찾아 두 번째 레코드 위치에 놓는 방식을 반복하여 정렬
• 평균과 최악 모두 시간 복잡도 O(n²)

버블 정렬

• 인접한 두 개의 레코드 키 값을 비교하여 그 크기에 따라 레코드 위치를 서로 교환하는 정렬 방식
• 평균과 최악 모두 시간 복잡도 O(n²)

쉘 정렬

• 매개변수 값으로 서브파일을 구성하고 각 서브파일을 Insertion 정렬 방식으로 순서 배열하는 정렬 방식
• 삽입 정렬을 확장한 개념

퀵 정렬

• 키를 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽 서브 파일에 분해시키는 과정을 반복하는 정렬 방식
• 평균 시간 복잡도 O(nlog₂n)이고, 최악 시간 복잡도 O(n²)

힙 정렬

• 전이진 트리를 이용한 정렬 방식
• 평균 및 최악 시간 복잡도 O(nlog₂n)이다.

2-Way 합병 정렬

• 이미 정렬되어 있는 두 개의 파일을 한 개의 파일로 합병하는 정렬 방식
• 평균 및 최악 시간 복잡도 O(nlog₂n)이다.

기수 정렬

• Queue를 이용하여 자릿수별로 정렬하는 방식
• 평균 및 최악 시간 복잡도 O(dn)이다.