[자료구조 및 알고리즘] 기본 정렬

정렬이란?

원소를 순서대로 배열하는 것

크기가 크거나 작은 순으로 정렬을 비롯하 알파벳, 생년월일 순으로 정리하는 것 모두 포함

 

정렬의 종류

- 기본정렬 : 평균적으로 n^2의 시간이 소요되는 기본적인 정렬알고리즘

- 고급정렬 : 평균적으로 nlogn의 시간이 소요되는 고급 정렬 알고리즘

- 특수정렬 : 특수한 성질을 만족하고 평균적으로 n의 시간이 소요되는 정렬 알고리즘

 

오늘 정리할 기본정렬에는 선택정렬, 버블정렬,삽입정렬이 있다.

평균적으로 n의 제곱만큼의 시간이 소요된다.

---

 

- 선택정렬

기본 원리

1. n개의 원소로 된 리스트 A[0,1,2.....,n-1]에서 가장 큰 원소를 찾는다

2. 가장 큰 원소와 리스트의 맨 끝자리 원소 A[n-1]과 자리를 바꾸고 맨 오른쪽 자리를 관심대상에서 제외

원소가 1개 남을 때 까지 반복

 

작동 과정

1) 주어진 배열(n=10)에서 가장 큰 수(노랑) 찾기

8

31

48

73

3

65

20

29

11

15

 

2) 가장 큰 수(노랑)와 맨 오른쪽 수(15)와 자리를 바꾸고 맨 오른쪽 자리를 관심대상에서 제외(하늘색)

8

31

48

15

3

65

20

29

11

73

반복

8

31

48

15

3

65

20

29

11

73

8

31

48

15

3

11

20

29

65

73

8

31

48

15

3

11

20

29

65

73

8

31

29

15

3

11

20

48

65

73

8

31

29

15

3

11

20

48

65

73

8

20

29

15

3

11

31

48

65

73

8

20

29

15

3

11

31

48

65

73

8

20

11

15

3

29

31

48

65

73

8

20

11

15

3

29

31

48

65

73

8

3

11

15

20

29

31

48

65

73

8

3

11

15

20

29

31

48

65

73

8

3

11

15

20

29

31

48

65

73

8

3

11

15

20

29

31

48

65

73

8

3

11

15

20

29

31

48

65

73

8

3

11

15

20

29

31

48

65

73

3

8

11

15

20

29

31

48

65

73

최종배열

 

시간 복잡도 

- 가장 큰수를 찾는 노랑색으로 표시된 theLargest()가 9번(n-1) 호출됨

- theLargest()가 호출될때마다 수행시간은 줄어듦 n-1 > n-2 > .... > 1

총 수행시간 = (n-1) + (n-2) + ..... +2 +1 = n(n-1)/2 

평균적으로 n^2의 수행시간

 

- 구현 코드

def selectionSort(A):
	for last in range(len(A)-1, 0,-1):        # 반복할때마다 고려하는 리스트의 범위가 줄어듦
    	k = theLargest(A,last)                # theLargest() 호출 가장 큰 원소가 들어있는 원소번호 k로 받기
        A[K], A[last] = A[last], A[k]         # 가장 큰 원소와 고려하는 리스트 범위의 가장 마지막 원소랑 교환
        
def theLargest(A, last):                      # 리스트와 고려하는 범위를 인자로 받음
	largest = 0                               # 초기값을 0으로 설정
    for i in range(last + 1):                 # 0부터 last까지 반복
    	if A[i] > A[largest]:			      # 첫번째 원소부터 순차적으로 크기 비교
        	largest = i                       # 큰 값이 나올때마다 largest에 할당
    return largest                            # 가장 큰 원소번호 리턴

 

 

---

- 버블정렬

선택 정렬과 유사한 아이디어에 기반

선택 정렬과 동일하게 제일 큰 원소를 끝자리로 옮기는 작업을 반복 하지만 제일 큰 원소를 오른쪽으로 옮기는 방법이 다르다.

 

기본원리

1. 맨 앞부터 이동하면서 연속된 두 원소를 선택

2. 두 원소가 순서대로 정렬되어 있지 않으면 자리 바꿈(큰수를 한칸 뒤로)

3. 리스트 끝까지 반복한 뒤 맨 오른쪽 자리를 관심 대상에서 제외

원소가 1개 남을 때 까지 반복

 

작동과정

주어진 배열(n = 10)

1) 왼쪽부터 이웃한 쌍을 비교(하늘색) 순서대로 이루어져 있으면 그대로 유지

3

31

48

73

8

11

20

29

65

15

2) 순서대로 되어 있지 않으면 자리를 바꾼다(노랑)

3

31

48

73

8

11

20

29

65

15

3

31

48

8

73

11

20

29

65

15

3

31

48

8

73

11

20

29

65

15

3

31

48

8

11

73

20

29

65

15

3

31

48

8

11

73

20

29

65

15

3

31

48

8

11

20

73

29

65

15

3

31

48

8

11

20

73

29

65

15

3

31

48

8

11

20

29

73

65

15

3

31

48

8

11

20

29

73

65

15

3

31

48

8

11

20

29

65

73

15

3

31

48

8

11

20

29

65

73

15

3

31

48

8

11

20

29

65

15

73

한 사이클이 완료되면 가장 큰 원소가 맨 오른쪽에 위치하게 된다.

이제 관심범위를 줄여 n-1개의 원소를 대상으로 같은 사이클을 반복하며 정렬을 진행한다.

 

---

3

8

11

15

20

29

31

48

65

73

최종배열

시간복잡도

한 사이클이 완료될때마다 관심대상이 하나씩 줄어들어 이웃된 두 쌍을 비교하고 정렬하는 과정이 한번씩 줄어들게 된다.

이웃한 두쌍을 비교하는 작업의 총 수가 수행시간을 좌우하게 된다.

(n-1) + (n-2) + ... + 2 + 1 = n(n-2)/2 = 평균 n^2의 수행시간(선택정렬과 처럼 최악의 경우와 평균의 경우 동일)

 

구현 코드

def bubbleSort(A):
	for numElements in range(len(A)-1, 0, -1):       # 사이클이 돌때마다 관심범위가 한칸 씩 줄어듦
    	for i in range(numElements):            # 관심범위안에 원소 수만큼 반복
        	if A[i] > A[i+1]:                  # 이웃한 두쌍의 크기 비교
            	A[i], A[i+1] = A[i+1], A[i]   # 정렬되어 있지 않으면 자리바꾸기

 

 

---

- 삽입정렬

선택 정렬과 버블 정렬은 정렬되지 않은 배열의 크기가 하나씩 작아지는 알고리즘이지만

삽입정렬은 정렬된 배열의 크기가 하나씩 커지는 알고리즘

 

기본원리

이미 정렬된 i개 짜리 리스트에 하나의 원소를 더하여 정렬된 i + 1개 짜리 리스트를 만든다.

 

작동과정

주어진 배열(n = 10)

1) 정렬된 리스트의 범위(하늘색)를 늘여나감

3

31

48

73

8

33

11

15

20

65

2) 리스트의 범위를 확장하려고 하자 정렬이 되어있지 않음(빨강)

3

31

48

73

8

33

11

15

20

65

3)  추가되는 원소를 적절한 위치에 삽입하고 해당 원소보다 큰 원소들은 한칸씩 뒤로 밀림

3

8

31

48

73

33

11

15

20

65

3

8

31

48

73

33

11

15

20

65

3

8

31

48

73

33

11

15

20

65

3

8

31

33

48

73

11

15

20

65

3

8

31

33

48

73

11

15

20

65

3

8

31

33

48

73

11

15

20

65

3

8

11

31

33

48

73

15

20

65

3

8

11

31

33

48

73

15

20

65

3

8

11

31

33

48

73

15

20

65

3

8

11

15

31

33

48

73

20

65

3

8

11

15

31

33

48

73

20

65

3

8

11

15

31

33

48

73

20

65

3

8

11

15

20

31

33

48

73

65

3

8

11

15

20

31

33

48

73

65

3

8

11

15

20

31

33

48

73

65

3

8

11

15

20

31

33

48

65

73

3

8

11

15

20

31

33

48

65

73

최종배열

 

시간복잡도

한 사이클이 돌때마다 원소가 하나씩 삽입되어 반복작업 획수가 늘어가나게 됨

비교횟수와 이동횟수중 큰 값이 수행시간을 좌우

1+2+...+(n-1) = n(n-1)/2 = 평균 n^2의 수행시간(최악의 경우 - 모든 경우 shift가 이루어지는 경우)

{1+2+...+(n-1)}/2 = n(n-1)/4 = 평균 n^2의 수행시간 (보통의 경우 - shift가 이루어지는 경우와 아닌경우 반반)

1+ 1+ 1+....+1 = n-1 = 평균 n의 수행시간(최고의 경우 - 이미 정렬되어있어 삽입이 필요없는경우)

 

구현코드

def insertionSort(A):
	for i in range(1,len(A)):                 # 관심범위를 한칸씩 늘임
    loc = i-1                            # 관심범위의 마지막 원소 위치
    newItem = A[i]                       # 새로게 추가될 원소를 newItem에 할당
    while loc >= 0 and newItem < A[loc]:      # newItem이 배정될 위치 찾기
    	A[loc+1] = A[loc]               # newItem보다 큰 원소는 한칸씩 뒤로 미루기
        loc -= 1                          # 위치조정
    A[loc+1] = newItem                 # 적절한 위치에 배정