정렬(Sort)

1. 삽입 정렬(Insertion Sort)

• 삽입 정렬은 가장 간단한 정렬 방식으로 이미 순서화된 파일에 새로운 하나의 레코드를 순서에 맞게 삽입시켜 정렬하는 방식이다.
• 평균과 최악 모두 수행시간은 O(n²) 이다.

<여기서 Tip!>

기본적인 원리는 아래와 같다.

 

1. 2번을 기준으로 1번에 비교

2. 3번을 기준으로 1번 2번에 비교

3. 4번을 기준으로 1번, 2번, 3번에 비교

4. 5번을 기준으로 1번, 2번, 3번, 4번에 비교

 

대소를 비교하여 기준보다 작다면 다음 진행을 하고, 기준보다 크다면 기준숫자 앞에 비교한 숫자를 배치하고 다음을 진행.

 

  | 8 | 5 | 6 | 2 | 4 | 

위와 같이 배열이 있을 경우

 

1. 첫 번째 실행 결과

 

     | 8 | 5 | 6 | 2 | 4 | 

  - 5보다 8이 크므로 5를 8 앞으로넣고 뒤는 밀림

     | 5 | 8 | 6 | 2 | 4 |

 

2. 두 번째 실행 결과 

 

     | 5 | 8 | 6 | 2 | 4 |

  - 6보다 8이 크므로 6를 8 앞으로넣고 뒤는 밀림

     | 5 | 6 | 8 | 2 | 4 |

 

3. 세 번째 실행 결과

 

     | 5 | 6 | 8 | 2 | 4 |

  - 2보다 5가 크므로 2를 5 앞으로넣고 뒤는 밀림

     | 2 | 5 | 8 | 6 | 4 |

  - 6보다 8이 크므로 6를 8앞으로넣고 뒤는 밀림

     | 2 | 5 | 6 | 8 | 4 |

 

4. 네 번째 실행 결과

 

     | 2 | 5 | 6 | 8 | 4 |

  - 4보다 5가 크므로 4를 앞으로넣고 뒤는 밀림

     | 2 | 4 | 5 | 6 | 8 |

 

 

 

2. 선택 정렬(Selection Sort)

• 선택 정렬은 n개의 레코드 중에서 최소값을 찾아 첫 번째 레코드 위치에 놓고, 나머지 (n-1)개 중에서 다시 최소값을 찾아 두 번째 레코드 위치에 놓는 방식을 반복하여 정렬하는 방식이다.
• 평균과 최악 모두 수행시간 복잡도는 O(n²)이다.

 

<여기서 Tip!>

기본적인 원리는 아래와 같다.

 

1. 1번을 기준으로 2번, 3번, 4번, 5번에 비교

2. 2번을 기준으로 3번, 4번, 5번에 비교

3. 3번을 기준으로 4번, 5번에 비교

4. 4번을 기준으로 5번에 비교

 

대소를 비교하여 기준보다 크다면 다음을 진행하고, 작다면 서로의 숫자를 교환함.

 

 

  | 8 | 5 | 6 | 2 | 4 | 

위와 같이 배열이 있을 경우

 

1. 첫 번째 실행 결과

 

     | 8 | 5 | 6 | 2 | 4 | 

  - 8보다 5가 작으므로 8과 5를 교환

     | 5 | 8 | 6 | 2 | 4 |

  - 5보다 2가 작으므로 5와 2를 교환

     | 2 | 8 | 6 | 5 | 4 |

 

2. 두 번째 실행 결과 

 

     | 2 | 8 | 6 | 5 | 4 |

  - 8보다 6이 작으므로 8과 6을 교환

     | 2 | 6 | 8 | 5 | 4 |

  - 8보다 6이 작으므로 8과 6을 교환

     | 2 | 5 | 8 | 6 | 4 |

  - 8보다 6이 작으므로 8과 6을 교환

     | 2 | 4 | 8 | 6 | 5 |

 

3. 세 번째 실행 결과

 

     | 2 | 4 | 8 | 6 | 5 |

  - 8보다 6이 작으므로 8과 6을 교환

     | 2 | 4 | 6 | 8 | 5 |

  - 8보다 6이 작으므로 8과 6을 교환

     | 2 | 4 | 5 | 8 | 6 |

 

4. 네 번째 실행 결과

 

     | 2 | 4 | 5 | 8 | 6 |

  - 8보다 6이 작으므로 8과 6을 교환

     | 2 | 4 | 5 | 6 | 8 |

 

 

3. 버블 정렬(Bubble Sort)

• 버블 정렬은 주어진 파일에서 인접한 두 개위 레코드 키값을 비교하여 그 크기에 따라 레코드 위치를 서로 교환하는 정렬 방식이다.
• 평균과 최악 모두 수행시간 복잡도는  O(n²)이다.

 

<여기서 Tip!>

기본적인 원리는 아래와 같다.

 

1. 1번을 기준으로 2번에 비교

2. 2번을 기준으로 3번에 비교

3. 3번을 기준으로 4번에 비교

4. 4번을 기준으로 5번에 비교

 

대소를 비교하여 기준보다 작다면 서로 교환

위 단계를 계속 반복을 하는데 더 이상 안 바꿘다면 Stop

 

 

  | 8 | 5 | 6 | 2 | 4 | 

위와 같이 배열이 있을 경우

 

1. 첫 번째 실행 결과

 

     | 8 | 5 | 6 | 2 | 4 | 

  - 8보다 전부 작으므로 맨 뒤로 가짐

     | 5 | 6 | 2 | 4 | 8 | 

 

2. 두 번째 실행 결과 

 

     | 5 | 6 | 2 | 4 | 8 |

  - 6보다 2가 작으므로 교환

     | 5 | 2 | 6 | 4 | 8 | 

  - 6보다 4가 작으므로 교환

     | 5 | 2 | 4 | 6 | 8 | 

 

3. 세 번째 실행 결과

 

     | 5 | 2 | 4 | 6 | 8 | 

  - 5보다 2가 작으므로 교환

     | 2 | 5 | 4 | 6 | 8 | 

  - 5보다 4가 작으므로 교환

     | 2 | 4 | 5 | 6 | 8 | 

 

4. 쉘 정렬(Shell Sort)

• 쉘 정렬은 입력 파일을 어떤 매개변수의 값으로 서브파일을 구성하고, 각 서브파일을 삽입 정렬(Insertion Sort) 방식으로 순서 배열하는 과정을 반복하는 정렬 방식이다.
• 삽입 정렬(Insertion Sort)을 확장한 개념이다.
• 평균 수행 시간 복잡도는 O(n¹∙⁵)이고, 최악의 수행 시간 복잡도는 O(n²)이다.

 

5. 퀵 정렬(Quick Sort)

• 퀵 정렬은 키를 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽 서브 파일에 분해 시키는 과정을 반복하는 정렬 방식이다.
• 레코드의 많은 자료 이동을 없애고 하나의 파일을 부분적으로 나누어 가면서 정렬한다.
• 평균 수행 시간 복잡도는 O(nlog₂n)이고, 최악의 수행 시간 복잡도는 O(n²)

 

6. 힙 정렬(Heap Sort)

• 힙 정렬은 전이진 트리를 이용한 정렬 방식이다.
• 구성된 전이진 트리(Complete BinaryTree)를 Heap Tree로 변환하여 정렬한다.
• 평균과 최악 모두 시간 복잡도는 O(nlog₂n)이다.

 

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

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

 

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

• 기수 정렬은 Queue를 이용하여 자릿수(Digit)별로 정렬하는 방식이다.
• 레코드의 키 값을 분석하여 같은 수 또는 같은 문자끼리 그 순서에 맞는 버킷에 분배하였다가 버킷의 순서대로 레코드를 꺼내어 정렬한다.
• 평균과 최악 모두 시간 복잡도는 O(dn)이다. 

 

<여기서 Tip!>

위를 정리한 시간복잡도 표이다.

종류	평균(Big-O)	최악(Big-O)
삽입 정렬	O(n²)	O(n²)
선택 정렬	O(n²)	O(n²)
버블 정렬	O(n²)	O(n²)
쉘 정렬	O(n¹∙⁵)	O(n²)
퀵 정렬	O(nlog₂n)	O(n²)
힙 정렬	O(nlog₂n)	O(nlog₂n)
2-Way 정렬	O(nlog₂n)	O(nlog₂n)
기수 정렬	O(dn)	O(dn)

 

 

 

 

 

드디어 데이터 입출력 파트도 끝났습니다..

1, 2 파트가 책의 25퍼라니.. (12장까진데...?)

 

여.. 여튼 다음은 통합 구현입니다!!

통합구현은 XML만 중요도만 높기 때문에 한 챕터만 다룰 생각입니다!

사실 실기 시험까지 1달밖에 안남아서..

빠르게 중요부분만 정리하고 따로 공부하려합니다..

 

읽어주셔서 감사합니다!

정처기 화이팅!