정렬(Sort)

1. 삽입 정렬(Insertion Sort)

(1) 이미 순서화된 파일에 새로운 하나의 레코드를 순서에 맞게 삽입시켜 정렬하는 방식

(2) 평균, 최악 수행 시간 복잡도 O(n²)

 

예시: 주어진 배열: [5, 3, 8, 4, 2]

1. 처음에는 첫 번째 요소(5)는 이미 정렬된 부분으로 간주합니다.
2. 두 번째 요소(3)를 정렬된 부분에 삽입합니다. 이때, 3은 5보다 작으므로 5의 앞에 위치합니다. 결과 배열: [3, 5, 8, 4, 2]
3. 세 번째 요소(8)은 이미 정렬된 부분에 삽입될 위치를 찾아 삽입합니다. 결과 배열: [3, 5, 8, 4, 2]
4. 네 번째 요소(4)를 삽입합니다. 결과 배열: [3, 4, 5, 8, 2]
5. 마지막으로 다섯 번째 요소(2)를 삽입합니다. 결과 배열: [2, 3, 4, 5, 8]

 

2. 선택 정렬(Selection Sort)

(1) 최소값을 찾아 첫 번째 레코드 위치에 놓고, 다시 최소값을 찾아 두 번째 레코드 위치에 놓는 방식을 반복하여 정렬하는 방식

(2) 평균, 최악 수행 시간 복잡도 O(n²)

 

예시: 주어진 배열: [5, 3, 8, 4, 2]

1. 처음에는 전체 배열에서 가장 작은 값을 찾아 첫 번째 위치로 이동시킵니다. 결과 배열: [2, 3, 8, 4, 5]
2. 다음으로 두 번째로 작은 값을 찾아 두 번째 위치로 이동시킵니다. 결과 배열: [2, 3, 8, 4, 5]
3. 이런 식으로 반복하여 정렬이 완료됩니다.

3. 버블 정렬(Bubble Sort)

(1) 인접한 두개의 레코드 키 값을 비교하여 그 크기에 따라 레코드 위치를 서로 교환하는 정렬 방식

(2) 평균, 최악 수행 시간 복잡도 O(n²)

 

예시: 주어진 배열: [5, 3, 8, 4, 2]

1. 처음에는 인접한 요소인 5와 3을 비교하여 큰 값을 뒤로 이동시킵니다. 결과 배열: [3, 5, 8, 4, 2]
2. 다음으로 5와 8을 비교하여 교환하지 않습니다. 결과 배열: [3, 5, 8, 4, 2]
3. 이런 식으로 배열을 끝까지 순회하면서 필요에 따라 교환하며 정렬이 완료됩니다.

4. 쉘 정렬(Shell Sort)

(1) 매개변수의 값으로 서브파일을 구성하고, 각 서브파일을 Insertion 정렬 방식으로 순서 배열하는 정렬 방식

(2) 삽입 정렬의 확장 개념

(3) 평균 수행 시간 복잡도 O(n^1.5), 최악 수행시간 복잡도 O(n²)

 

5. 퀵 정렬(Quick Sort)

(1) 키를 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽 서브 파일에 분해시키는 정렬 방식

(2) 자료이동을 없애고 하나의 파일을 부분적으로 나누어 가면서 정렬

(3) 평균 수행 시간 복잡도 O(nlog₂n), 최악 수행시간 복잡도 O(n²)

 

6. 힙 정렬(Heap Sort)

(1) 전이진 트리를 이용한 정렬 방식

(2) 전이진 트리를 힙 트리로 변환하여 정렬

(3) 평균,최악 수행 시간 복잡도 O(nlog₂n)

 

7.  2-Way 합병 정렬(Merge Sort)

(1) 이미 정렬되어 있는 두 개의 파일을 한 개의 파일로 합병하는 정렬 방식

(2) 평균,최악 수행 시간 복잡도 O(nlog₂n)

 

8.  기수 정렬(Radix Sort) = Bucket Sort

(1) Queue를 이용하여 자릿수 별로 정렬하는 방식

(2) 레코드 키 값을 분석하여 같은 수 또는 같은 문자끼리 그 순서에 맞는 버킷에 분배하였다가 버킷의 순서대로 레코드를 꺼내어 정렬

(3) 평균,최악 수행 시간 복잡도 O(dn)

 

 

 

출처 :  정보처리기사 실기 2024 기본서 / 저자 : 길벗알앤디(김정준, 강윤석, 김용갑, 김우경)  / 출판사 : 길벗