Do it! 자료구조와 함께 배우는 알고리즘 입문 [파이썬] #6장 정렬 알고리즘

[Do it! 자료구조와 함께배우는 알고리즘 입문] 내용을 정리한 내용입니다.

 

목차 

06-1 정렬 알고리즘

06-2 버블 정렬

06-3 단순 선택 정렬

06-4 단순 삽입 정렬

---

✔06-1 정렬 알고리즘

 

정렬 : 정렬이란 이름,학번, 학점 등의 키를 항목값의 대소 관계에 따라 데이터 집합을 일정한 순서로 바꾸어 늘어놓는 작               업을 말합니다.

 

오름차순: 작은 데이터를 앞쪽에 늘어놓은 것

내림차순: 큰 데이터를 앞쪽에 늘어놓은 것

 

정렬알고리즘

1. 안정적인 알고리즘
2. 안정적이지 않은 알고리즘

내부정렬과 외부정렬

• 내부 정렬: 정렬할 모든 데이터를 하나의 배열에 저장할 수 있는 경우에 사용하는 알고리즘
• 외부 정렬: 정렬할 데이터가 많아서 하나의 배열에 저장할 수 없는 경우에 사용하는 알고리즘

※ 정렬 알고리즘의 핵심은 교환, 선택, 삽입입니다

정렬 알고리즘은 데이터를 교환, 선택, 삽입하면서 정렬을 완료합니다. 대부분의 정렬 알고리즘은 이 3가지를 
응용하고 있으며, 앞으로 다룰 8가지의 알고리즘에서도 자주 등장하는 핵심 개념입니다.
앞으로 다룰 8가지 정렬 알고리즘은 버블정렬, 단순 선택정렬, 단순 삽입 정렬, 셸 정렬, 퀵 정렬, 병합 정렬
힙 정렬, 도수 정렬입니다.

---

✔06-2 버블 정렬

버블 정렬: 이웃한 두 원소의 대소 관계를 비교하여 필요에 따라 교환을 반복하는 알고리즘, 단순 교환정렬이라도 합니다.

 

버블정렬 알아보기

6

4

3

7

1

9

8

9와 8을 오름차순으로 정렬하면

8

4

3

7

1

8

9

9와 8의 위치가 바뀌고 1과 8은 오름차순으로 되어있으므로 바뀌지 않아도 됩니다.

이렇게 이웃한 원소를 비교하고, 필요하면 교환하는 전체 작업 과정을 패스(pass)라고 합니다.

 

✔Do it! 실습6-1

# [실습6-1] 버블 정렬 알고리즘 구현하기

from typing import MutableSequence

def bubble_sort(a: MutableSequence) -> None:
    """버블 정렬"""
    n = len(a)
    for i in range(n - 1):
        for j in range(n - 1, i, -1):		# 09~11 패스(pass)
            if a[j - 1] > a[j]:
                a[j - 1], a[j] = a[j], a[j - 1] # 교환정렬

if __name__ == '__main__':
    print('버블 정렬을 수행합니다.')
    num = int(input('원소 수를 입력하세요.: '))
    x = [None] * num                            # 원소 수가 num인 배열을 생성

    for i in range(num):
        x[i] = int(input(f'x[{i}]: '))

    bubble_sort(x)				# 배열 x를 버블 정렬

    print('오름차순으로 정렬했습니다.')
    for i in range(num):
        print(f'x[{i}] = {x[i]}')

 

✔문제풀이

 

0

1

4

6

4

5

8

7

9

버블정렬은 1칸이상 떨어져 있는 원소를 교환하는 것이 아니라 서로 이웃한 원소만 교환하므로 안정적입니다.

원소를 비교하는 횟수는 첫 번째 패스에서는 n - 1번, 두번째 패스에서는 n - 2번 이므로 합계는 다음과 같습니다.

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

그런데 실제 원소를 교환하는 횟수는 평균값의 비교 횟수 전체의 절반인 n(n - 1) / 4 번 입니다.

 

 

✔Do it! 실습6-2

# [실습6-2] 버블 정렬 알고리즘 구현하기

from typing import MutableSequence

def bubble_sort_verbose(a: MutableSequence) -> None:
    """버블 정렬(정렬 과정을 출력)"""
    ccnt = 0  # 비교 횟수
    scnt = 0  # 교환횟수
    n = len(a)
    for i in range(n - 1):
        print(f'패스 {i + 1}')
        for j in range(n - 1, i, -1):
            for m in range(0, n - 1):
              print(f'{a[m]:2}' + ('  ' if m != j - 1 else
                                   ' +' if a[j - 1] > a[j] else ' -'),
                                   end ='')
              print(f'{a[n - 1]:2}')
              ccnt += 1
              if a[j - 1] > a[j]:
                  scnt += 1
                  a[j - 1], a[j] = a[j], a[j - 1]
              for m in range(0, n - 1):
                  print(f'{a[m]:2}', end='  ')
              print(f'{a[n - 1]:2}')
        print(f'비교를 {ccnt}번 했습니다.')
        print(f'교환을 {scnt}번 했습니다.')
#(생략...)

 

✔셰이커 정렬 : 홀수 번째의 패스는 가장 작은 요소가 맨 앞에 오도록 교환하고, 짝수 번째의 패스는 가장 큰 요소가 맨 뒤                             에 오도록 교환한다.

 

✔Do it! 실습6-5

# [실습6-5] 셰이커 정렬 알고리즘 구현하기

from typing import MutableSequence

def shaker_sort(a: MutableSequence) -> None:
    """셰이커정렬"""
    left = 0
    right = len(a) - 1
    last = right
    while left < right:
        for j in range(right, left, -1):
            if a[j - 1] > a[j]:
                a[j - 1], a[j] = a[j], a[j - 1]
                last = j
        left = last

        for j in range(left, right):
            if a[j] > a[j + 1]:
                a[j]. a[j + 1] = a[j + 1], a[j]
                last = j
        right = last
# 생략

✔문제풀이

실습 6-5는 while문 안에 for문이 2개 들어 있는 구조입니다. 변수left는 스캔 범위의 첫 원소 인덱스이며, right는 스캔 범위의 마지막 원소 인덱스 입니다.

 

✔보충 수업 6-1 산술 연산에 사용하는 내장 함수

abs(x)	x의 절대값을 반환합니다.
bool(x)	x의 논리값을 반환합니다.
complex(real, imag)	real + imag * 1j인 복소수를 반환하거나, 문자열 또는 수를 복소수로 변환한 값을 반환합니다. imag를 생략하면 real + 0j를, real과 imag 둘다 생략한다면 0j를 반환합니다.
divmod(a, b)	a를 b로 나누었을 때의 몫과 나머지로 구성된 튜플을 반환합니다.
float(x)	문자열 또는 수로 입력받은 x를 부동 소수점 수로 변환하여 값을 반환합니다. x를 생략하면 0.0을 반환합니다.
hex(x)	정숫값 x의 16진수 문자열을 반환합니다.
int(x, base)	x를 int형 정수로 변환한 값을 반환합니다. base는 0~36의 범위에서 진수를 나타내야하며, 생략할 경우 10진법입니다.
max(args1, args2, ...)	인수의 최대값을 반환합니다.
min(args1, args2, ...)	인수의 최솟값을 반환합니다.
oct(x)	정숫값 x에 해당하는 8진수 문자열을 반환합니다.
pow(x, y, z)	x의 y 제곱인 (x ** y)를 반환합니다. z값을 입력하면 x의 y제곱을 z로 나누었을 때의 나머지를 반환합니다. 같은 식인 pow(x, y) & z보다 효율적으로 계산할 수 있습니다.
round(n, ndigits)	n의 소수부를 ndigits 자릿수가 되도록 반올림한 값을 반환합니다. ndigits가 None이거나 생략한 경우 입력한 값에 가장 가까운 정수를 반환합니다.
sum(x, start)	x의 원솟값을 처음부터 끝까지 순서대로 더한 총합에 start값을 더하여 반환합니다. start의 기본값은 0입니다.

---

✔06-3 단순 선택 정렬

단순 선택 정렬 : 가장 작은 원소부터 선택해 알맞은 위치로 옮기는 작업을 반복하며 정렬하는 알고리즘입니다.

1.아직 정렬하지 않은 부분에서 값이 가장 작은 원소 a[min]을 선택합니다.
2.a[min]과 아직 정렬하지 않은 부분에서 맨 앞에 있는 원소를 교환합니다.

for i in range(n - 1):
	min # a[i], ..., a[n - 1]에서 키 값이 가장 작은 원소의 인덱스
    a[i]와 a[min]의 값을 교환합니다.

---

✔06-4 단순 삽입 정렬

단순 삽입 정렬 : 주목한 원소보다 더 앞쪽에서 알맞은 위치로 삽입하며 정렬하는 알고리즘입니다. 단순 선택 정렬과 비슷해 보이지만                                값이 가장 작은 원소를 선택하지 않는다는 점이 다릅니다.

 

for i in range(1, n):
    tmp <- a[i]를 넣습니다.
    tmp a[0], ..., a[i - 1]의 알맞은 위치에 삽입합니다.

 

※버블, 선택, 삽입정렬의 시간복잡도는 모두O(n^2)으로 프로그램 효율이 좋지 않습니다.

 

정렬알고리즘 문제 모음
https://www.acmicpc.net/workbook/view/10413
https://www.acmicpc.net/workbook/view/9900