자료 구조 - 정렬 1

1. 정렬과 정렬 종류

• 2개 이상의 자료를 작은 것부터 큰 것 순서의 오름차순이나 큰 것부터 작은 것 순서의 내림차순으로 재배열하는 것

1) 정렬

• 키 : 자료를 정렬하는데 사용하는 기준이 되는 특정 값
• 정렬의 예)

2) 정렬 방법의 종류

(1) 비교식 정렬

• 비교하고자 하는 각 키 값들을 한번에 두개 씩 비교하여 교환하는 방식

(2) 분산식 정렬

• 키 값을 기준으로 하여 자료를 여러개의 부분 집합으로 분해하고 각 부분집합을 정렬함으로써 전체를 정렬하는 방식

(3) 정렬 장소에 따른 분류

(3-1) 내부 정렬 (internal sort)

• 정렬할 자료를 메인 메모리에 올려서 정렬하는 방식
• 정렬 속도가 빠르지만 정렬할 수 있는 자료의 양이 메인 메모리의 용량에 따라 제한된

(3-2) 내부 정렬 방식

• 교환 방식 : 키를 비교하고 교환하여 정렬하는 방식
  • 선택 정렬, 버블 정렬, 퀵 정렬
• 삽입 방식 : 키를 비교하고 삽입하여 정렬하는 방식
  • 삽입 정렬, 쉘 정렬
• 병합 방식 : 키를 비교하고 병합하옂 정렬하는 방식
  • 2-way 병합, n-way 병합
• 분배 방식 : 키를 구성하는 값을 여러 개의 부분집합에 분배하여 정렬하는 방식
  • 기수 정렬
• 선택 방식 : 이진 트리를 사용하여 정렬하는 방식
  • 히프 정렬, 트리 정렬

(3-3) 외부 정렬 (external sort)

• 정렬할 자료를 보조 기억장치에서 정렬하는 방식
• 대용량의 보조 기억 장치를 사용하기 때문에 내부 정렬보다 속도는 떨어지지만 내부 정렬로 처리할 수 없는 대용량의
  자룔에 대한 정렬

(3-4) 외부 정렬 방식

• 병합 방식 : 파일을 부분 파일로 분리하여 각각을 내부 정렬 방법으로 정렬하여 병합하는 정렬 방식
  • 2-way 병합, n-way 병합

(4) 정렬 방식의 선택 기준

• 시스템 특성, 정렬할 자료의 양, 자료들의 정렬 전 상태, 정렬에 사용하는 기억 공간과 실행 시간등의 조건에 따라 결정
• 정렬의 효율성을 비교하는 기준은 정렬에 필요한 비교 횟수와 이동 횟수

2. 선택 정렬과 버블 정렬

1) 선택 정렬

• 전체 원소들 중에서 기준 위치에 맞는 원소를 선택하여 자리를 교환하는 방식으로 정렬

(1) 수행 방법

• 전체 원소 중에서 가장 작은 원소를 찾아 선택하여 첫 번째 원소와 자리를 교환함
• 그 다음 두 번째로 작은 원소를 찾아 선택하여 두 번째 원소와 자리를 교환함
• 그 다음에 세 번째로 작은 원소를 찾아 선택하여 세 번째 원소와 자리를 교환함
• 이 과정을 반복하면서 정렬을 완성

2) 선택 정렬 수행 과정

• 정렬되지 않은 {69,10,30,2,16,8,31,22}의 자료들을 선택 정렬 방법으로 정렬하는 과정

(1) 첫 번째 자리를 기준 위치로 정함

• 전체 원소 중에서 가장 작은 원소 2를 선택하여 기준 위치에 있는 원소 69와 자리 교환

(2) 두 번째 자리를 기준 위치로 정함

• 나머지 원소 중에서 가장 작은 원소 8을 선택하여 기준 위치에 있는 원소 30과 자리 교환

(3) 세 번째 자리를 기준 위치로 정함

• 나머지 원소 중에서 가장 작은 원소 10을 선택하여 기준 위치에 있는 원소 30과 자리 교환

(4) 네 번째 자리를 기준 위치로 정함

• 나머지 원소 중에서 가장 작은 원소 16을 선택하여 기준 위치에 있는 원소 69와 자리 교환

(5) 다섯 번째 자리를 기준 위치로 정함

• 나머지 원소 중에서 가장 작은 원소 22를 선택하여 기준 위치에 있는 원소 69와 자리 교환

(6) 여섯 번째 자리를 기준 위치로 정함

• 나머지 원소 중에서 가장 작은 원소 30를 서택하여 기준 위치에 있는 원소 30과 자리 교환 (제자리)

(7) 일곱 번째 자리를 기준 위치로 정함

• 나머지 원소 중에서 가장 작은 원소 31를 선택하여 기준 위치에 있는 원소 31과 자리 교환 (제자리)

• 마지막에 남은 원소 69는 전체 원소 중에서 가장 큰 원소로서 이미 마지막 자리에 정렬된 상태이므로 실행을
  종료하고 선택 정렬이 완성됨

3) 선택 정렬 알고리즘

  selectionSort(a[],n){
      for( i<-1 ; i < n ; i <- i + 1){

            a[i], ... , a[n-1] 중에서 가장 작은 원소 a[k]를 선택하여,
            a[i]와 교환
      }
  }
  end selectionSrot()

(1) 메모리 사용 공간

• n개의 원소에 대하여 n개의 메모리 사용

(2) 비교 횟수

• 1 단계 : 첫 번째 원소를 기준으로 n개의 원소 비교
• 2 단계 : 두 번째 원소를 기준으로 마지막 원소까지 n-1개의 원소 비교
• 3 단계 : 세 번재 원소를 기준으로 마지막 원소까지 n-2개의 원소 비교
• i 단계 : i 번째 원소를 기준으로 n-i개의 원소 비교

• 어떤 경우에서나 비교 횟수가 같으므로 시간 복잡도는 o(n(2승))이 됨