Python Algorithm class (Sorting - 정렬)

nathan·2021년 4월 7일

algorithm python sorting

Python Algorithm class

목록 보기

3/27

배울 내용

정렬
분할과 정복
재귀
분할과 정복에 의한 정렬 알고리즘(병합정렬과 퀵정렬)
힙정렬
Radix정렬

정렬(Sorting)

정렬 : 자료들을 크기 순서대로 (오름차순으로) 나열하는 것

정렬은 여러 응용분야에서 사용되는 매우 기본적인 문제이다.

간단한 정렬 알고리즘에는 다음과 같은 정렬들이 있다.
1. 선택정렬
2. 버블정렬
3. 삽입정렬
고급 정렬 알고리즘에는 다음과 같은 정렬들이 있다.
1. 분할과 정복 - 병합정렬(Merge sort)과 퀵정렬(Quick sort)
2. 힙정렬(heapsort) - 우선순위큐(priority queue)
3. 기수정렬(radix sort)

정렬 알고리즘 분류

1. Stable 정렬 알고리즘

정렬할 자료들(입력 자료) 중 동일한 두 자료의 상대적인 위치가 정렬 후에도 유지되는 정렬 알고리즘

2. In-place 정렬 알고리즘

입력(정렬할 자료)을 저장하는 메모리 공간 이외에 추가로 사용하는 메모리 공간이 O(1)인 정렬 알고리즘

(1) 선택정렬(Selection Sort)

기본 아이디어

각 루프마다 최대(최소) 원소를 찾는다.

최대(최소) 원소와 마지막(가장 앞에 있는) 원소를 교환한다.

마지막(가장 앞에 있는) 원소를 제외한다.

하나의 원소만 남을 때까지 위의 루프를 반복한다.

(1)-1 선택 정렬 프로그램 및 시간 분석

a=[3, 44, 38, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50]

n = len(a)

for i in range(n-1):    # loop n-1번 반복
    index = i  # 루프를 돌면서 가장 작은 원소를 찾아 그 인덱스를 저장
    for j in range(i, n-1):   # 가장 작은 수 찾기 위한 원소 비교횟수
        if a[index] >= a[j]:    
            index = j
    
    a[index], a[i] = a[i], a[index]

print(a)

입력 형태(정방향, 역방향)와 관계없이 모든 입력형태에 대하여 동일한 시간 복잡도가 걸림.

전체 원소 비교 횟수 : (n-1) + (n-2) + (n-3) + ... = n(n-1)/2

최악의 경우 시간 복잡도 : O(N^2)
= 가장 좋은 경우(best case) 시간 복잡도 = 평균적인 시간 복잡도

(2) 버블 정렬(Bubble sort)

기본 아이디어

매 단계마다 처음부터 마지막까지 차례대로 인접한 두 원소를 비교하여, 뒤에 있는 원소가 앞의 원소보다 작은 경우 두 원소를 교환

각 단계 수행 후 최댓값이 마지막으로 이동하므로, 마지막 원소는 정렬대상에서 제외

만약 끝까지 가면서 교환이 일어나지 않았으면, 정렬이 되어있는 것임.

(2)-1 버블 정렬 프로그램 및 시간 분석

a=[3, 44, 38, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50]

n = len(a)
# 마지막 부터 차곡차곡 쌓는다
for i in range(n-1, 0, -1):    # 마지막 원소는 자동으로 정렬!
    for j in range(i):
        if a[j] >= a[j+1]:
            a[j], a[j+1] = a[j+1], a[j]

print(a)

전체 원소 비교 횟수 : (n-1) + (n-2) + (n-3) + ... = n(n-1)/2

최악의 경우 시간 복잡도 : O(N^2)
= 가장 좋은 경우(best case) 시간 복잡도 = 평균적인 시간 복잡도

(2)-2 개선된 버블 정렬 알고리즘

핵심 : 정렬이 되는 순간 반복을 멈춘다.
(정렬 도중에 정렬이 끝났음을 알 수 있으면 됨)

Algorithm bubbleSort(a, n):
	for i = n-1 to 1 by -1
   	sorted = true
    	for j = 0 to i - 1
        	if(a[j] > a[j+1])
            	a[j]와 a[j+1]을 교환
                sorted = flase; 정렬이 되어 있지 않은 상태로 바꿈
        if (sorted)
        	break

아래는 파이썬 코드이다

a=[3, 44, 38, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50]

n = len(a)

for i in range(n-1, 0, -1):    # 마지막 원소는 자동으로 정렬!
    sorted_list = False
    for j in range(i):
        if a[j] >= a[j+1]:
            a[j], a[j+1] = a[j+1], a[j]
            sorted_list = True
        
        
    if sorted_list == False:
        break
print(a)

전체 원소 비교 횟수 =< (n-1) + (n-2) + (n-3) + ... = n(n-1)/2

최악의 경우 시간 복잡도 : O(N^2) (역순으로 정렬되어 있을 때)

가장 좋은 경우(best case) 시간 복잡도 : O(N) (정렬되어 있는 입력)

[버블 정렬 활용]
사다리타기에 이용할 수 있다!

버블 정렬의 횟수를 통하여 몇 개의 사다리를 놓아야 하는지 알 수 있다.
(개선된 버블정렬에서 사용해야 최솟값이 나온다.)

(3) 삽입 정렬(Insertion sort)

기본 아이디어

a[0]부터 a[i-1]까지 정렬되어 있을 때, a[i]까지 포함하여 정렬하는 알고리즘

(3)-1 삽입 정렬 프로그램 및 시간 분석

a=[3, 44, 38, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50]

n = len(a)

for i in range(1, n):
    temp = a[i]
    for j in range(i-1, -1, -1):
        if (a[j]>temp):
            a[j+1] = a[j]
        else:
            break
        a[j] = temp # 큰 것과 교환

print(a)