정렬

정의

- 오름차순 또는 내림차순으로 데이터를 나열함

정렬 알고리즘 선택 시 고려사항

• 데이터 양
• 초기 데이터의 배열 상태
• 키 값들의 분포 상태
• 공간 및 작업 시간
• OS종류, 엑세스 빈도, 증가 데이터의 배열 상태는 고려X

선택정렬(Selection Sort)

• 첫 번째 자리를 선택하고 오른쪽으로 비교하면서 교환하기.
  

• 그 다음, 두번 째 자리를 지정하고 오른쪽으로 비교하면서 교환하기.
  

• 즉, 주어진 리스트 중에 최솟값 찾고, 그 값을 맨 앞에 위치한 값과 교체, 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체

> 첫 번째 자리에는 100이 있고 70과 비교 후 70이 첫번 째 자리에 옴.
> 첫 번째 자리에는 70이 있고 100, 90, 80, 90과 비교 후 교환이 이루어지지 않아 첫 번째 자리는 70이 당첨~

> 그 다음은 두 번째 자리를 구해야하고 100이라는 값이 있다. 따라서 비교하고 교환하고를 반복~

버블정렬(Bubble Sort)

• 두 값끼리 짝을 지어서 비교하면서 오른쪽으로 이동하기.
  
• 가장 오른쪽 자리 부터 큰 값으로 채워진다.

> 처음 두 쌍(100,70)을 비교하고 (70,100) 순서로 교환
> 그 다음 두쌍(100,90)을 비교하고 (90,100) 순서로 교환
> 계속 반복하면 100은 가장 오른쪽에 자리~

삽입정렬(Insertion Sort)

• 두 번째 자리값인 70을 key로 잡고 왼쪽으로 비교, 교환을 한다.
  
• 그 다음은 세 번째 자리값을 key로 잡고 왼쪽으로 비교, 교환을 하다가 key값보다 더 크면 교환, 작거나 같으면 다음 단계로 간다.
  

> 70을 key값으로 잡고 왼쪽으로 비교~

> 100이 key값(70)보다 크니 교환하여 Pass 1 완성
> 세 번째 값 90을 key값으로 잡고 왼쪽으로 비교~
> 100이 key값(90)보다 크니 교환하고, 70이 key값(90)보다 작으니 그대로 유지하여 Pass 2 완성

퀵 정렬(Quick Sort)

파랑 = Pivot

회색 = 확정

빨강 = Low

보라 = High

5

3

8

4

9

1

6

2

7

> 5를 Pivot으로 잡고 5보다 큰 숫자를 왼쪽부터 찾아감(Low가 3부터 오른쪽으로 이동)

> 5보다 작은 숫자를 오른쪽부터 찾아감(High가 7부터 왼쪽으로 이동)

> Low는 8에 바로 걸리고 High는 없어서 2에 걸림
> Low와 High가 서로 걸렸기 때문에 서로 교환

5

3

2

4

9

1

6

8

7

> Low가 4부터 오른쪽으로 이동 / High가 6부터 왼쪽으로 이동

> Low는 9에 걸리고 High는 1에 걸림

> 서로 걸렸기 때문에 교환

5

3

8

4

1

9

6

2

7

> Low가 9부터 오른쪽으로 이동 / High가 1부터 왼쪽으로 이동

> 이렇게 Low와 High가 엇갈리는게 Pass 1 High와 Pivot을 교환하고 Pivot이었던 5는 확정

1

3

8

4

5

9

6

2

7

> 확정된 5를 기준으로 왼쪽 1 3 8 4와 오른쪽 9 6 2 7이 있으니 따로따로 정렬 수행

• 분할 정복 알고리즘의 하나로, 평균적으로 매우 빠른 수행 속도를 자랑
• Pivot 값은 리스트의 첫 번째 데이터가 아니어도 상관없다.
• 순환 알고리즘을 사용해야 하므로 스택공간을 필요로 한다.
• 키를 기준으로 작은 값은 왼쪽에, 큰 값은 오른쪽 서브파일로 분해시키는 방식
• 평균 시간 복잡도 : 
• 최악 시간 복잡도 :