1. 정렬
정렬(Sorting)은 데이터를 사용자가 설정한 기준에 따라서 순서대로 나열하는 것을 말한다. 보통은 문제의 조건에 따라서 오름차순이나 내림차순으로 정렬을 한다. 정렬되는 데이터는 꼭 하나의 '수' 혹은 '문자' 뿐만 아니라, 데이터 값이 2개가 입력된 튜플 자료형이 하나의 값으로써 사용자의 설정에 따라서 정렬되기도 한다. 단순히 정렬을 해야 하는 경우라면 내장 함수 sort, sorted를 사용하는데, 문제의 조건에 따라서 직접 정렬을 시켜야 하는 경우도 있기에 여러가지 방법으로 데이터를 정렬하는 법을 살펴보자.
특히 선택, 삽입, 버블, 계수정렬은 for 반복문을 통해 정렬을 시키는데 반해, 병합정렬과 퀵정렬은 재귀함수를 통한 반복문을 실행시키기에 앞의 4가지 방법보다 연산이 빠르다는 장점이 있지만 재귀함수의 이해가 선행되지 않으면 이해하기 조금 어렵다는 단점이 있다. 먼저 앞선 4가지를 살펴보고 그 다음 병합과 퀵정렬을 살펴보겠다.
2. 선택정렬
데이터가 순서 없이 나열되어 있을 때, 그 데이터들 중 가장 작은 데이터를 찾아 제일 앞에 두고, 그 다음 작은 데이터를 찾아서 가장 작은 데이터 다음에 두는 식의 과정을 반복한다. 그래서 매번 가장 작은 수를 선택하여 정렬한다고 해서 선택정렬이라고 한다. 
위 그림과 같이 먼저 제일 작은 수 1을 찾아 제일 앞의 수와 교체를 한다. 그 다음 2는 두번째에 재자리를 차지하고 있기에 그 다음 작은 수 3을 찾아 앞의 작은수 2 다음 자리의 수와 교체를 하는 식이다.
import random
def Ssort(nums):
for i in range(len(nums) - 1): # i는 가장 작은 수가 교체될 인덱스 번호.
minN = i # 일단 i 를 가장 작은 값으로 초기화하여 다음 반복문을 통해서 nums[i]보다 작은 수를 찾아간다.
for j in range(i + 1, len(nums)): # i의 다음 인덱스부터 끝까지 탐색한다.
if nums[minN] > nums[j]: # 현재 nums[i]보다 nums[j]가 더 작다면, 이제는 인덱스 j 값을 가장 작은 값으로 업데이트한다.
minN = j
nums[minN], nums[i] = nums[i], nums[minN] # 첫번째 안쪽 반복문이 끝이나면 가장 작은 수를 찾았을 것이다.
return nums # 가장 작은 수와 가장 작은 수가 들어갈 인덱스 i의 데이터를 교체한다.
if __name__ == '__main__':
nums = random.sample(range(0, 10), 10)
print('Before:', nums)
print('After:', Ssort(nums))
출력:
Before: [8, 5, 1, 2, 3, 6, 7, 0, 4, 9]
After: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
# 추가:
# 아래는 버블정렬의 개념이다.
# 하지만 연산 횟수를 보았을 때에는 선택정렬과 버블정렬의 연산 횟수가 같다.
# 작은 수를 계속 업데이트 한 후 숫자를 교체하는 것(선택정렬)과, i번째 보다 작은 수를 찾을 때마다 업데이트하는 것(버블정렬)은 같은 교체의 연산 횟수가 일어난다.
# 다시 말해 가장 작은 수를 찾은 후 바꿀 것인지(선택정렬), 작은 수가(가장 작든 아니든, 현재보다 작다면) 나타날 때마다 바꿀 것인지(버블정렬)
import random
def Bsort(nums):
for i in range(len(nums) - 1):
for j in range(i + 1, len(nums)):
if nums[i] > nums[j]:
nums[i], nums[j] = nums[j], nums[i] # 가장 작은 수를 찾았을 때마다 업데이트(가장 작은 수 j를 minN으로 업데이트와 연산 횟수가 같다)
return nums
if __name__ == '__main__':
nums = random.sample(range(0, 10), 10)
print('Before:', nums)
print('After:', Bsort(nums))3. 삽입정렬
데이터가 순서 없이 나열되어 있을 때, 두 번째 숫자부터 시작하여 앞자리 숫자와 비교하여 앞자리보다 현재의 수가 더 작다면 교체하는 식으로, 제일 앞자리인 인덱스 0번까지 진행한다. 2번째 수가 끝나면 다시 3번째 인덱스 부터 앞의 과정을 반복해서 범위를 점차 넓혀가며 정렬을 한다. 삽입하려는 숫자의 앞은 항상 정렬이 된 상태이기 때문에, 현재 삽입하려는 숫자가 작을 때까지 그리고 제일 앞자리까지 교체하며 진행되고 현재의 수보다 작은 수가 나타나면 정지하여 자신의 자리를 찾는 것이다. 
그림과 같이, 먼저 앞의 인덱스 1부터 시작하여 10이 선택되고 숫자 10 앞을 보았을 때 자신보다 작기에 정렬은 변하지 않는다. 그 다음 범위를 한 칸 넓혀 인덱스 2부터 시작하여 앞과 비교하면서 인덱스 0번의 숫자까지 확인하면서 앞으로 삽입되는 식으로 숫자 교체가 일어난다. 다음 숫자인 1이 선택이 되고 다시 인덱스 0을 향해서 움직이며 앞의 숫자와 비교하여 1이 작기에 교체되는 식으로 진행되며 자신보다 작은 수가 나타나면 멈춘다.
import random
def Isort(nums):
for i in range(len(nums)-1): # 다음 반복문의 j가 i보다 인덱스 보다 1 큰 곳에서 역으로 진행하기에 전체 길이에서 1을 빼준다.(앞과 비교를 하며 인덱스 번호 1까지만 내려가서 인덱스 0과 비교하기에 전체 길이에서 -1을 해도 무방하다.
for j in range(i+1, 0, -1): # i보다 인덱스 번호 1만큼 더 큰 곳에서 역으로 찾아가도록(앞의 수와 비교하면서 진행하기에 인덱스 1까지만 내려가도록)
if nums[j] < nums[j-1]: # 현재의 수보다 앞의 수가 더 크다면 교체.
nums[j], nums[j-1] = nums[j-1], nums[j] # 파이썬이 사용하기 쉽다는 것은 이런 임시 변수 생성없이 바로 교체가 가능하다는 점들이다.
return nums
if __name__ == '__main__':
nums = random.sample(range(0, 10), 10)
print('Before:', nums)
print('After:', Isort(nums))
출력:
Before: [3, 9, 7, 0, 5, 2, 6, 1, 4, 8]
After: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]