3. Sort 정렬

정렬

정렬

2개 이상의 자료를 특정 기준에 의해 작은 값부터 큰 값(오름차순 : ascending), 혹은 그 반대의 순서대로(내림차순 : dexending) 재배열 하는 것

키 : 자료를 정렬하는 기준이 되는 특정 값

 

정렬의 종류

• 버블 정렬
• 카운팅 정렬
• 선택 정렬
• 퀵 정렬
• 삽입 정렬
• 병합 정렬

 

버블 정렬(Bubble Sort)

인접한 두 개의 원소를 비교하며 자리를 계속 교환하는 방식

 

정렬과정

• 첫번째 원소부터 인접한 원소끼리 계속 자리를 교환하면서 맨 마지막 자리까지 이동한다.
• 한 단계가 끝나면 가장 큰 원소가 마지막 자리로 정렬된다.
• 교환하며 자리를 이동하는 모습이 물 위에 올라오는 거품 모양과 같다고 하여 버블 정렬이라고 한다.

 

시간복잡도

O(n²)

 

배열을 활용한 버블 정렬

def BubbleSort(a, N): # 정렬할 List, N 원소 수
    for i in range(N-1, 0, -1): # 점위의 끝 위치
        for j in range(0, i):
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]

 

카운팅 정렬(Counting Sort)

항목들의 순서를 결정하기 위해 집합에 각 항목이 몇 개씩 있는지 세는 작업을 하여, 선형 시간에 정렬하는 효율적인 알고리즘

 

정렬과정

• Data에서 각 항목들의 발생 회수를 세고, 정수 항목들로 직접 인덱스 되는 카운트 배열 counts에 저장한다.
• 정렬된 집합에서 각 항목의 앞에 위치할 항목의 개수를 반영하기 위해 counts의 원소를 조정한다.
• counts[a] 감소, temp에 a 삽입 , 반복

 

시간복잡도

O(n + k)

: n은 리스트 길이, k는 정수의 최대값

 

제한사항

• 정수나 정수로 표현할 수 있는 자료에 대해서만 적용 가능
  • 각 항목의 발생 회수를 기록하기 위해, 정수 항목으로 인덱스 되는 카운트들의 배열을 사용하기 때문이다.
• 카운트들을 위한 충분한 공간을 할당하려면 집합 내의 가장 큰 정수를 알아야한다.

 

카운팅 정렬 구현

def Counting_Sort(A, B, k):
# A[] - 입력 배열 (1 to k)
# B[] - 정렬된 배열
# C[] - 카운트 배열

    C = [0] * (k + 1)

    for i in range(0, len(A)):
        C[A[i]] += 1

    for i in range(0, len(C)):
        C[i] += C[i - 1]

    for i in range(len(B) - 1, -1, -1):
        C[A[i]] -= 1
        B[C[A[i]]] = A[i]

 

셀렉션 알고리즘(Selection Algorithm)

저장되어 있는 자료로부터 k번째로 큰 혹은 작은 원소를 찾는 방법을 셀렉션 알고리즘이라 한다.

최소값, 최대값 혹은 중간값을 찾는 알고리즘을 의미하기도 한다.

 

선택과정

셀렉션은 아래와 같은 과정을 통해 이루어진다.

• 정렬 알고리즘을 이용하여 자료 정렬하기
• 원하는 순서에 있는 원소 가져오기

 

K번째로 작은 원소를 찾는 알고리즘

1번부터 k번째까지 작은 원소들을 찾아 배열의 앞쪽으로 이동시키고, 배열의 k번째를 반환한다.

k가 비교적 작을 때 유용하며 O(kn)의 수행시간을 필요로 한다.

def select(arr, k):
    for i in range(0, k):
        minIndex = i
        for j in range(i+1, len(arr)):
            if arr[minIndex] > arr[j]:
                minIndex = j
        arr[i], arr[minIndex] = arr[minIndex], arr[i]
    return arr[k-1]

시간복잡도

O(n²)

 

선택정렬

주어진 자료들 중에서 가장 작은 원소부터 차례대로 선택하여 위치를 교환하는 방식

앞서 살펴본 셀렉션 알고리즘을 전체 자료에 적용한 것.

 

정렬과정

• 주어진 리스트 중에서 최소값을 찾는다.
• 그 값을 리스트의 맨 앞에 위치한 값과 교환한다.
• 맨 처음 위치를 제외한 나머지 리스트를 대상으로 위의 과정을 반복한다.
• 미정렬 원소가 하나 남은 상황에서는 마지막 원소가 가장 큰 값을 갖게 되므로 실행을 종료하고 선택 정렬이 완료 된다.

 

시간복잡도

O(n²)

 

구현

## 알고리즘
def selectionSort(a[], N) :
        for i from 0 to n-2
                a[i], ... , a[n-1] 원소 중 최소값 a[k] 찾음
                a[i]와 a[k] 교환

## 선택 정렬
def selectionSort(a, N) :
        for i in range(N-1) :
                minIdx = i       # 최소 인덱스만 찾기! value까지 찾지 x 
                for j in range(i+1, N):
                        if a[minIdx] > a[j] :
                                minIdx = j
                a[i], a[minIdx] = a[minIdx], a[i]   # 같다면 건너뛰는 조건문 추가? < 실행할거만 늘어남 필요없음

arr = [7, 2, 5, 3, 4, 3]
N = len(arr)

for i in range(N-1):
    minIdx = i
    for j in range(i+1, N):
        if arr[minIdx] > arr[j]:
            minIdx = j
    arr[minIdx], arr[i] = arr[i], arr[minIdx]  # if문 넣지 말기 생각보다 은근 잡아먹음