Sorting 정렬

정렬이란 " 데이터를 특정한 기준에 따라서 순서대로 나열 "

 

정렬 알고리즘으로 데이터를 정렬하면 => 이진 탐색(Binary Search)이 가능해짐 ???

- 정렬 알고리즘은 이진 탐색의 전처리 과정이기도 하다

<Binary Search>

https://cord-ai.tistory.com/161

 

정렬 알고리즘

- 선택 정렬, 삽입 정렬, 퀵 정렬, 계수 정렬

- Python에서 제공하는 기본 정렬 라이브러리 적용 가능(= 더 효율적인 정렬 수행 방법)

- 면접에서도 단골 문제로 출제

# 단순 정렬해야하는 상황에서는 기본 정렬 라이브러리(sort, sorted) 사용
# 데이터의 범위가 한정되어 있으며 더 빠르게 동작해야할 경우 계수 정렬 사용
<코딩 테스트에서 정렬 알고리즘이 사용되는 경우>
1. 정렬 라이브러리로 풀 수 있는 문제 : 단순히 정렬 기법을 알고 있는지 물어보는 문제 
2. 정렬 알고리즘의 원리에 대해서 물어보는 문제 : 선택, 삽입, 퀵 정렬 등의 원리를 알고 있어야 풀 수 있음
3. 더 빠른 정렬이 필요한 문제 : 퀵 정렬 기반의 정렬 기법으로는 풀 수 없으며 계수 정렬 등의 다른 정렬 알고리즘을 이용해야한다. or 기존에 알려진 알고리즘의 구조적인 개선을 거쳐야 풀 수 있음

## 퀵 정렬로 풀 수 없는 것???
- 이미 데이터가 정렬되어 있는 경우

<비교 기반 정렬 알고리즘>

- 직접 데이터의 값을 비교한 뒤에 위치를 변경하는 알고리즘

(선택 정렬, 삽입 정렬, 퀵 정렬 / Not 계수 정렬)

상황에 적절하지 못한 정렬 알고리즘을 이용하면 프로그램은 비효율적으로 동작하며 필요 이상으로 시간을 많이 소요한다. 따라서 정렬 알고리즘을 공부하다보면 자연스럽게 알고리즘 효율의 중요성을 깨닫는다

# 리스트 뒤집기 = reverse()
- O(N)의 복잡도를 가짐

 

선택 정렬 Selection Sort

" 데이터가 무작위로 여러 개 있을 때, 이 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 반복하면 어떨까??? "

- "가장 작은 것을 선택"한다는 의미에서 선택 정렬 알고리즘이라고 한다.

# 선택 정렬(selection Sort)
array = []

for _ in range(1000):
    array.append(randint(1, 100))

# 인덱스 접근
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)

'''
randint는 a가 최소, b가 최대의 범위

randrange는 a가 최소, b-1이 최소
'''

선택 정렬의 시간 복잡도

- 선택 정렬은 N-1번 만큼 가장 작은 수를 찾아서 맨 앞으로 보내야 한다.

- 또한 매번 가장 작은 수를 찾기 위해서 비교 연산이 필요하다.

- 2중 반복문(= for 문)으로 시간 복잡도 == O(N²)

=> 정렬해야 할 데이터의 개수가 100배 늘어나면, 이론적으로 수행 시간은 10,000배로 늘어난다

선택 정렬은 다른 정렬 알고리즘에 비해 매우 비효율적 = 알고리즘 문제 풀이에 사용하기에 느린 편
=> 현재 데이터의 상태와 상관없이 무조건 모든 원소를 비교하고 위치를 바꾼다.
But, 특정한 리스트에서 가장 작은 데이터를 찾는 일이 코딩 테스트에서 잦으므로 해당 소스 코드에 익숙해질 필요가 있다.

 

삽입 정렬 Insertion Sort

" 데이터를 하나씩 확인하며, 각 데이터를 적절한 위치에 삽입하면 어떨까??? "

- 선택 정렬에 비해 실행 시간 측면에서 더 효율적

- 필요할 때만 위치를 바꾸므로 '데이터가 거의 정렬 되어 있을 때' 훨씬 효율적

- 삽입 정렬은 두 번째 데이터부터 시작한다
=> 첫 번째 데이터는 그 자체로 정렬되어 있다고 판단하기 때문

* 삽입 정렬은 
정렬이 이루어진 원소는 항상 오름차순을 유지하고 있다.
 이러한 특징 때문에 삽입 정렬에서는 특정한 데이터가 삽입될 위치를 선정할 때(= 삽입될 위치를 찾기 위해서 왼쪽으로 한 칸씩 이동할 때), 
삽입될 데이터보다 작은 데이터를 만나면 그 위치에서 멈추면 된다.

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): # i 부터 1까지 감소하며 반복
        if array[j] < array[j -1]: # 왼쪽으로 이동
            array[j], array[j-1] = array[j-1], array[j]

        else: # 자기보다 작은 데이터를 만나면 그 위치에서 멈춤
            break

print(array)

'''
range(start, end, step)
step == -1이면, start 인덱스부터 시작해서 end + 1 인덱스 까지 1씩 감소한다.
'''

삽입 정렬의 시간 복잡도

- 2중 반복문으로 시간 복잡도 == O(N²)

- 최선의 경우 == O(N)

<선택 정렬 특징>

- 삽입 정렬은 현재 리스트의 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작

- 거의 정렬되어 있는 상태라면 퀵 정렬 알고리즘보다 더 강력함

 

퀵 정렬 Quick Sort

" 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸면 어떨까??? "

- 기준을 설정한 다음 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 방식

- 가장 많이 사용되는 알고리즘

- 퀵 정렬과 비교할 만큼 빠른 알고리즘으로 "병렬 정렬" 알고리즘이 있다.

- 퀵, 병렬 정렬 알고리즘은 프로그래밍 언어에서 정렬 라이브러리의 근간이 되는 알고리즘이다.

퀵 정렬은 피벗 Pivot이 사용된다.
큰 숫자와 작은 숫자를 교환할 때, 교환하기 위한 " 기준 " 을 바로 피벗이라고 한다.
퀵 정렬을 수행하기 전에는 피벗을 어떻게 설정할 것인지 미리 명시해야한다.

<직관적인 이해>
- 피벗값의 위치가 변경되어 분할이 일어날 때마다 정확히 왼쪽, 오른쪽 리스트를 절반씩 분할한다면???
- 데이터 개수가 8개라고 가정
- 4, 4 분할
- 2, 2, 2, 2 분할
- 1, 1, 1, 1, 1, 1, 1, 1 분할
== 높이를 확인해보면 N개일 때 높이는 약 logN이라고 판단할 수 있다.

 

<피벗을 설정하고 리스트를 분할하는 방법에 따라서 여러 가지 방식으로 퀵 정렬을 구분>

- 가장 대표적인 분할 방식 = " 호어 분할 Hoare Partition "

# 리스트에서 첫 번째 데이터를 피벗으로 정한다.

1. 피벗 설정 후 피벗보다 큰 데이터를 왼쪽에서부터 찾고, 오른쪽에서부터 작은 데이터를 찾는다.

2. 큰 데이터와 작은 데이터의 위치를 교환한다.

3. 큰 데이터와 작은 데이터의 위치가 엇갈리면 ( 교환할 필요 없이 작은 데이터가 왼쪽에 큰 데이터가 오른쪽에 위치하면) 작은 데이터와 피벗의 위치를 교환한다.

4. 처음 설정한 피벗을 기준으로 좌측은 작은 데이터, 우측은 큰 데이터가 위치하게 된다 = Divide or Partition이라고 한다.

5. 이후 왼쪽 리스트와 오른쪽 리스트를 개별적으로 정렬(= 재귀 함수)

6. 리스트의 원소가 1이라면 더 이상 분할이 불가능하므로 퀵 정렬이 종료된다.

<python의 장점을 살린 퀵 정렬>

- 시간 면에서는 조금 비효율적임

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


# 왼쪽에서부터 작은 숫자, 오른쪽에서부터 큰 숫자 찾음
left_list = []
right_list = []

left_list = [array[i] for i in range(1, len(array)) if array[i] <= p]
right_list = [array[i] for i in range(1, len(array)) if array[i] > p]

# left_list, right_list 반복 = 재귀 함수 사용


# python의 장점을 살린 퀵 정렬
def quick_sort(array):
    # 리스트가 하나 이하의 원소만을 담고 있다면
    if len(array) <= 1:
        return array
    
    # 피벗 설정
    pivot = array[0]

    # 피벗을 제외한 array
    tail = array[1:]

    left_list = [i for i in tail if i <= pivot]
    right_list = [i for i in tail if i > pivot]   

    return quick_sort(left_list) + [pivot] + quick_sort(right_list)

print(left_list +  [p] + right_list)
print(quick_sort(array))

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

<가장 직관적인 형태의 퀵 정렬>

def quick_sort1(array, start, end):
    # 원소가 하나인 경우 종료
    if start >= end:
        return # None
    
    # 인덱스
    pivot = start # 피벗
    left = start + 1 # 피벗을 제외
    right = end # array 끝 인덱스 

    # 마지막 인덱스 값 까지 확인
    # left = 큰 데이터, right = 작은 데이터
    while left <= right:

        # 왼쪽, 오른쪽 동시에 확인
        # 왼쪽에서부터 피벗보다 큰 데이터를 찾을 때까지 반복
        while left <= end and array[left] <= array[pivot]:
            left += 1 # 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]

    # left가 더 크면 while 종료
    # 분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬 수행
    quick_sort1(array, start, right-1) # right - 1 ==> 피벗 제외
    quick_sort1(array, right + 1, end) # right + 1 ==> 피벗 제외

# len(array1) - 1 => 인덱스 접근을 위함
quick_sort1(array1, 0, len(array1) - 1)
print(array1)

퀵 정렬의 시간 복잡도

- 선택 정렬과 삽입 정렬은 최악의 경우에도 항상 시간 복잡도 O(N²)을 보장한다.

- 퀵 정렬 시간 복잡도 == O(NlogN)

- 최악의 경우 시간 복잡도 ==  O(N²)
=> 리스트의 가장 왼쪽 데이터를 피벗으로 삼을 때"이미 데이터가 정렬되어 있는 경우"

"이미 데이터가 정렬되어 있는 경우" 에는 삽입 정렬 사용

 

<기본 정렬 라이브러리 이용시 O(NlogN) 보장> 

- Python의 정렬 라이브러리 참조(맨 밑)

Count Sort

" 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠른 정렬 알고리즘 "

- 데이터 개수가 N, 데이터 중 최댓값이 K일 때, 계수 정렬은 최악의 경우에도 수행 시간 O(N+K)

- 매우 빠르고 간단

- 단, "데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때" 만 사용 가능

=> 데이터의 값이 무한한 범위를 가질 수 있는 실수형 데이터가 주어지는 경우 계수 정렬은 사용하기 어렵다.

=> 가장 큰 데이터와 가장 작은 데이터의 차가 1,000,000을 넘지 않을 때 효과적

why???

- 모든 범위를 담을 수 있는 크기의 리스트를 선언 해야 하기 때문

# 일반적으로 별도의 리스트를 선언하고 그 안에 정렬에 대한 정보를 담는다는 특징이 있음

array = [7,5,9,0,3,1,6,2,9,1,4,8,0,5,2]
'''
1. 가장 큰 데이터가 9, 가장 작은 데이터가 0
2. 정렬해야할 데이터의 범위는 0-9, 리스트의 인덱스가 모든 범위를 포함할 수 있도록 한다.
3. 즉, 단순히 크기가 10인 리스트를 선언
4. 처음에는 리스트의 모든 데이터가 0이 되도록 초기화
5. 데이터를 하나씩 확인하며 데이터의 값과 동일한 인덱스의 데이터를 1씩 증가시키면 계수 정렬 완료
6. 결과적으로 각 데이터가 몇 번 등장했는지 그 횟수가 기록됨
'''

# max, min
max_value = max(array)
min_value = min(array)

# 정렬 데이터 리스트 개수 및 0으로 초기화
count_list = []

for i in range(min_value, max_value+1):
    count_list.append(0)
    
# 다른 방법
count = []
for i in range(len(array)):
    count[array[i]] += 1
    
# 데이터와 count_list 인덱스 값과 일치하면 인덱스의 데이터를 + 1
for i in array:
    if i <= len(count_list): # 굳이 필요없음...
        count_list[i] += 1

print(count_list)

# 각 인덱스 값에서 횟수만큼 출력
for i in range(len(count_list)):
    # count
    for j in range(count_list[i]):
        print(i, end=' ')
        
[2, 2, 2, 1, 1, 2, 1, 1, 1, 2]
0 0 1 1 2 2 3 4 5 5 6 7 8 9 9

<데이터의 특성을 파악하기 어렵다면 퀵 정렬 이용하는 것이 유리하다>

1. 데이터의 개수가 매우 많을 때엗 특정 조건만 만족한다면 효과적(= 데이터가 많으면 사용하기 어렵)

2. 데이터의 크기가 많이 중복되어 있을수록 유리하며 항상 사용할 수는 없다.

3. 보통 코테는 메모리 공간상의 제약과 입출력 시간 문제로 인해 입력되는 데이터 개수는 1,000만개미만 으로 출제

 

Python의 정렬 라이브러리

https://cord-ai.tistory.com/33 (sort, sorted 차이 참조)

- sorted(), 퀵 정렬과 동작 방식이 비슷한 병합 정렬을 기반으로 만들어졌음

- 병합 정렬은 일반적으로 퀵 정렬보다 느리지만 O(NlogN)을 보장한다는 특징이 있음

- 딕셔너리 자료형 등을 입력받아도 정렬될 결과를 출력, 집합 자료형이나 딕셔너리 자료형을 입력받아도 반환되는 결과는 리스트 자료형이다.

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

# sorted()
res = sorted(array)
print(res)

# sort() - 내부 원소를 바로 정렬
array.sort()
print(array)

# sorted(), sort() = key 매개변수를 입력으로 받을 수 있다.
# key == 함수
array = [("바나나", 2), ("사과", 5), ("딸기", 3)]

def setting(data):
    return data[1]

res = sorted(array, key= lambda x : x[1])
res1 = sorted(array, key= setting)

print(res)
print(res1)

[('바나나', 2), ('딸기', 3), ('사과', 5)]
[('바나나', 2), ('딸기', 3), ('사과', 5)]