1. 알고리즘 - 정렬(Sort)

 1. 정렬의 종류

  - 내부정렬(Internal Sort)

 데이터의 양이 적을 때 주기억장치에서 정렬하는 방식이다. 메모리를 이용하므로 정렬 속도가 빠르지만 정렬할 수 있는 데이터의 양이 RAM의 용량에 따라 제한된다.

 

  - 외부정렬(External Sort)

 입력 크기가 주기억장치 공간보다 큰 경우 보조기억장치에 있는 입력(파일)을 나누어 주기억장치에 읽어들인 후 정렬하는 방식으로 2-way 병합 정렬과 n-way 병합 정렬이 있다.

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

 

 2. 선택 정렬(Selection Sort)

  : 주어진 데이터에서 가장 큰 값 또는 작은 값을 찾아 선택하고 교환하여 정렬

  : 구현이 간단하지만 입력 배열의 정렬 여부와 관계 없이 항상 동일한 연상량을 가지고 있어 최적화의 여지가 적음

  : 시간복잡도는 O(n^2)

def selectionSort(array):
    for i in range(len(array)-1):
    	minIndex = i
        for j in range(i+1, len(array)):
            if array[j] < array[minIndex]:
                array[minIndex], array[j] = array[j], array[minIndex]

  ▸초기 배열 상태

 ▸최소값을 찾아 array[i]의 값과 교환

 

2. 버블 정렬(Bubble Sort)

 : 인접한 두 원소를 비교해 자리를 교환하여 정렬

 : 구현이 단순하지만 집합 요소의 Swap이 빈번하며 느리다

 : O(n^2)

def bubbleSort(array):
    for i in range(len(array)-1, 0, -1):
        for j in range(i):
            if(array[j] > array[j+1]):
                array[j], array[j+1] = array[j+1], array[j]

 

3. 삽입 정렬(Insertion Sort)

 : 배열의 인덱스를 확장하여 데이터를 삽입하는 과정을 반복하여 정렬

 : O(n^2)

def insertionSort(array):
    for i in range(1, len(array)):
        for j in range(i, 0, -1):
            if(array[j-1] > array[j]):
                array[j-1], array[j] = array[j], array[j-1]

 

 

4. 쉘 정렬(Shell Sort)

: 일정한 간격으로 데이터의 부분집합을 구성하여 삽입 정렬을 수행

: 입력이 작을때 효율적 → 임베디드에서 주로 사용

: 간격에 따른 그룹별 정렬 방식이 H/W로의 구현에 적합

 

매개 변수가 4일때 삽입 정렬 수행

매개 변수가 2일때 삽입 정렬 수행