4. 정렬 - 1(선택정렬, 버블정렬, 삽입정렬)

2021.09.23 - [알고리즘] - 0. 알고리즘 공부 시작

2021.09.24 - [알고리즘] - 1. 알고리즘(Algorithm)이란?

2021.09.26 - [알고리즘] - 2. 알고리즘 점근적 표기 및 시간 복잡도

2021.09.26 - [알고리즘] - 3. 점근적 표기법(o-표기법, ω-표기법)

2021.10.19 - [알고리즘] - 4. 정렬 - 1(선택정렬, 버블정렬, 삽입정렬)

2021.10.20 - [알고리즘] - 5. 정렬 - 2(합병 정렬, 퀵 정렬)

 

 

사실 수업 초기에는 욕이 많이 나왔다.

내가 상상하던 알고리즘가 다르게 이상한 계산식만 나왔기 때문이다.

중간고사 공부하는 지금도 사실 욕이 나온다.

 

드디어 내가 상상하던 부분에 도입됬다.

 

바로 정렬이다.

 

정렬 알고리즘이란?

원소들을 번호순이나 사전 순서와 같이 일정한 순서대로 열거하는 것을 정렬 알고리즘이라고 한다.

즉 쉽게 말해서 말그대로 순서대로 배열한다.

숫자가 크거나 작은 순

a~z순 같은 느낌이다.

 

이게 뭐라고 이러지라고 생각 할 수 있지만

정렬은 생각보다 성능에 중요한 역활을 하기도 한다.

 

우선 처음으로 배워볼 정렬은

 

1. 선택정렬(Select Sort)

선택 정렬은 정렬 알고리즘 중에서 간단한 알고리즘 중 하나이다.

 

1. 배열에서 가장 작은 값을 찾은 후 선택한다.

2. 첫번째 자리와 위치를 바꾼다.

3. 첫번째를 제외한 배열 중 가장 작은 값을 찾는다.

4. 두번째 자리와 위치를 바꾼다.

위 과정을 반복하여 정렬한다.

 

내가 본 책에서는 가장 큰 값을 찾은 후 가장 오른쪽에 정렬했는데 찾아보니 통상적으로는 가장 작은 값을 가장 왼쪽에 정렬하는 방식으로 진행되어서 작은 값 기준으로 적었다.

  #참고로 이렇게 받으면 문자로 받기때문에 숫자로 형변환을 해줘야 하지만 직관적인 이해를 위해 스킵하겠다.
 a = input().split(' ') #여러 값을 받아서 리스트형태로 저장한다.
 
 minIndex = 0
 
 for i in range(len(a) - 1):
 	minIndex = i
    
    for j in range(i + 1, len(a) - 1):
    	if(a[minIndex] > a[j]):
        	minIndex = j
    
    a[minIndex], a[i] = a[i], a[minIndex]

 

Θ(n**2)의 복잡도를 가진다.

 

입력된 값을 n이라 했을 때 처음에는 n-1만큼 반복이 되고

n-1인 이유는 정렬이 진행될 수록 좌측을 제외한 우측의 값을 비교하게 되는데 가장 우측 즉 정렬의 마지막은 비교 대상이 없고 또한 이미 제일 우측에 i값이 도달했을때는 정렬이 완료됬기 때문에 정렬할 필요도 없다.

 

그러므로 수를 비교하는 총 횟수는

(n - 1) + (n - 2) + (n - 3) + ... + 2 + 1이다. 어디서 많이 본 공식이 아닌가?

내 기억상 시그마 공식과 비슷하다. 시그마 공식에서 n-1로 대입하게 되면

 

n(n - 1) / 2라는 값이 나온다.

T(n) = n(n - 1) / 2인것이다.시간 복잡도에서 사소한 값을 버리기 때문에 Θ(n**2)의 복잡도를 가지는것이다.

 

개인적으로 책의 설명이 너무 어렵다.

 

2. 버블정렬(Bubble Sort)

 

 

버블 정렬은 선택정렬처럼 제일 작은 원소를 끝자리로 옮기는 작업을 반복하지만 제일 작은 원소를 옮기는 방법이 다르다.이 역시도 통상적으로는 가장 작은 값을 쓰지만 책에서는 가장 큰 값을 찾는다.

 

또한 시간복잡도가 좋은 퍼포먼스를 못내서 잘 사용안한다고 한다.

 

진행되는 방식은

 

1. 가장 처음 값을 선택한다.2. 비교해서 처음 값이 더 크면 우측으로 이동3. 우측으로 이동 후 다시 이동한 선택값의 우측값과 비교한다.3. 만약 선택 값보다 비교 값이 더 크면 비교값을 선택하고 그 우측의 값과 비교를 한다.4. 이렇게 우측 끝에는 가장 큰 값이 위치하게 된다.5. 우측 끝을 제외하고 다시 반복한다. 그리고 우측끝의 바로 옆을 다시 제외하고 비교한다.위 과정을 반복하여 정렬을 완료한다.

 

 a = input().split(' ')
 
 for i in range(len(a) - 1, 0, -1):
 	sortedBool = True
    
 	for j in range(i - 1):
    	if(a[i] < a[i + 1]):
        	a[i], a[i + 1] = a[i + 1], a[i]
            sortedBool = False
            
        if(sortedBool == True): break

정렬이 완료되도 도는걸 방지하기 위해 sortedBool이라는 변수를 둔다. 

 

시간 복잡도는

 

T(n) = (n -1) + (n - 2) + ... + 2 + 1 = n(n - 1) / 2

선택정렬과 마찬가지로

 

Θ(n**2)이다.

 

3. 삽입 정렬(Insert Sort)

삽입 정렬은 선택 된 값보다 아래에 위치하는 Index들을 보면서 자신보다 작은 값이 나오면 그 우측에 위치하도록 삽입하여 정렬하는 방식이다.

 

진행 방식은1. 두번째 값부터 선택2. 좌측 값과 비교하여 선택값이 작으면 그 다음 Index와 비교한다.3. 선택값보다 비교값이 작다면 그 우측에 Insert한다.4. 이를 반복하여 배열을 정렬한다.

 

 

a = input().split()

for i in range(1, len(a)):
	for j in range(0,i):
    	if(j == 0 or a[i] > a[j]):
            a.insert((j + 1), a[j])
            del a[i]
            break

삽입정렬은 최악의 경우 O(n**2)이지만 운이 좋다면 최악보다 절반 정도가 될 수도 있다.

하지만 그럼에도 Θ(n**2)의 시간 복잡도를 가지는것은 마찬가지이다.

 

T(n) = n(n - 1) / 2으로 위와 비슷한 시간 복잡도를 가지지만 경우에 따라서는 O(n)도 가능하다.