정렬 알고리즘(홍진택 주무관님)

[자료구조 목차]

 

1. 버블 정렬

• 왼쪽끝에서부터 시작해서 인접하는 두 항목의 값을 비교하여 원하는 순서(오름차순 또는 내림차순)로 되어있지 않으면 서로 위치를 교환하는 정렬
• Sorted flag를 이용하여 정렬이 완료되었는지를 판단 -> 교환이 한번도 발생하지 않는다면 정렬이 완료된 것임
• 이웃노드간 비교 if A[i] < A[i+1] -> 비교횟수 O(N^2), 이동횟수 O(N^2), 도중 정렬 완성시 멈출 수 있음 - 최선O(N)

2. 선택 정렬

• 주어진 리스트 중에서 최소값(또는 최대값)을 찾고 그 값을 맨 앞에 위치한 값과 교체함으로써 정렬을 완성하는 알고리즘
• 최소값/최대값(Min/Max) 찾아 교체 -> 비교횟수 O(N^2), 이동횟수 O(N^2)

3. 삽입 정렬

• 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘
• 데이터를 정렬된 데이터에 삽입해 나가는 방법 -> 비교횟수 O(N^2), 이동횟수(최악 O(N^2), 최선 O(1)-발생 않할때) 

4. 쉘 정렬

• 특정 레코드와 거리가 일정한 레코드끼리 부파일로 나누어 각 부파일을 삽입 정렬하는 방식 - O(N^2)

5. 퀵 정렬

• 입력자료를 Pivot(기준데이터)을 중심으로 작은 값을 갖는 자료들과 큰 값을 갖는 자료들로 분할하여 정렬하며, 분할된 각 부분 리스트에 대해 반복적으로 퀵 정렬을 수행하는 정렬 알고리즘
• 최악 -> 정렬된 입력데이터 O(N^2), 평균: O(N log N), 분할,정복 기법

6. 힙(Heap) 정렬

• 최대 힙 트리나 최소 힙 트리를 구성해 정렬을 하는 방법 - 내림차순 정렬을 위해서는 최대 힙을 구성하고 오름차순 정렬을 위해서는 최소 힙을 구성하여 정렬
• 완전이진트리, 힙의 삭제 이용(최대힙 - 내림차순) -> 평균,최악 O(N log N)

7. 합병 정렬

• 분할(Divide): 입력 배열을 같은 크기의 2개의 부분 배열로 분할한다.
  정복(Conquer): 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출을 이용하여 다시 분할 정복 방법을 적용한다.
  결합(Combine): 정렬된 부분 배열들을 하나의 배열에 합병한다.
• 두 개 파일 합쳐 한개 파일 만듬. 추가적 메모리 필요, 2배 공간 -> N개 레코드 있을때, 2C(N/2) + N - 1, 평균, 최악 O(N log N)

 

※ 정렬(sort) 정리

<정렬 빅오 표기>

버블정렬?  이웃노드간 비교 if A[i] < A[i+1] -> 비교횟수 O(N^2), 이동횟수 O(N^2), 도중 정렬 완성시 멈출 수 있음 - 최선O(N)

선택정렬? 최소값/최대값(Min/Max) 찾아 교체 -> 비교횟수 O(N^2), 이동횟수 O(N^2)

삽입정렬? 데이터를 정렬된 데이터에 삽입해 나가는 방법 -> 비교횟수 O(N^2), 이동횟수(최악 O(N^2), 최선 O(1)-발생 않할때)  

쉘정렬? 데특정 레코드와 거리가 일정한 레코드끼리 부파일로 나누어 각 부파일을 삽입 정렬하는 방식 - O(N^2)

퀵정렬? Pivot(기준데이터)을 중심으로 작은 값을 갖는 자료들과 큰 값을 갖는 자료들로 분할하여 정렬 - 최악 -> 정렬된 입력데이터 O(N^2), 평균: O(N log N), 분할,정복 기법

힙정렬? 완전이진트리, 힙의 삭제 이용(최대힙 - 내림차순) -> 평균,최악 O(N log N)

2-Way merge? 두 개 파일 합쳐 한개 파일 만듬. 추가적 메모리 필요, 2배 공간 -> N개 레코드 있을때, 2C(N/2) + N - 1, 평균, 최악 O(N log N)

기수 정렬? 공간복잡도 큼, 비교없이 분배 -> O(N)

구분	정렬	설명
평균, 최악 시간복잡도 정렬	- 버블, 선택, 삽입 정렬	- O(N^2)
	- 2-way merge, 힙 정렬	- O(N log N)
평균, 최악 시간복잡도 차가 가장 큰 정렬	- 퀵 정렬	- 평균: O(N log N)
		- 최악 : O(N^2) -> 정렬된 데이터 사용 시
입력데이터의 순서에 영향 받는 정렬	- 버블, 삽입 정렬	- 최선: O(N)
	- 퀵 정렬	- 최악: O(N^2)
공간복잡도 큰 정렬	- 기수 정렬	- 비교없고, 분배 없음
	- 2-way merge	- 기수 정렬 다음으로 공간복잡도 큰 정렬임