정렬

정렬(Sorting)이란 데이터를 특정한 기준에 따라서 순서대로 나열하는 것

정렬 알고리즘은 이진 탐색의 전처리 과정

 

선택 정렬, 삽입 정렬, 퀵 정렬, 계수 정렬, 파이썬에서 제공하는 기본 정렬 라이브러리

(reverse 함수는 O(N)의 복잡도로 수행할 수 있으므로 내림차순 정렬은 오름차순 정렬을 수행한 뒤에 뒤집으면 된다.)

 

파이썬의 정렬 라이브러리

파이썬은 기본 정렬 라이브러리인 sorted() 함수를 제공한다. (딕셔너리 자료형 등을 입력받고 반환되는 결과는 리스트이다.)

 

병합 정렬을 기반으로 만들어졌고 시간 복잡도는 O(NlogN)

리스트 객체의 내장 함수인 sort() - 리스트가 반환되지 않고 내부 원소가 바로 정렬된다

 

array = [('banana', 2), ('apple', 5), ('carrot', 3)]

def setting(data):
	return data[1], data[0]
    
result = sorted(array, key=setting)
print(result)

                    

선택 정렬, '가장 작은 것을 선택'

- 가장 작은 것을 선택해서 앞으로 보내는 과정을 반복해서 수행하여 데이터 정렬

# 최소값 위치 찾는 코드
def findMinIdx(ary) :
    minIdx = 0
    for i in range(1, len(ary)):
        if(ary[minIdx]>ary[i]):
            minIdx = i
    return minIdx

testAry = [55, 8, 33, 77]
minPos = findMinIdx(testAry)
print(testAry[minPos])
print(minPos)

# 선택 정렬, 배열 두개 사용
before = [1,0,5,2,8]
after = []

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

# 선택 정렬, 배열 한개 사용(원래 하던거)
before = [1,0,5,2,8]

def selectionSort(ary):
    n = len(ary)
    for i in range(0, n-1):
        minIdx = i # minIdx를 변수로 설정하여 코드를 재사용하기 쉬움
        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

before = selectionSort(before)
print(before)

# 중앙값 구하는 코드
print(before[len(before)//2])

 

- 시간 복잡도 : O(N^2)

 

삽입 정렬, '데이터를 하나씩 확인하며, 각 데이터를 적절한 위치에 삽입'

- 삽입하기 전에 그 앞까지 데이터는 '이미 정렬되어 있다고 가정'한다. 정렬되어 있는 데이터 리스트에서 적절한 위치를 찾은 뒤에, 그 위치에 삽입.

첫 번째 데이터는 그 자체로 정렬되어 있다고 판단한다.

# 배열(빈 배열 or after 배열 or 정렬 중인 배열)에서 자신이 삽입될 위치를 찾는 함수
def findInsertIdx(ary, data) :
    findIdx = -1
    for i in range(0, len(ary)) :
        if (ary[i] > data) :
            findIdx = i # 자신보다 큰 데이터 자리 가져옴
            break
    if findIdx == -1 : # 자신보다 큰 값을 못 찾음 제일 마지막 위치 return
        return len(ary)
    else :
        return findIdx

# 위 함수를 이용한 삽입 정렬
before = [1,0,5,2,8]
after = []

print('정렬 전 -->', before)
for i in range(len(before)) : # 첫 번째 배열부터 after 배열에 삽입할 위치 찾기
	data = before[i]
    insPos = findInsertIdx(after, data) # 삽입 할 인덱스 위치
    after.insert(insPos, data) # 첫 번째는 맨 앞, 두 번째는 맨 앞과 비교, 세 번째 앞에 들어간 거랑 다 비교 ...
print('정렬 후 -->', after)

# 삽입 정렬2
def insertionSort(ary):
    n = len(ary)
    for end in range(1, n): # 처음에는 앞 두개, 다음은 3개, 다음은 4개 ... 처리
        for cur in range(end, 0, -1): # 사이클 i의 마지막을 현재를 두고 앞과 비교
            if(ary[cur-1]>ary[cur]):
                ary[cur-1], ary[cur] = ary[cur], ary[cur-1]
    return ary

dataAry = [18, 16, 12, 5, 10]

print(dataAry)
dataAry = insertionSort(dataAry)
print(dataAry)

    for i in range(1, n): # 처음에는 앞 두개, 다음은 3개, 다음은 4개 ... 처리
        for cur in range(end, 0, -1): # 사이클 i의 마지막을 현재를 두고 앞과 비교
            if ary[cur-1] > ary[cur]:
                ary[cur-1], ary[cur] = ary[cur], ary[cur-1]
    return ary

 

- 시간 복잡도 : O(N^2)

최선의 경우 O(N)의 시간 복잡도를 가진다.

삽입 정렬에서는 특정한 데이터가 삽입될 위치를 선정할 때, 삽입될 데이터보다 작은 데이터를 만나면 그 위치에서 멈추면 된다. 따라서 삽입 정렬은 현재 리스트의 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작하므로 다른 정렬 알고리즘을 이용하는 것보다 삽입 정렬을 이용하는 것이 정답 확률을 높일 수 있다.

 

퀵 정렬

기준 데이터(pivot)를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꿈 -> 리스트 분할,을 반복

## 호어 분할 방식
def quick(start, end, array):
	if start >= end:
    	return
    pivot = start # 리스트의 첫 번째 데이터를 피벗으로 설정
    left = start + 1
    right = end
# 왼쪽에서부터 피벗보다 큰 데이터를 찾고, 오른쪽에서부터 피벗보다 작은 데이터를 찾고 서로 교환
    while left <= right:
    	# 왼쪽에서부터
        while left <= end and array[left] <= array[pivot]:
        	left += 1
        # 오른쪽에서부터
        while right > start and array[right] >= array[pivot]:
        	right -= 1
        if left > right:
        	array[right], array[pivot] = array[pivot], array[right]
        else: 데이터를 서로 교환
        	array[left], array[right] = array[right], array[left]
    # 위 과정을 반복하며 피벗에 대하여 정렬
    quick(start, right-1, array)
    quick(right+1, end, array)

 

계수 정렬

'데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때'만 사용할 수 있다. 일반적으로 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000을 넘지 않을 때 효과적으로 사용할 수 있다. 모든 범위를 담을 수 있는 크기의 리스트를 선언해야 하기 때문이다.

 

참고 문법

#배열 구현법 1
ary = [None for_in range(3)]
ary[0]=100, ary[1]=100, ary[2]=200

#배열 구현법 2
ary = []
ary.append(100), ary.append(100), ary.append(200)

#두 변수 값의 교환1
tmp = A
A = B
B = temp

#두 변수 값의 교환2 - 파이썬 스와프(Swap)
#스와프란? 특정한 리스트가 주어졌을 때 두 변수의 위치를 변경하는 작업
A, B = B, A

#배열에 데이터 삽입, insert(삽입할 위치, 값)
testAry = []
testAry.insert(0, 55)
testAry

 

출처 : 이것이 ~ 코딩 테스트다 with 파이썬(p156) 등