[Python] 정렬 알고리즘 - 선택, 삽입, 퀵, 계수

---

💡 선택 정렬 (Selection Sort)

• 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 데이터와 바꾼다.

1. 처리되지 않은 데이터 중 가장 작은 데이터를 맨 앞 데이터와 바꿈
2. 이러한 과정 반복 (마지막 경우에는 처리하지 않아도 된다)

• 탐색 범위는 점점 줄어든다.
• 매번 선형 탐색한다.
• 복잡도 O(N^2) : n번 만큼 가장 작은 수를 찾아서 맨 앞으로 보낸다.
• n + (n-1) + (n-2) = (n^2 +n - 2) / 2

🧷 구현 과정

array = [리스트]

for : 리스트 길이만큼

    for : i부터 0까지 1씩 줄면서

    if : 현재 원소가 앞의 원소보다 작다면 : 서로 바꿈

    else : break

print(리스트)

🧷 파이썬 코드

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

for i in range(1, len(array)):
    for j in range(i, 0, -1):
        if array[j] < array[j-1]:
            array[j], array[j-1] = array[j-1], array[j]
        else:
            break

print(array)

 

💡 삽입 정렬

• 처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입한다.
• 선택 정렬에 비해 난이도 조금 높지만 빠르다.

7

5

9

0

3

1

6

2

4

8

1. 앞의 원소가 정렬되어 있다고 가정
2. 7은 그자체로 정렬, 5가 어떤 위치로 들어갈지 왼쪽이거나 오른쪽으로 들어가거나 작으면 왼쪽으로 (오름차순으로 가정)
3. 9가 3곳(5앞, 5와 7사이, 7뒤) 중 어디에 들어갈 지, 7보다 크기 때문에 그대로
4. 0이 어디로 들어갈지, 5의 왼쪽까지 하나씩 이동, 매번 왼쪽에 있는 데이터와 위치를 바꾸면서
5. 이 과정 반복

• 복잡도 O(N^2) : 반복문 중첩 -> 비교, 스와핑
• 현재 리스트가 정렬되어 있는 상태면 매우 빠름 - 다 정렬되면 O(N)

🧷 구현 과정

array = 리스트

    for 리스트 길이만큼 : 가장 작은 값

    for i, 0, -1 : 1씩 감소하면서 

        if min_index의 값보다 인덱스 j의 값이 작다면 : min_index를 j로 업데이트

    i와 가장 작은 인덱스 스와프

🧷 파이썬 코드

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

for i in range(len(array)):
	min_index = i

	for j in range(i + 1, len(array)):
		if array[min_index] > array[j]:
			min_index = j
	array[i], array[min_index] = array[min_index], array[i]

print(array)

 

💡 퀵 정렬

• 기준 데이터를 설정, 그 기준보다 큰 데이터와 작은 데이터 위치를 바꿈
• 일반적으로 가장 많이 사용
• 병합과 더울어 표준 정렬 라이브러리의 근간
• 가장 기본적 퀵 정렬은 첫번째 데이터를 기준 데이터(pivot)으로 설정

🧷 구현 과정

1. 현재 피벗의 값은 5, 왼쪽에서부터 큰값, 오른쪽에서 부터 작은값 4와 7의 위치 바꿈
2. 위치가 엇갈린경우 작은 데이터와 피벗값의 위치를 바꿔줌
3. 피벗이 중간으로 들어가게된다.-> 왼쪽의 데이터는 피벗보다 작고, 오른쪽은 큰 데이터
4. 왼쪽 오른쪽을 각 각의 배열로 취급하여 각각 퀵 정렬 수행 -> 재귀적으로, 범위 점점 작아짐

• 데이터가 절반에 가깝게 분할된다면 O(nlogn) : 너비 x 높이
• 평균의 경우 O(NlogN)
• 최악(N^2)
• 이미 정렬된 배열인 경우 : 분할이 이루어졌을 때 분할이 이루어지지 않는다. 분할을 위해 매번 선형 탐색을 하기 때문이다.

🧷 구현 과정

array = 리스트

def 퀵 (array, start, end) # 리스트, 첫

    if (start >= end) 원소 한개일때 종료 : return

    pivot =   첫 번째 원소

    left = 첫번째 + 1 (가장 왼쪽)

    right = end (가장 오른쪽)

while left <= right

    while 왼쪽에서 부터 피벗보다 큰 데이터 찾을 때까지: left 1씩 증가

    while 피벗보다 작은 데이터 찾을 때까지 : right 1씩 감소

    if (left > right) 엇갈렸다면, 작은 데이터 <-> 피벗 --- 분할

    else 엇갈리지 않았다면, 작은 데이터 <-> 큰 데이터 

quick_sort(리스트, 시작, 오른쪽-1)

quick_sort(리스트, 오른쪽+1, 끝)

 

퀵 (array, 0, 리스트길이-1)

🧷 파이썬 코드

array = [5,7,9,0,3,1,6,2,4,8]

def quick_sort(array, start, end):
    if start >= end:
        return
    pivot = start
    left = start + 1
    right = end

    while (left <= right):
        while (left <= end) and (array[left] <= array[pivot]): # array[left]<=array[pivot]
            left += 1
        while (right > start) and (array[right] >= array[pivot]):
            right -= 1
        if left > right : 
            array[pivot], array[right] = array[right], array[pivot] #right : 작은 데이터
        else:
            array[left], array[right] = array[right], array[left]
    quick_sort(array, start, right - 1)
    quick_sort(array, right + 1, end)

quick_sort(array, 0, len(array) - 1)
print("quick_sort :", array)

 

🧷 파이썬 성질 이용한 코드

def 퀵(리스트):

    if 길이 <= 1: return

    pivot = 인덱스 0

    tail = [1:] 피벗 제외 리스트

    왼쪽리스트 = tail 돌면서 pivot보다 작은 거

    오른쪽리스트 = tail 돌면서 pivot보다 큰 거

    return 왼쪽리스트+피벗+오른쪽리스트

def quick_sort2(array):
    if len(array) <= 1:
        return array
    pivot = array[0]
    tail = array[1:]

    left_array = [x for x in tail if x <= pivot]
    right_array = [x for x in tail if x > pivot]

    return quick_sort2(left_array) + [pivot] + quick_sort2(right_array)
    
    print("quick_sort2 :", quick_sort2(array))

💡계수 정렬

• 특정 조건이 부합할 때만
• 데이터의 크기 제한, 정수 형태로 표현할 수 있을 때
• O(N+K)

1. 가장 작은 데이터부터 큰 데이터가 모두 담기도록 리스트 생성, 해당 데이터가 몇 번 등장하는지
2. 데이터를 하나씩 확인하며 데이터의 값과 동일한 인덱스의 데이터를 1씩 증가
3. 각 데이터가 몇 번 등장했는 지 그 횟수 기록

• 결과 확인 할 때, 개수만큼 인덱스를 출력
• 상대적으로 공간 복잡도가 높지만 조건에 맞는다면 빠르다

🧷 구현 과정

array = 리스트

count리스트 = [0] * (최댓값+1)

for 리스트 길이 만큼 : count의 해당 인덱스에 1 증가

for count길이 만큼

    for count 리스트 인덱스를 돌면서 : 그 안에 들어있는 값만큼 프린트

🧷 파이썬 코드

array = [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2]

count = [0] * (max(array)+1)

for i in array:
    count[i] += 1

for i in range(len(count)):
    for j in range(count[i]):
        print(i, end=" ")

 

• 시간 복잡도와 공간 복잡도 모두 N(O+K)
  데이터가 0과 999999라면 비효율적
• 동일한 데이터 값이 여러개 등장할 때 (성적의 경우 100점이 여러명)