기본 정렬 알고리즘

정렬 알고리즘은 n개의 숫자가 입력으로 주어졌을 때, 이를 기준에 맞게 정렬하여 출력하는 알고리즘이다.
많은 종류의 알고리즘이 있고, 시간 복잡도와 공간 복잡도가 다 다르다. 대표적으로 많이 사용하는 몇가지만 우선적으로 학습할 예정이다.

 

1. 선택 정렬

해당 순서에 원소를 넣을 위치는 이미 정해져있고, 그 위치에 어떤 원소를 넣을지 선택하는 알고리즘이다.

 

progress

1) 주어진 배열 중 최소값을 찾는다.
2) 그 최소값을 가장 앞에 위치한 값과 바꾼다.
3) 가장 앞에 위치한 값 뺀 나머지 배열에서 동일한 동작을 반복한다.

 

8

7

2

5

4

➡️ 최소값 2와 가장 앞에 위치한 8을 바꾼다.

 

2

7

8

5

4

➡️ 2는 자리가 고정된 상태이다. 이는 제외하고 동일한 과정을 반복한다.

최소값 4와 가장 앞에 위치한 7을 바꾼다.

 

2

4

8

5

7

➡️ 최소값 5와 가장 앞에 위치한 8을 바꾼다.

 

2

4

5

8

7

➡️ 최소값 7과 가장 앞에 위치한 8을 바꾼다.

 

오름차순 완료 상태

2

4

5

8

7

 

파이썬 코드

for i in range(len(array)):
	min_index=i
    for j in range(i+1,len(array)):
    	if array[min_index]>array[j]:
        	min_index=j
    array[i], array[min_index]=array[min_index],aray[i] 

print(array)

 

시간 복잡도
데이터의 개수가 N개일 때 첫 번째 회전에서 비교 횟수는 n-1, 두 번째 회전에서 비교 횟수는 n-2 이므로 전체를 합하면 (n-1) + (n-2) + ... + 2 + 1 => n(n-1) / 2
O(N^2)의 시간이 걸린다.

공간 복잡도

주어진 배열 안에서 교환을 통해 정렬이 수행되므로 O(N)이다.

 

장, 단점

장) 알고리즘이 쉽고 간단하다.
단) 시간 복잡도를 봤을 때 비효율적이다.

 

2. 삽입 정렬

현재 위치에서, 이미 정렬되어 있는 그 이하의 배열들과 비교하여 자신이 들어갈 위치를 찾아, 그 위치에 삽입하는 배열 알고리즘이다.

손 안의 카드를 정렬하는 방법과 유사하다.

 

progress

1) 2번째 위치의 값을 tmp에 저장한다.

2) tmp와 이전에 있는 원소들과 비교하며 삽입한다.
3) 그 다음 위치의 값을 tmp에 저장하고 위 과정을 반복한다.

 

8

7

2

5

4

➡️ 8은 정렬이 된 상태이다. 7을 8과 비교했을 때  8보다 작기 때문에 8 앞에 삽입한다. 

 

7

8

2

5

4

➡️ 7과 8은 정렬된 상태이다. 2를 7,8과 비교했을 때 가장 작기 때문에 가장 앞에 삽입한다.

 

2

7

8

5

4

➡️ 5를 앞의 배열과 비교하여 자신의 위치에 삽입한다.

 

2

5

7

8

4

➡️ 4를 앞의 배열과 비교하여 자신의 위치에 삽입한다.

 

오름차순 완료 상태

2

4

5

7

8

 

파이썬 코드

array=[7,5,9,0,3,1,6,2,4,8]
for i in range(1,len(array)):
    for j in range(i,0,-1):
        if array[j] < array[j-1]:
            array[j],array[j-1]=array[j-1],array[j]
        else:
            break
print(array)

 

시간 복잡도

역으로 정렬된 최악의 경우 선택 정렬과 마찬가지로 O(N^2)이다.

모두 정렬이 되어있을 경우 한번씩만 비교를 하므로 O(N)이다.

 

공간 복잡도

주어진 배열 안에서 교환을 통해 정렬이 수행되므로 O(N)이다.

 

장, 단점
장) 알고리즘이 단순하고 대부분의 원소가 정렬되어 있는 경우, 효율적이다.

단) 평균과 최악의 시간 복잡도가 비효율적이다.

 

 

3. 퀵 정렬

퀵 정렬은 분할 정복 방법을 통해 주어진 배열을 정렬한다.

 

progress

1) 배열 가운데서 하나의 원소를 고른다. 이 원소를 pivot이라고 한다. (첫 원소를 고르는 경우가 많다.)
2) 피벗 앞에는 피벗보다 작은 원소들이 오고, 피벗 뒤에는 피벗보다 큰 값이 오도록 피벗을 기준으로 배열을 나눈다.
3) 분할된 두개의 작은 배열에 대해 재귀적으로 이 과정을 반복한다.

 

파이썬 코드

array=[5,7,9,0,3,1,6,2,4,8]

def quick_sort(array):
    if len(array)<=1:
        return array
    
    pivot=array[0] #피벗은 첫 번째 원소
    tail=array[1:] #피벗을 제외한 리스트
    left_side=[x for x in tail if x<=pivot] #분할된 왼쪽 
    right_side=[x for x in tail if x>pivot] #분할된 오른 쪽

    return quick_sort(left_side)+[pivot]+quick_sort(right_side)

print(quick_sort(array))

 

시간 복잡도

O(NlogN)이다. 하지만, 피벗 값이 최소나 최대값으로 지정되어 파티션이 나누어지지 않았을 때 O(N^2)이다.

 

공간 복잡도

주어진 배열 안에서 교환을 통해 정렬이 수행되므로 O(N)이다.

 

장, 단점
장) 한 번 결정된 피벗들이 추후 연산에서 제외되는 특성 때문에 시간 복잡도가 O(NlogN)으로 빠르다.

단) 정렬된 배열에 대해서는 오히려 비효율적이다.