[알고리즘] 정렬 알고리즘

* 정렬 알고리즘

- 데이터를 특정한 기준에 따라 순서대로 나열하는 것

[선택 정렬]
: 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복

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)

- 매번 선형 탐색을 하는 것과 동일 -> 이중 반복문 활용!

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

 

[삽입 정렬]
: 처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입
선택 정렬에 비해 구현 난이도가 높은 편이지만, 일반적으로 더 효율적으로 동작

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까지 1씩 감소하며 반복하도록!
        if array[j] < array[j-1]:
            array[j], array[j-1] = array[j-1], array[j]
        else :  
          break

print(array)

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

- 최선의 경우(현재 리스트의 데이터가 거의 정렬되어 있는 경우)

- 시간 복잡도 : O(N**2) / 최선의 경우 O(N)을 가질 수 있다.(break로 멈출 수 있기 때문)

 

[퀵 정렬]
: 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법

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]
            left +=1
        while (right > start and array[right] >= array[pivot]
            rightt -=1
        if (left > right):
            array[right], array[pivot] = array[pivot], array[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(array)

- 일반적인 상황에서 가장 많이 사용되는 정렬 알고리즘

- 병합 정렬과 더불어 대부분의 프로그래밍 언어의 정렬 라이브러리의 근간이 되는 알고리즘

- 가장 기본적인 퀵 정렬은 첫 번째 데이터를 기준 데이터(pivot)로 설정하는 것.

- 정렬 수행 중 위치가 엇갈리는 경우 피벗과 작은 데이터의 위치를 서로 변경

-> 피벗을 기준으로 데이터 묶음을 나누는 분할 작업 + 피벗을 기준으로 두 그룹을 다시 재귀

- 시간 복잡도 : O(NlogN) / 최악의 경우 O(N**2)

 

[계수 정렬]
: 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠르게 동작하는 정렬 알고리즘
데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때 사용 가능
주어지는 데이터들의 범위가 모두 담길 수 있도록 새로운 리스트를 생성하고 각 데이터가 몇 번 등장했는지 카운트!

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

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

for i in range(len(array)):
    count[array[i]] +=1

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

- 데이터의 개수가 N개, 데이터(양수) 중 최댓값이 K일 때 최악의 경우에도 수행 시간이 O(N+K)를 보장

- 동일한 값을 가지는 데이터가 여러 개 등장했을 때 효과적

 

---

[대표 예제 1] 두 배열의 원소 교체

매번 배열 B의 가장 큰 수와 배열 A의 가장 작은 수를 바꾼다는 방식
- A에 대하여 오름차순 정렬 + B에 대하여 내림차순 정렬
- O(NlogN)을 보장해야 한다.

n , k = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))

a.sort()
b.sort(reverse=True)

for i in range(k):
    if a[i] < b[i]:
        a[i] , b[i] = b[i] , a[i]
    else : 
        break

print(sum(a))

---

강의 내용 출처 - https://youtu.be/KGyK-pNvWos

(이코테 2021 강의 몰아보기) 4. 정렬 알고리즘