자료정렬 알고리즘

자료 정렬 알고리즘

• 자료정렬 (자료 처리의 기본)
  • 자료를 원하는 기준에 맞게 순서를 재배치
  • 자료저리의 효율성을 향상시키기 위한 작업
  • 많은 양 중 원하는 정보를 찾고자 할 때 훨씬 빠르게 할 수 있음.
  • 자료의 생성은 자료 내용을 컴퓨터에 저장한 후 효율적으로 사용하기 위함임
    • 양이 많을 경우 정렬은 검색을 위한 우선단계가 됨.
  • 정렬 → 검색 → 원하는 작업 실행  (이게 가장 효율적임)
  • 기준값 = 키(key)값
  • key 선택 -> 정렬 순서 방식 지정 (ex, 오름차순 / 내림차순)
  • 정렬기준 정하기 → 자료 비교하기 → 자료 이동하기

 

• 선택정렬
  • 오름차순의 선택 정렬은 배열된 자료의 값을 모두 비교
  • 자료의 양이 적을 때 알고리즘 효율성이 좋으나 특정 값의 반복된 위치 교환이 있을 수 있음.
  • 작은값 찾는 과정, 위치 교환하는 과정이 필요하므로 시간효율성이 낮음.

실행 과정	예시	8 4 7 3 5
가장 작은 값 선택	1) 가장 작은 값 3, 첫번째 자리 수 8 교환	3 4 7 8 5
첫 번째 자리 값과 위치 교환	2) 두번째 작은 값 4, 두번째 자리 수 4 => 자리 이동 x	3 4 7 8 5
가장 작은 값부터 정렬	3) 세번째 작은 값 5, 세번째 자리수 7 교환	3 4 5 8 7
모두 정렬 될 때까지 계속 반복	4) 네번째 작은 값 7, 다섯번째 자리수 8 교환	3 4 5 7 8
전체 자료 정렬 n-1번 반복 (자료 개수 n개)	전체 자료 개수 5개, 정렬 횟수 4회

 

// python 코드
def selection_sort(a):
    for i in range(len(a)):
        for j in range(i + 1, len(a)):
            if a[i] > a[j]:
                a[i], a[j] = a[j], a[i]
    return a

// c++ 코드
vector<int> selection_sort(vector<int> a) {
    for (int i = 0; i < a.size(); i++) {
        for (int j = i + 1; j < a.size(); j++) {
            if (a[i] > a[j]) swap(a[i], a[j]);
        }
    }
    return a;
}

 

 

• 버블 정렬
  • 자료를 하나씩 올바른 위치에 삽입하여 정렬하므로 정렬 과정 중 정렬 순번 배열까지 정렬 상태 유지
  • 구현이 가장 쉬운 정렬 알고리즘이지만, 효율성은 낮음

실행 과정	예시	8 4 7 3 5
인접한 두 수를 비교하며 더 큰 값을 뒤로 보내는 과정 반복 한 사이클이 끝나면 가장 큰 수가 뒤로 정렬됨.	1) 첫 번째와 두 번째 비교 (8 > 4) → 교환	4 8 7 3 5
	2) 두 번째와 세 번째 비교 (8 > 7) → 교환	4 7 8 3 5
	3) 세 번째와 네 번째 비교 (8 > 3) → 교환	4 7 3 8 5
	4) 네 번째와 다섯 번째 비교 (8 > 5) → 교환	4 7 3 5 8
	다시 처음부터 반복하며 정렬(전부 정렬될 때까지 반복)	...

 

// python 코드
def bubble_sort(a):
    for i in range(len(a) - 1):
        for j in range(len(a) - 1 - i):
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]
    return a
    
// C++ 코드
vector<int> bubble_sort(vector<int> a) {
    for (int i = 0; i < a.size() - 1; i++) {
        for (int j = 0; j < a.size() - 1 - i; j++) {
            if (a[j] > a[j + 1]) swap(a[j], a[j + 1]);
        }
    }
    return a;
}

 

 

• 삽입 정렬
  • 자료를 하나씩 올바른 위치에 삽입하여 정렬하므로 정렬 과정 중 정렬 순번 배열까지 정렬 상태 유지
  • 선택정렬보다 시간 효율성 높음. (작은 수를 찾는 과정 X, 수 하나 골라서 앞에서부터 비교)

실행 과정	예시	8 4 7 3 5
이미 정렬된 배열 부분의 내용과 자신의 값을 비교 → 자신의 위치 찾아 삽입	1) 맨 앞자리 수는 이미 정렬된 것으로 봄.	8 4 7 3 5
	2) 두번째 자리 수 정렬 (4<8 이므로 8 앞에 삽입)	4 8 7 3 5
	3) 세번째 자리 수 정렬 (4<7<8 이므로 4와 8 사이에 삽입)	4 7 8 3 5
	4) 네번째 자리 수 정렬 (3<4 이므로 4 앞에 삽입)	3 4 7 8 5
	5) 다섯번째 자리 수 정렬 (4<5<7 이므로 4와 7 사이에 삽입)	3 4 5 7 8

 

// python 코드
def insert_sort(a):
    for i in range(1, len(a)):
        key = a[i]
        j = i - 1
        while j >= 0 and a[j] > key:
            a[j + 1] = a[j]
            j -= 1
        a[j + 1] = key
    return a
    
// C++ 코드
vector<int> insert_sort(vector<int> a) {
    for (int i = 1; i < a.size(); i++) {
        int key = a[i];
        int j = i - 1;
        while (j >= 0 && a[j] > key) {
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = key;
    }
    return a;
}

 

 

• 퀵 정렬
  • 기준(pivot)을 정해 그보다 작은 값은 왼쪽, 큰 값은 오른쪽으로 분할하여 정렬을 반복하는 방식 (분할 정복 방식)
  • 선택정렬보다 빠르며, 정렬 알고리즘 중 가장 많이 사용되는 방법 중 하나
  • 재귀적으로 정렬을 수행하며 평균 시간복잡도는 매우 우수하지만 최악의 경우(이미 정렬된 경우 등)에는 O(n^2) 시간 발생 가능

실행 과정	예시	8 4 7 3 5
***기준값(pivot)을 설정 → 이미 정렬된 배열 부분의 내용과      자신의 값을 비교 → 자신의 위치 찾아 삽입 = 재귀적으로 정렬 완료 될 때까지 반복	1) 기준값(pivot) 설정  ex) 마지막 요소를 기준으로 설정	8 4 7 3 5
	2) 작은 값은 왼쪽, 큰 값은 오른쪽으로 분할	4 3 (5 기준) 8 7
	3) 왼쪽 그룹에 대해 다시 퀵정렬	[3] 4  (3기준)
	4) 오른쪽 그룹에 대해 다시 퀵정렬	[7] 8  (7기준)
	5) 전체 정렬 결과 병합	3 4 5 7 8

***기준값(pivot)을 설정 방법 (첫번째 요소(0), 마지막 요소(n-1), 중간요소(n/2), 무작위, 처음-중간-끝 중 중앙값)

 

• 합병정렬
  • 전체 문제를 한번에 푸는 방식이 아니라 문제를 작은 두개로 분리하고, 다시 반복분리하여 최소에서 문제를 해결하고 그 해결책을 반복적용하여 전체를 해결하는 방식
  • 재귀함수 적용시 구현이 용이함. 임시 배열을 이용하는 방식이므로 공간적 낭비 있음.

실행 과정						예시 )   8 4 7 3 5
자료를 두개의 균등한 크기로 분할 → 최소단위까지 반복 → 두 자료를 정렬 기준에 맞게 합병 → 전체 정렬까지 반복

 

• 쉘 정렬
  • 자료를 일정 간격(gap)을 두고 나눈 뒤 삽입정렬을 수행하고, 점차 간격을 줄이며 전체 배열을 정렬하는 방식
  • 삽입정렬을 개선한 방식으로, 자료 수가 많을수록 효율적

실행 과정	예시	8 4 7 3 5
자료를 일정 간격으로 나누어 정렬 → 각 그룹 마다 삽입정렬 사용 → 간격을 줄여가며 반복실행 → 간격 1로 줄이고 삽입정렬 수행	1) 초기 gap = 2 설정	8 4 7 3 5
	2) gap=2로 나눈 그룹 삽입정렬	그룹1: (0,2) → 8 7 → 7 4 8 3 5
		그룹2: (1,3) → 4 3 → 7 3 8 4 5
		그룹3: (2,4) → 8 5 → 7 3 5 4 8
	3) gap=1로 줄여 전체 삽입정렬 수행	3 < 7 → 3 7 5 4 8
		5 < 7 → 3 5 7 4 8
		4 < 7 & 4 < 5 → 3 4 5 7 8

 

 

• 자료 정렬 알고리즘 선택시 고려사항
  • 1) 자료의 양     2) 사용 가능한 기억 공간의 크기   3) 정렬을 위한 자료 이동의 빈도 수
  • 효율성을 위한 수행 시간 측정(시간복접도 : 수행시간을 계산하여 알고리즘의 효율성 검토)

 

정렬 알고리즘 종류	최선(측정시간 하한 값)	평균(하한/상한 사이 값)	최악(측정시간 상한 값)	비고
선택정렬	n^2	n^2	n^2
버블정렬	n	n^2	n^2
삽입정렬	n	n^2	n^2	최선 우수(선택 대비)
빠른(퀵)정렬	n log n	n log n	n^2
합병정렬	n log n	n log n	n log n	효율성 우수
쉘정렬	n log n	n (log n)^2	n (log n)^2	가장 우수(자료多 유용)

시간 비효율 : 선택(제일 비효율), 삽입, 버블 -> 단순하고 비효율적

시간 효율 : 빠른, 합병, 쉘(제일 효율) ->  복잡하고 효율적