[Python] 정렬(Sort) : 선택 정렬, 삽입 정렬, 버블 정렬, 퀵 정렬

정렬(Sort)

정렬의 기본

정렬의 개념

• 정렬(Sort) : 자료들을 일정한 순서대로 나열하는 것
• 순서대로 나열할 때는 작은 것부터 나열하는 방법(오름차순)과 큰 것부터 나열하는 방법(내림차순)이 있다.
  • 오름차순 정렬(Ascending Sort) : 작은 것부터 큰 순으로 나열된 방법
  • 내림차순 정렬(Descending Sort) : 큰 것부터 작은 순으로 나열된 방법
• 정렬의 대표적인 예 : 사전

 

정렬 알고리즘의 종류

• 오름차순 정렬이든 내림차순 정렬이든 결과의 형태만 다를 뿐, 같은 방식으로 처리된다.
• 정렬하는 방법에 대한 알고리즘은 수십 가지이다.
  • 이해하고 구현하기 쉽지만 속도가 느린 알고리즘
  • 이해와 구현이 어렵지만 속도가 빠른 알고리즘
  • 특수한 상황에서만 효율적인 알고리즘
  • 메모리를 적게 사용하는 알고리즘 등
• 그 중 대표적으로 다음과 같은 정렬 알고리즘이 주로 쓰인다.
  • 선택 정렬(Selection Sort)
  • 삽입 정렬(Insertion Sort)
  • 버블 정렬(Bubble Sort)
  • 퀵 정렬(Quick Sort)

 

정렬 알고리즘의 원리와 구현

① 선택 정렬(Selection Sort)

개념

• 여러 데이터 중에서 가장 작은 값을 뽑는 동작을 반복하여 값을 정렬하는 방법

 

최솟값을 찾는 방법

• 선택 정렬을 구현하려면 가장 작은 값을 찾는 함수가 필요하다.
• 최솟값은 다양한 방법으로 찾을 수 있지만, 여기에서는 다음 방식을 사용한다.

① 배열의 첫 번째 값을 가장 작은 값으로 지정한다.
② 가장 작은 값으로 지정한 값을 다음 차례의 값과 비교하여 가장 작은 값을 변경하거나 그대로 두는 방법으로 마지막 값까지 비교를 마친 후, 현재 가장 작은 값으로 지정된 값을 가장 작은 값으로 결정한다.

 

구현

def findMinIdx(ary) :
    minIdx = 0
    for i in range(1, len(ary)) :
        if (ary[minIdx] > ary[i]) :
            minIdx = i
        return minIdx

testAry = [55, 88, 33, 77]
minPos = findMinIdx(testAry)
print('최솟값 -->', testAry[minPos])

최솟값 --> 55

 

구현

• 파이썬에서 제공하는 가변 크기의 배열(리스트)을 사용한다.
• 빈 배열을 준비한 후, append() 함수로 배열에 값을 추가하면 배열 크기가 자동으로 늘어난다.

ary = []
ary.append(100)
ary.append(200)
ary.append(300)

 

구현

def findMinIdx(ary) :
    minIdx = 0
    for i in range(1, len(ary)) :
        if (ary[minIdx] > ary[i]) :
            minIdx = i
    return minIdx
	
before = [188, 162, 168, 120, 50, 150, 177, 105]
after = []

print('정렬 전 -->', before)
for _ in range(len(before)) :
    minPos = findMinIdx(before)
    after.append(before[minPos])
    del(before[minPos])
print('정렬 후 -->', after)

정렬 전 --> [188, 162, 168, 120, 50, 150, 177, 105]
정렬 후 --> [50, 105, 120, 150, 162, 168, 177, 188]

 

두 변수 값 교환

• 알고리즘을 구현할 때, 두 변수 값을 교환해야 하는 경우가 종종 생긴다.
• 일시적으로 한 번에 두 변수의 값을 교환할 수 없으므로, 임시 공간을 사용해야 한다.

temp = A
A = B
B = temp

 

• 파이썬은 임시 공간 없이 A 변수와 B 변수를 한 행으로 변경하는 문법을 제공한다.

A, B = B, A

 

개선된 선택 정렬 구현

• 앞에서는 선택 정렬 전 배열, 정렬 후 배열 2개를 사용했다. 
• 하지만, 배열 하나로 데이터를 정렬하는 방식이 더 효율적이다.
• '배열크기 - 1' 회의 큰 반복을 하고, 이 큰 반복을 사이클(Cycle)이라고 할 때, 데이터가 4개인 배열은 총 3회의 사이클로 선택 정렬을 수행할 수 있다.
  • 반복되는 변수를 i라고 하면, i는 0, 1, 2로 3회 반복하는 것이다.

 

구현

def selectionSort(ary) :
    n = len(ary)
    for i in range(0, n-1) :
        minIdx = i
        for k in range(i+1, n) :
            if (ary[minIdx] > ary[k]) :
                minIdx = k
        tmp = ary[i]
        ary[i] = ary[minIdx]
        ary[minIdx] = tmp

    return ary

dataAry = [188, 162, 168, 120, 50, 150, 177, 105]

print('정렬 전 -->', dataAry)
dataAry = selectionSort(dataAry)
print('정렬 후 -->', dataAry)

정렬 전 --> [188, 162, 168, 120, 50, 150, 177, 105]
정렬 후 --> [50, 105, 120, 150, 162, 168, 177, 188]

 

성능

• 정렬에서 중요한 사항 중 하나는 정렬을 완료하는 비교 횟수이다.
• 위의 코드에서 이중 반복문이 사용되므로, 성능 측정을 위한 빅-오(Big-Oh) 표기법대로 하면 선택 정렬의 연산 수는 `O(n^{2})`이 된다.

 

② 삽입 정렬(Insertion Sort)

개념

• 기존 데이터 중에서 자신의 위치를 찾아 데이터를 삽입하는 정렬 방법

 

삽입 위치를 찾는 방법

• 삽입 정렬을 구현하려면 먼저 현재 값을 배열 중에 삽입할 위치를 찾는 함수가 필요하다.
• 삽입 정렬의 전제 조건은 삽입할 위치를 찾는 기존 배열은 이미 정렬되어 있다는 점이다.

1. 빈 배열일 때는 첫 번째 자리에 삽입한다.
2. 배열에 삽입할 값보다 큰 값이 있을 때는 처음부터 비교해 가면서 자신보다 큰 값을 만나면 그 값 바로 앞에 삽입한다.
3. 배열에 삽입할 값보다 큰 값이 없을 때는 맨 뒤에 삽입한다.

 

• 빈 배열일 때(1)와 배열에 삽입할 값보다 큰 값이 없을 때(3)는 동일하게 동작한다.
  • 둘 다 자신보다 큰 값이 없으므로, 현재 배열의 맨 뒤에 삽입된다.
    • 빈 배열일 때는, 맨 뒤가 첫 번째가 되는 것이다.

구현

def findInsertIdx(ary, data) :
    findIdx = -1			# 초깃값은 없는 위치로
    for i in range(0, len(ary)) :
        if (ary[i] > data) :
            findIdx = i
            break
    if findIdx == -1 :			# 큰 값을 못찾음 == 제일 마지막 위치
        return len(ary)
    else :
        return findIdx

testAry = []
insPos = findInsertIdx(testAry, 55)
print('삽입할 위치 -->' , insPos)

testAry = [33, 77, 88]
insPos = findInsertIdx(testAry, 55)
print('삽입할 위치 -->' , insPos)

testAry = [33, 55, 77, 88]
insPos = findInsertIdx(testAry, 100)
print('삽입할 위치 -->' , insPos)

삽입할 위치 --> 0
삽입할 위치 --> 1
삽입할 위치 --> 4

 

구현

• 파이썬에서 제공하는 insert(삽입할 위치, 값) 함수를 사용하면 간단하게 배열에 데이터를 삽입할 수 있다.

testAry = []
testAry.insert(0, 55)
testAry

testAry = [33, 77, 88]
testAry.insert(1, 55)
testAry

testAry = [33, 55, 77, 88]
testAry.insert(4, 100)
testAry

[55]
[33, 55, 77, 88]
[33, 55, 77, 88, 100]

 

구현

def findInsertIdx(ary, data) :
    findIdx = -1			# 초깃값은 없는 위치로
    for i in range(0, len(ary)) :
        if (ary[i] > data ) :
            findIdx = i
            break
    if findIdx == -1 :			# 큰 값을 못찾음 == 제일 마지막 위치
        return len(ary)
    else :
        return findIdx

before = [188, 162, 168, 120, 50, 150, 177, 105]
after = []

print('정렬 전 -->', before)
for i in range(len(before)) :
    data = before[i]
    insPos = findInsertIdx(after, data)
    after.insert(insPos, data)
print('정렬 후 -->', after)

정렬 전 --> [188, 162, 168, 120, 50, 150, 177, 105]
정렬 후 --> [50, 105, 120, 150, 162, 168, 177, 188]

 

삽입 정렬의 효율적인 구현

• 앞에서는 삽입 정렬 전 배열, 정렬 후 배열 2개를 사용했다. 
• 하지만, 배열 하나로 데이터를 정렬하는 방식이 더 효율적이다.
• '배열크기 - 1' 회의 큰 반복을 하고, 이 큰 반복을 사이클(Cycle)이라고 할 때, 데이터가 4개인 배열은 총 3회의 사이클로 삽입 정렬을 수행할 수 있다.
  • 처음에는 앞 2개를, 다음에는 3개를, 그 다음에는 4개를 처리하게 된다.
• 삽입할 위치를 찾는 함수를 없애고, 정렬 함수인 insertionSort() 에서 모두 처리하도록 한다.

 

구현

def insertionSort(ary) :
    n = len(ary)
    for end in range(1, n) :
        for cur in range(end, 0, -1) :
            if (ary[cur-1] > ary[cur]) :
                ary[cur-1], ary[cur] = ary[cur], ary[cur-1]
    return ary

dataAry = [188, 162, 168, 120, 50, 150, 177, 105]

print('정렬 전 -->', dataAry)
dataAry = insertionSort(dataAry)
print('정렬 후 -->', dataAry)

정렬 전 --> [188, 162, 168, 120, 50, 150, 177, 105]
정렬 후 --> [50, 105, 120, 150, 162, 168, 177, 188]

 

성능

• 선택 정렬(Selection Sort)와 마찬가지로 이중 반복문이 사용되므로, 성능 측정을 위한 빅-오(Big-Oh) 표기법대로 하면 선택 정렬의 연산 수는 `O(n^{2})`이 된다.

 

 

③ 버블 정렬(Bubble Sort)

개념

• 첫 번째 값부터 시작해서 바로 앞뒤 데이터를 비교하여 큰 것은 뒤로 보내는 방법을 사용하는 정렬
• 각 사이클이 끝날 때마다 마지막 위치에 가장 큰 데이터가 자리 잡는다.
• 정렬을 위해 비교하는 모양이 거품(Bubble)처럼 생겼다고 해서 '버블 정렬'이라고 한다.

 

구현

• 배열 하나에 4개의 데이터를 버블 정렬함으로써 원리를 알아보자.
• '배열크기 - 1'번 사이클을 반복하므로 3회 사이클을 반복하고, 사이클1은 전체 4개의 데이터를, 사이클2는 앞부터 3개, 사이클3은 앞부터 2개 데이터를 처리한다.

4

3

2

1

 

 

사이클1 

• 데이터 4개 중, 앞부터 2개씩을 비교해서 큰 것을 뒤로 보낸다.

4

3

2

1

3

4

2

1

3

2

4

1

3

2

1

4

 

사이클2

• 데이터 3개 중, 앞부터 2개씩을 비교해서 큰 것을 뒤로 보낸다.

3

2

1

4

2

3

1

4

2

1

3

4

 

사이클3

• 데이터 2개 중, 앞부터 2개씩 비교해서 큰 것을 뒤로 보낸다.

2

1

3

4

1

2

3

4

 

1

2

3

4

 

구현

def BubbleSort(ary) :
    n = len(ary)
    for end in range(n-1, 0, -1) :
        for cur in range(0, end) :
            if (ary[cur] > ary[cur+1]) :
                ary[cur], ary[cur+1] = ary[cur+1], ary[cur]
    return ary

dataAry = [188, 162, 168, 120, 50, 150, 177, 105]

print('정렬 전 -->', dataAry)
dataAry = BubbleSort(dataAry)
print('정렬 후 -->', dataAry)

정렬 전 --> [188, 162, 168, 120, 50, 150, 177, 105]
정렬 후 --> [50, 105, 120, 150, 162, 168, 177, 188]

 

성능과 특이점

• 버블 정렬도 삽입 정렬, 선택 정렬과 마찬가지로 연산 수는 `O(n^{2})`이다.
• 정렬할 데이터 개수가 작다면 별 문제가 안 되지만, 데이터 개수가 커질수록 기하급수적으로 비교 횟수(또는 연산 횟수)가 늘어나기에 성능이 좋지 않은 알고리즘이라고 볼 수 있다.
• 하지만, 버블 정렬은 기존에 배열이 어느 정도 정렬되어 있다면 연산 수가 급격히 줄어든다.
• 사이클 중간에서 이미 정렬된 상태일 때, 더 이상 사이클을 진행하지 않고 종료하는 버블 정렬을 구현할 수 있다.

 

구현

def bubbleSort(ary) :
    n = len(ary)
    for end in range(n-1, 0, -1) :
        changeYN = False
        print('#사이클-->', ary)
        for cur in range(0, end) :
            if (ary[cur] > ary[cur+1]) :
                ary[cur], ary[cur+1] = ary[cur+1], ary[cur]
                changeYN = True
        if not changeYN :
            break
    return ary

dataAry = [50, 105, 120, 188, 150, 162, 168, 177]

print('정렬 전 -->', dataAry)
dataAry = bubbleSort(dataAry)
print('정렬 후 -->', dataAry)

정렬 전 --> [50, 105, 120, 188, 150, 162, 168, 177]
#사이클--> [50, 105, 120, 188, 150, 162, 168, 177]
#사이클--> [50, 105, 120, 150, 162, 168, 177, 188]
정렬 후 --> [50, 105, 120, 150, 162, 168, 177, 188]

 

④ 퀵 정렬(Quick Sort)

개념

• 기준을 하나 뽑은 후, 기준보다 작은 그룹과 큰 그룹으로 나누어 다시 각 그룹으로 정렬하는 방법
• 이때, 나눈 그룹을 다시 정렬하고자 재귀 호출을 하고, 각 그룹의 정렬이 완료되면 합치는 방식을 사용한다.

 

구현

• 퀵 정렬에서는 기준(Pivot)을 선정하는 것이 첫 과정이다.
• 기준은 어떤 것을 선정해도 상관 없지만, 일반적으로 중간에 위치한 데이터를 선정한다.

 

구현

def quickSort(ary) :
    n = len(ary)
    if n <= 1 :     # 정렬할 리스트의 개수가 1개 이하면
        return ary
	
    pivot = ary[n // 2]      # 기준값을 중간값으로 지정
    leftAry, rightAry = [], []

    for num in ary :
        if num < pivot :
            leftAry.append(num)
        elif num > pivot :
            rightAry.append(num)

    return quickSort(leftAry) + [pivot] + quickSort(rightAry)

dataAry = [188, 150, 168,  162, 105, 120,  177,  50]

print('정렬 전 -->', dataAry)
dataAry = quickSort(dataAry)
print('정렬 후 -->', dataAry)

정렬 전 --> [188, 150, 168, 162, 105, 120, 177, 50]
정렬 후 --> [50, 105, 120, 150, 162, 168, 177, 188]

 

중복 값을 고려한 구현

• 위의 코드는 중복 값이 있으면 중복 값 하나만 남긴다.
  • 중복 값이 없거나 중복 값은 하나로 처리할 경우에 적합한 방법이다.
• 하지만, 중복 값까지 고려한다면 코드를 다음과 같이 약간 수정해야 한다.

 

구현

def quickSort(ary) :
    n = len(ary)
    if n <= 1 :		# 정렬할 리스트의 개수가 1개 이하면
        return ary

    pivot = ary[n // 2] 	# 기준값을 중간 값으로 지정
    leftAry, midAry, rightAry = [], [], []

    for num in ary :
        if num < pivot :
            leftAry.append(num)
        elif num > pivot :
            rightAry.append(num)
        else :
            midAry.append(num)

    return quickSort(leftAry) + midAry + quickSort(rightAry)

dataAry = [120, 120, 188, 150, 168, 50, 50, 162, 105, 120,  177,  50]

print('정렬 전 -->', dataAry)
dataAry = quickSort(dataAry)
print('정렬 후 -->', dataAry)

정렬 전 --> [120, 120, 188, 150, 168, 50, 50, 162, 105, 120, 177, 50]
정렬 후 --> [50, 50, 50, 105, 120, 120, 120, 150, 162, 168, 177, 188]

 

일반 구현

• 앞서 퀵 정렬을 위해 왼쪽 그룹과 오른쪽 그룹을 위한 별도의 배열을 사용했다.
• 이번에는 원래의 배열 하나로 퀵 정렬을 하는 방법을 알아보자.
• 처음에는 첫 번째를 start 로, 마지막을 end 로 둔 후, 재귀로 호출될 때마다 start(시작점)와 end(끝점)를 전달받으면서 진행된다.
  • 그러다가 start가 end보다 크거나 같으면 재귀를 종료한다.
    • 정렬할 데이터가 1개 이하라 더는 정렬할 데이터가 없어 재귀를 종료한다.

 

구현

def qSort(arr, start, end) :
    if end <= start :
        return

    low = start
    high = end

    pivot = arr[(low + high) // 2]      # 작은 값은 왼쪽, 큰 값은 오른쪽으로 분리한다.
    while low <= high :
        while arr[low] < pivot :
            low += 1
        while arr[high] > pivot :
            high -= 1
        if low <= high :
            arr[low], arr[high] = arr[high], arr[low]
            low, high = low + 1, high - 1

    mid = low

    qSort(arr, start, mid-1)
    qSort(arr, mid, end)

def quickSort(ary) :
    qSort(ary, 0, len(ary)-1)

dataAry = [188, 150, 168, 162, 105, 120, 177, 50]

print('정렬 전 -->', dataAry)
quickSort(dataAry)
print('정렬 후 -->', dataAry)

정렬 전 --> [188, 150, 168, 162, 105, 120, 177, 50]
정렬 후 --> [50, 105, 120, 150, 162, 168, 177, 188]

 

성능과 특이점

• 퀵 정렬도 가장 나쁜 경우에는 삽입 정렬, 선택 정렬과 마찬가지로 연산 수는 `O(n^{2})`이 되지만, 평균적으로 `O(nlogn)`의 연산 수를 갖는다.
  • 다른 정렬에 비해서 상당히 빠른 속도이며, 특히 정렬할 데이터 양이 많을수록 다른 정렬보다 매우 우수한 성능을 낸다.

 

정렬 알고리즘의 응용

① 1차원 배열의 중앙값 계산

평균값과 중앙값

• 평균값 : 전체 데이터 값을 합친 후 개수로 나누는 것
• 비정상적인 값의 영향을 배제하고 대푯값을 구하는 방법 중 하나가 중앙값이다.

 

중앙값 계산

• 중앙값은 데이터를 일렬로 정렬해서 나열한 후, 나열된 숫자의 가운데에 위치하는 값을 대푯값으로 하는 방법이다.
• 중앙값을 구하려면 우선 데이터를 오름차순 또는 내림차순으로 정렬해야 한다.
• 데이터의 개수가 짝수 개인 경우, 중앙값을 (개수/2) 또는 (개수/2 - 1) 어느 것을 해도 된다.

 

구현

• 선택 정렬(Selection Sort)을 이용하여 중앙값을 계산해본다.

def selectionSort(ary) :
    n = len(ary)
    for i in range(0, n-1) :
        minIdx = i
        for k in range(i+1, n) :
            if (ary[minIdx] > ary[k]) :
                minIdx = k
        tmp = ary[i]
        ary[i] = ary[minIdx]
        ary[minIdx] = tmp

    return ary

moneyAry = [7, 5, 11, 6, 9, 80000, 10, 6, 15, 12]

print('용돈 정렬 전 -->', moneyAry)
moneyAry = selectionSort(moneyAry)
print('용돈 정렬 후 -->', moneyAry)
print('용돈 중앙값 --> ', moneyAry[len(moneyAry)//2])

용돈 정렬 전 --> [7, 5, 11, 6, 9, 80000, 10, 6, 15, 12]
용돈 정렬 후 --> [5, 6, 6, 7, 9, 10, 11, 12, 15, 80000]
용돈 중앙값 -->  10

 

② 2차원 배열의 중앙값 계산

구현

• 선택 정렬(Selection Sort)을 이용하여 중앙값을 계산해본다.
• 2차원 배열을 1차원 배열로 만든 후, 정렬하는 방법을 사용한다.

def selectionSort(ary) :
    n = len(ary)
    for i in range(0, n-1) :
        minIdx = i
        for k in range(i+1, n) :
            if (ary[minIdx] > ary[k]) :
                minIdx = k
        tmp = ary[i]
        ary[i] = ary[minIdx]
        ary[minIdx] = tmp

    return ary

ary2 = [[55, 33, 250, 44],
         [88,  1,  67, 23],
         [199,222, 38, 47],
         [155,145, 20, 99]]
ary1 = []

for i in range(len(ary2)) :
    for k in range(len(ary2[i])) :
        ary1.append(ary2[i][k])

print('1차원 변경 후, 정렬 전 -->', ary1)
ary1 = selectionSort(ary1)
print('1차원 변경 후, 정렬 후 -->', ary1)
print('중앙값 --> ', ary1[len(ary1)//2])

1차원 변경 후, 정렬 전 --> [55, 33, 250, 44, 88, 1, 67, 23, 199, 222, 38, 47, 155, 145, 20, 99]
1차원 변경 후, 정렬 후 --> [1, 20, 23, 33, 38, 44, 47, 55, 67, 88, 99, 145, 155, 199, 222, 250]
중앙값 -->  67

 

③ 파일 이름의 정렬 출력

지정된 폴더에서 하위 폴더를 포함한 파일 목록 추출

• C:\Windows\System32 폴더의 파일을 배열에 저장하는 기능을 하는 코드이다.

import os

fnameAry = []
folderName = 'C:/Windows/System32'
for dirName, subDirList, fnames in os.walk(folderName) :
    for fname in fnames :
        fnameAry.append(fname)

print(len(fnameAry))

9593

 

 

파일 목록 정렬

• 파일은 '파일명.확장명'으로 구분되어 있다.
• 이것을 파일명 및 확장명으로 분리해서 정렬하는 방법을 사용하겠다.

 

구현

• 파일 목록 배열을 파일명으로 내림차순 정렬한 결과와 확장명으로 내림차순 정렬한 결과를 출력하는 코드는 다음과 같다.

import os

def makeFileList(folderName) :
    fnameAry = []
    for dirName, subDirList, fnames in os.walk(folderName):
        for fname in fnames:
            fnameAry.append(fname)
    return fnameAry

def insertionSort(ary) :
    n = len(ary)
    for end in range(1, n) :
        for cur in range(end, 0, -1) :
            if (ary[cur-1] < ary[cur]) :
                ary[cur-1], ary[cur] = ary[cur], ary[cur-1]
    return ary

fileAry = []

fileAry = makeFileList('C:/Program Files/Common Files')
fileAry = insertionSort(fileAry)
print('파일명 역순 정렬 -->', fileAry)

파일명 역순 정렬 --> ['zh-phonetic.xml', 'zh-dayi.xml', 'zh-changjei.xml', 'wab32res.dll.mui',
'vcruntime140.dll', 'vccorlib140.dll', 'ucrtbase.dll', 'tpcps.dll', 'tiptsf.dll', 'tipskins.dll'
'AppVClient.man', 'AppVCatalog.dll', 'ApiClient.dll', 'Alphabet.xml']

 

④ 컬러 이미지를 흑백 이미지로 만들기

• 다양한 색상 값이 있는 컬러 이미지를 종종 흑백 이미지로 변경하는 경우가 있다.
• 이때 컬러 색상을 흑백으로 변환할 때, 중앙값을 사용해야 정확한 결과가 표현되기도 한다.
• 중앙값을 계산하려면 우선 정렬을 해야하며, 대용량 크기의 이미지는 퀵 정렬 등 속도가 빠른 정렬을 사용해야 한다.

 

컬러와 흑백 색상 표현 이해하기

• 컬러 이미지를 흑백 이미지로 만들기 전에 이미지 색상의 표현법을 간단하게 이해하고 있어야 한다.
• 이미지 파일은 컬러, 그레이, 흑백 이미지로 나눌 수 있고, 256가지(0~255)의 Red, Green, Blue 색이 조합되어서 표현된다.
• 컬러 이미지를 그레이 이미지로 변환
  • Red, Green, Blue 세 값을 합하고 3으로 나눈 후 Red, Green, Blue 값으로 모두 사용한다.
• 그레이 이미지를 흑백 이미지로 변환
  • 0~255 중간 값인 127을 기준으로 127보다 작으면 0으로, 127보다 크면 255로 처리한다.

컬러 이미지
Red		Green		Blue
10	250	55	100	190	240
77	179	188	3	220	33
그레이 이미지
Red		Green		Blue
85	197	85	197	85	197
162	72	182	72	162	72
흑백 이미지
Red		Green		Blue
0	255	0	255	0	255
255	0	255	0	255	0

 

파이썬으로 이미지 출력하기

• 이미지를 화면에 출력할 때 파이썬에서는 tkinter 를 사용할 수 있다.
• 컬러 이미지가 흑백으로 변환된 결과를 확인하는 데 이미지의 화면 출력이 필요하다.
• 우선 이미지를 표현하고자 PhotoImage() 함수를 사용하고, 레이블에 출력하는 방식을 쓴다.
• 파이썬은 기본적으로 GIF 그림 파일만 지원하고, JPG, PNG 등 그림 파일을 보려면 외부 라이브러리를 사용해야 한다.

from tkinter import *

window = Tk()
window.geometry("600x600")

photo = PhotoImage(file = 'pet01.gif')

paper = Label(window, image=photo)
paper.pack(expand=1, anchor=CENTER)
window.mainloop()

 

컬러 이미지를 1차원 배열로 만들기

• 컬러 이미지의 각 점에는 Red, Green, Blue 값이 3개 있으므로 1차원 배열 하나에 저장할 때는 세 점을 합한 평균으로 저장한다.

r, g, b = photo.get(i, k)
value = (r + g + b) // 3
photoAry.append(value)

 

구현

from tkinter import *

window = Tk()
window.geometry("600x600")
photo = PhotoImage(file = 'pet01.gif')

photoAry=[]
h = photo.height()
w = photo.width()
for i in range(h) :
    for k in range(w) :
        r, g, b = photo.get(i,k)
        value = (r + g + b) // 3
        photoAry.append(value)

# 이 부분에 필요한 내용을 추가

paper = Label(window, image=photo)
paper.pack(expand=1, anchor = CENTER)
window.mainloop()

 

흑백 이미지로 만들기

• 흑백 이미지는 검은색(0)과 흰색(255)으로만 표현되는데, 현재 1차원 배열인 photoAry 는 그레이 이미지 정보인 0~255의 값을 가지고 있다.
• 따라서 다음과 같이 중간 값인 127을 기준으로 0부터 127까지는 0으로 변환하고, 128부터 255까지는 255로 변환해야 한다.

if photoAry[i] <= 127 :
    photoAry[i] = 0
else :
    photoAry[i] = 255

 

구현

from tkinter import *

window = Tk()
window.geometry("600x600")
photo = PhotoImage(file = 'pet01.gif')

photoAry=[]
h = photo.height()
w = photo.width()
for i in range(h) :
    for k in range(w) :
        r, g, b = photo.get(i,k)
        value = (r + g + b) // 3
        photoAry.append(value)

for i in range(len(photoAry)) :
    if photoAry[i] <= 127 :
        photoAry[i] = 0
    else :
        photoAry[i] = 255

pos = 0
for i in range(h) :
    for k in range(w) :
        r = g = b = photoAry[pos]
        pos += 1
        photo.put("#%02x%02x%02x" % (r, g, b), (i, k))

paper = Label(window, image=photo)
paper.pack(expand=1, anchor = CENTER)
window.mainloop()

 

퀵 정렬로 중앙값 계산하기

• 위의 코드를 이용하여 지나치게 어두운 이미지를 127 기준으로 변환하면 이미지가 지나치게 부자연스럽게 표현된다.
  • 어두운 이미지는 대부분 127 미만의 어두운 색상값을 가지기 때문이다.

지나치게 어두운 이미지를 변환한 결과

 

• 이때는 해당 이미지의 중앙값을 계산해서 기준 값으로 사용하는 것이 좋다.

 

구현

from tkinter import *

def qSort(arr, start, end) :
    if end <= start :
        return

    low = start
    high = end

    pivot = arr[(low + high) // 2]     # 작은 값은 왼쪽, 큰 값은 오른쪽으로 분리한다.
    while low <= high :
        while arr[low] < pivot :
            low += 1
        while arr[high] > pivot :
            high -= 1
        if low <= high :
            arr[low], arr[high] = arr[high], arr[low]
            low, high = low + 1, high - 1

    mid = low

    qSort(arr, start, mid-1)
    qSort(arr, mid, end)

def quickSort(ary) :
    qSort(ary, 0, len(ary)-1)

window = Tk()
window.geometry("600x600")
photo = PhotoImage(file = 'pet02.gif')

photoAry=[]
h = photo.height()
w = photo.width()
for i in range(h) :
    for k in range(w) :
        r, g, b = photo.get(i,k)
        value = (r + g + b) // 3
        photoAry.append(value)

dataAry = photoAry[:]
quickSort(dataAry)
midValue = dataAry[h*w // 2]

for i in range(len(photoAry)) :
    if photoAry[i] <= midValue :
        photoAry[i] = 0
    else :
        photoAry[i] = 255

pos = 0
for i in range(h) :
    for k in range(w) :
        r = g = b = photoAry[pos]
        pos += 1
        photo.put("#%02x%02x%02x" % (r, g, b), (i, k))

paper = Label(window, image=photo)
paper.pack(expand=1, anchor = CENTER)
window.mainloop()