038 정렬 - 1장 데이터 입출력 - 2과목 소프트웨어 개발

1. 삽입 정렬(Insertion Sort)

- 가장 간단한 정렬 방식

- 이미 순서화된 파일에 새로운 하나의 레코드를 순서에 맞게 삽입시켜 정렬한다.

- 두 번째 키와 첫 번째 키를 비교해 순서대로 나열(1회전)하고, 이어서 세 번째 키를 첫 번째, 두 번째 키와 비교해서 순서대로 나열(2회전)하고, n번째 키를 n-1개의 키와 비교하여 알맞은 순서에 삽입하는 방식이다.

- 평균과 최악 모두 수행 시간 복잡도는 O(n^2)이다.

 

예제 -> 8,5,6,2,4를 삽입 정렬

    -> 비교 대상

1회전 : 8 5 6 2 4  ->  5 8 6 2 4 
두 번째 값(5)을 첫 번째 값(8)과 비교하여 8보다 작은 5를 첫 번째 자리에 삽입하고 8을 한 칸 뒤로 이동시킨다.

 

2회전 : 5 8 6 2 4 -> 5 6 8 2 4

세 번째 값(6)을 첫 번째 값(5), 두 번째 값(8)과 비교하여 6을 8자리에 삽입하고 8은 한 칸 뒤로 이동시킨다.

 

3회전 : 5 6 82 4 -> 2 5 6 8 4

네 번째 값 2를 처음부터 비교하여 맨 처음에 삽입하고 나머지를 한 칸씩 뒤로 이동시킨다.

 

4회전 : 2 5 6 8 4 -> 2 4 5 6 8 

다섯 번째 값 4를 처음부터 비교하여 5자리에 삽입하고 나머지를 한 칸씩 뒤로 이동시킨다.

 

2. 쉘 정렬(Shell Sort)

- 삽입 정렬을 확장한 개념

- 입력 파일을 어떤 매개변수(h)의 값으로 서브파일을 구성한다.

- 각 서브파일을 삽입 정렬 방식으로 순서 배열을 하는 과정을 반복하는 정렬 방식 (보통 h = 3√n)

- 즉 임의의 레코드 키와 h 값 만큼 떨어진 곳의 레코드 키를 비교하여 순서화되어 있지 않으면 서로 교환하는 것을 반복하는 정렬

- 입력 파일이 부분적으로 정렬되어 있는 경우 유리한 방식

- 평균 수행 시간 복잡도는 O(n^1.5)

- 최악 수행 시간 복잡도는 O(n^2)

 

3.선택 정렬(Selection Sort)

- n개의 레코드 중에서 최소값을 찾아 첫 번째 레코드 위치에 놓는다.

- 나머지 (n-1)개 중에서 다시 최소값을 찾아 두 번째 레코드 위치에 놓는 방식을 반복하여 정렬

- 평균, 최악 시간 복잡도 O(n^2)

 

예제 -> 8,5,6,2,4를 선택 정렬

    -> 비교 대상

1회전 :  5 8 6 2 4 -> 5 8 6 2 4 -> 2 8 6 5 4 -> 2 8 6 5 4

            5와 8을 비교하고 5가 작으니까 위치 변화 X

            5와 6을 비교하고 5가 작으니까 위치 변화 X

            5와 2를 비교하고 2가 작으니까 위치 바꿈

            2와 4를 비교하고 2가 작으니까 위치 변화 X

 

2회전 : 2 6 8 5 4 -> 2 5 8 6 4 -> 2 4 8 6 5 

            6과 8을 비교하고 6이 작으니까 위차 바꿈

            6과 5를 비교하고 5가 작으니까 위치 바꿈

            5와 4를 비교하고 4가 작으니까 위치 바꿈

 

3회전 : 2 4 6 8 5 -> 2 4 5 8 6

            8과 6을 비교하고 6이 작으니까 위치 바꿈

            6과 5를 비교하고 5가 작으니까 위치 바꿈

 

4회전 : 2 4 5 6 8

            8과 6을 비교하고 6이 작으니까 위치 바꿈

            선택 정렬 완성

 

4. 버블 정렬(Bubble Sort)

- 주어진 파일에서 인접한 두 개의 레코드 키 값을 비교하여 그 크기에 따라 레코드 위치를 교환하는 방식

- 계속 정렬 여부를 플래그 비트(f)로 결정한다

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

 

예제 -> 8,5,6,2,4를 버블 정렬

    -> 비교 대상

  

1회전 : 5 8 6 2 4 -> 5 6 8 2 4 -> 5 6 2 8 4 -> 5 6 2 4 8 

           8과 5를 비교하고 작은 값(5)과 위치를 바꾼다

           8과 6을 비교하고 작은 값(6)과 위치를 바꾼다
           8과 2를 비교하고 작은 값(2)과 위치를 바꾼다

           8과 4를 비교하고 작은 값(4)과 위치를 바꾼다

 

2회전 : 5 6 2 4 8 -> 5 2 6 4 8 -> 5 2 4 6 8

            5와 6을 비교하고 현재 상태를 유지한다

            6과 2를 비교하고 작은 값(2)과 위치를 바꾼다

            6과 4를 비교하고 작은 값(4)과 위치를 바꾼다

 

3회전 : 2 5 4 6 8 -> 2 4 5 6 8

            2와 5를 비교하고 현재 상태를 유지한다

            5와 4를 비교하고 작은 값(4)과 위치를 바꾼다

 

4회전 : 2 4 5 6 8

            2와 4를 비교하고 현재 상태를 유지한다

            버블 정렬 완료

 

5. 퀵 정렬(Quick Sort)

- 레코드의 많은 자료 이동을 없애고 하나의 파일을 부분적으로 나누어 가면서 정렬하는 방식

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

- 위치에 관계없이 임의의 키를 분할 원소로 사용할 수 있다

- 가장 빠른 정렬 방식

- 프로그램에서 되부름을 이용하기 때문에 스택이 필요

- 분할(Divide)과 정복(Conquer)을 통해서 정렬

- 분할 : 기준값인 피봇을 중심으로 정렬할 자료들을 2개의 부분집합으로 나눔

- 정복 : 부분집합의 원소들 중 피봇보다 작은 원소들은 왼족, 크면 오른쪽 부분집합으로 정렬

- 부분집합의 크기가 더 이상 나누어질 수 없을때까지 분할과 정복을 반복 수행

- 평균 수행 시간 복잡도는 O(nlog2n)

- 최악 수행 시간 복잡도는 O(n^2)

 

6. 힙 정렬(Heap Sort)

- 전이진 트리(Complete Binary Tree)를 이용한 정렬 방식

- 구성된 전이진 트리를 Heap Tree로 변환하여 정렬

- 평균, 최악 시간 복잡도 O(nlog2n)

 

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

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

- 두 개의 키들을 한 쌍으로 하여 각 쌍에 대하여 순서를 정한다

- 위 과정에서 정렬된 서브리스트들을 하나의 정렬된 파일이 될 때까지 반복한다

- 평균과 최악 시간 복잡도는 O(nlog2n)

 

예제 -> 71,2,38,5,7,61,11,26,53,42를 합병 정렬

 

1회전 : 두 개씩 묶은 후 각각의 묶음 안에서 정렬

          (71,2) (38,5) (7,61) (11,26) (53,42)     ->     (2,71) (5,38) (7,61) (11,26) (42,53)     

 

2회전 : 묶여진 묶음을 두 개씩 묶은 후 각각의 묶음 안에서 정렬한다

           ((2,71) (5,38)),  ((7,61) (11,26)) (42,53)     ->    (2, 5 ,38, 71),  (7, 11, 26, 61) (42,53)

 

3회전 : 묶여진 묶음을 두 개씩 묶은 후 각각의 묶음 안에서 정렬한다

          ((2, 5 ,38, 71) (7, 11, 26, 61)) (42,53)     ->    (2, 5, 7, 11, 26, 38, 61, 71) (42,53)

 

4회전 : 묶여진 묶음 두 개를 하나로 묶은 후 정렬한다

            ((2, 5, 7, 11, 26, 38, 61, 71) (42,53))     ->    2, 5, 7, 11, 26, 38, 42, 53, 61, 71

                                     

 

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

- 큐를 이용하여 자릿수(Digit)별로 정렬

- 레코드의 키 값을 분석하여 같은 수 또는 같은 문자끼리 그 순서에 맞는 버킷에 분배 하였다가 버킷의 순서대로 레코드를 꺼낸다

- 평균, 최악 시간 복잡도는 O(dn)