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

정렬 (Sort)

이미 저장된 데이터를 정렬하는 과정은 생각보다 복잡합니다. 다양한 정렬방법과 특징에 대해서 알아보도록 합시다.

 

삽입 정렬 - Insertion Sort

데이터 중에서 하나의 데이터를 차례대로 비교해서 조건에 만족할 시 만족한 데이터 앞에 삽입하는 정렬방식 

최대 시간 복잡도 O(n^2)

예시

• 초기 상태

5

4

1

2

3

 

•  1회전
  • 2번 값을 선택하고 1번 값과 비교한다.
  • 만약 2번값 < 1번 값이면, 2번 값을 1번 값 앞에 삽입하고 1번데이터를 뒤로 이동시킨다.
• 1회전 변경 전

5

4

1

2

3

• 1회전 변경 후

4

5

1

2

3

 

• 2회전
  • 3번 값을 선택하고 1번, 2번 값과 비교한다.
  • 동일하게 3번값 < 1번 값 이면 1번 값 앞에 3번 값 < 2번 값이면 2번 값 앞에 삽입한다.

• 2회전 변경 전

4

5

1

2

3

• 2회전 변경 후

1

4

5

2

3

 

• 3회전
  • 위 과정을 계속 반복한다.

• 3회전 변경 전

1

4

5

2

3

• 3회전 변경 후

1

2

4

5

3

 

•  4회전
  • 위 과정을 계속 반복한다.

• 4회전 변경 전

1

2

4

5

3

• 4회전 변경 후

1

2

3

4

5

 

선택 정렬 - Selection Sort

데이터중에서 최소값을 찾아 첫 번째 위치에 놓는 정렬방식

최대 시간 복잡도 O(n^2)

예시

• 초기 상태

5

4

1

2

3

 

• 1회전

5

4

1

2

3

4

5

1

2

3

1

5

4

2

3

1

5

4

2

3

• 1회전 최종 결과

1

5

4

2

3

• 2회전

1

5

4

2

3

1

4

5

2

3

1

2

5

4

3

• 2회전 최종 결과

1

2

5

4

3

• 3회전

1

2

5

4

3

1

2

4

5

3

• 3회전 최종 결과

1

2

3

5

4

• 4회전

1

2

3

5

4

• 4회전 최종 결과

1

2

3

4

5

 

버블 정렬 - Bubble Sotr

데이터 중에서 인접한 두 개의 값을 비교하여 그 크기에 따라 교환하며 정렬하는 방식

최대 시간 복잡도 O(n^2)

예시

• 초기 상태

5

4

1

2

3

 

• 1회전

5

4

1

2

3

4

5

1

2

3

4

1

5

2

3

4

1

2

5

3

• 1회전 최종 결과

4

1

2

3

5

• 2회전

4

1

2

3

5

1

4

2

3

5

1

2

4

3

5

• 2회전 최종 결과

1

2

3

4

5

 

쉘 정렬 - Shell Sort

삽입접렬을 확장한 개념

매개변수의 값으로 서브파일을 구성하고 각 서브파일은 삽입정렬방식으로 순서 배열하는 과정을 반복하는 정렬 방식

 

퀵 정렬 - Quick Sort

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

 

힙 정렬 - Heap Sort

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

 

합병 정렬 - Merge Sort

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

 

기수 정렬 - Bucket Sort

큐를 이용하여 자릿수별로 정렬하는 방식