CS/Sort

[Sort] 데이터 정렬에 대한 정리

배준오 2023. 3. 18. 02:33
반응형
arr = [35,33,42,10,14,19,27,44,26]

def quick_sort(arr,start,end):
    if start >= end: # 원소가 1개인 경우 종료
        return
    pivot = start # 피벗은 첫번째 원소
    left = start + 1
    right = end
    while left <= right:
        # 피벗보다 큰 데이터를 찾을 때까지 반복
        while left <= end and arr[left] <= arr[pivot]:
            left += 1
        # 피벗보다 작은 데이터를 찾을 때까지 반복
        while right > start and arr[right] >= arr[pivot]:
            right -= 1
        if left > right: # 엇갈렸다면 작은 데이터와 피벗 교체
            arr[right], arr[pivot] = arr[pivot], arr[right]
        else: # 엇갈리지 않았다면 작은 데이터와 큰 데이터를 교체
            arr[left], arr[right] = arr[right], arr[left]
    # 분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬 하기
    quick_sort(arr, start, right - 1)
    quick_sort(arr, right+1, end)

quick_sort(arr,0,len(arr) - 1)
print(arr)

정렬 카테고리 용도 :

🔎 데이터 정렬에 필요한 기법들을 정리하기 위함

📘 '이것이 취업을 위한 코딩테스트다' 책을 통해 공부하였습니다.

  • 선택 정렬 (Selection Sort)
  • 삽입 정렬 (Insertion Sort)
  • 퀵 정렬 (Quick Sort)
  • 계수 정렬 (Count Sort)

정렬(Sort)이란?

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

(프로그램을 작성할 때 가장 많이 사용되는 알고리즘 입니다.)

  1. 선택 정렬 (Selection Sort)

데이터가 무작위로 여러 개 있을 때, 이 중에서 가장 작은 데이터를 선택해

맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두 번째

데이터와 바꾸는 과정을 반복하는 것. (매번 가장 작은 것은 선택)

[동작 과정]

출처 - https://en.wikipedia.org/wiki/Selection_sort

[소스 코드]

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

for i in range(len(arr)):
    min_index = i
    for j in range(i + 1, len(arr)):
        if arr[min_index] > arr[j]:
            min_index = j
    arr[i], arr[min_index] = arr[min_index], arr[i] # 스와프(두 변수의 위치 변경)
print(arr)

[시간 복잡도]

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

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

따라서 구현 코드의 시간복잡도를 빅오 표기법으로 나타내면 O(N^2) 입니다

(데이터의 개수가 10,000개 이상이면 시간 초과가 날 수 있습니다!)

2. 삽입 정렬 (Insertion Sort)

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

삽입 정렬은 특정한 데이터를 적절한 위치에 '삽입'한다는 의미에서 삽입 정렬 이라고 부릅니다.

더불어 삽입 정렬은 특정한 데이터가 적절한 위치에 들어가기 이전에,

그 앞까지의 데이터는 이미 정렬되어 있다고 가정합니다.

[동작 과정]

출처 - https://en.wikipedia.org/wiki/Insertion_sort

[소스 코드]

arr = [6,5,3,1,8,7,2,4]

for i in range(1,len(arr)):
    for j in range(i,0,-1): # 인덱스 i부터 1까지 감소하며 반복
        if arr[j] < arr[j-1]: # 한칸씩 왼쪽
            arr[j], arr[j-1] = arr[j-1], arr[j]
        else:
            break
print(arr)

[시간 복잡도]

삽입 정렬의 시간 복잡도는 O(N^2)입니다.

앞서 설명한 선택정렬과 시간 복잡도가 같지만, 삽입 정렬의 경우

데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작합니다.

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

3. 퀵 정렬(Quick Sort)

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

퀵 정렬은 기준(pivot)을 설정한 다음 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는

방식으로 동작합니다. (왼쪽 분할에는 피벗보다 작은 데이터가, 오른쪽 분할에는 피벗보다

큰 데이터가 위치됩니다.)

[동작 과정]

출처 - https://engineering.fb.com/2022/07/20/security/hermes-quicksort-to-run-doom/

[소스 코드]

arr = [35,33,42,10,14,19,27,44,26]

def quick_sort(arr,start,end):
    if start >= end: # 원소가 1개인 경우 종료
        return
    pivot = start # 피벗은 첫번째 원소
    left = start + 1
    right = end
    while left <= right:
        # 피벗보다 큰 데이터를 찾을 때까지 반복
        while left <= end and arr[left] <= arr[pivot]:
            left += 1
        # 피벗보다 작은 데이터를 찾을 때까지 반복
        while right > start and arr[right] >= arr[pivot]:
            right -= 1
        if left > right: # 엇갈렸다면 작은 데이터와 피벗 교체
            arr[right], arr[pivot] = arr[pivot], arr[right]
        else: # 엇갈리지 않았다면 작은 데이터와 큰 데이터를 교체
            arr[left], arr[right] = arr[right], arr[left]
    # 분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬 하기
    quick_sort(arr, start, right - 1)
    quick_sort(arr, right+1, end)

quick_sort(arr,0,len(arr) - 1)
print(arr)

[시간 복잡도]

퀵 정렬의 평균 시간 복잡도는 O(NlogN)입니다. (최악 O(N^2))

데이터의 개수(N)
N^2(선택,삽입 정렬)
NlogN(퀵 정렬)
N = 1,000
1,000,000
10,000
N = 1,000,000
1,000,000,000,000
20,000,000

4. 계수 정렬(Count Sort) => 데이터의 크기 범위가 제한되어 정수 형태일 때만 사용가능

계수 정렬은 앞서 다룬 3가지 정렬 알고리즘 처럼 직접 데이터의 값을 비교한 뒤에

위치를 변경하며 정렬하는 방식이 아닙니다.!

일반적으로 별도의 리스트를 선언 후 그 안에 정렬에 대한 정보를 담는 방식입니다.

📌 계수 정렬의 조건은 아래와 같습니다

  1. 데이터의 크기 범위가 제한된 경우
    • ex) 0이상 100이하 성적 데이터 정렬

2. 데이터가 양의 정수인 경우

3. 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000을 넘지 않는 경우

[동작 과정]

출처 - https://medium.com/@manishsundriyal/counting-sort-in-javascript-abf976e66b8c

계수 정렬은,

1. 먼저 가장 큰 데이터와 가장 작은 데이터의 범위가 모두 담길 수 있도록

하나의 리스트를 생성합니다.

2. 처음 리스트의 모든 데이터는 0이되도록 초기화 합니다.

3. 데이터를 하나씩 확인하며 데이터의 값과 동일한 인덱스의 데이터를 1씩 증가시키면

계수정렬이 완료 됩니다.

.📢 결과적으로 리스트에는 각 데이터가 몇 번 등장했는지 그 횟수가 기록 됩니다.

[소스 코드]

# 모든 원소의 값이 0보다 크거나 같다고 가정
arr = [7,5,9,0,3,1,6,2,9,1,4,8,0,5,2]
# 모든 범위를 포함하는 리스트 선언(모든 값은 0으로 초기화)
count = [0] * (max(arr) + 1)

for i in range(len(arr)):
    count[arr[i]] += 1 # 각 데이터에 해당하는 인덱스 값 증가
for i in range(len(count)): # 리스트에 기록된 정렬 정보 확인
    for j in range(count[i]):
        print(i,end=' ') # 띄어쓰기를 구분으로 등장한 횟수만큼 인덱스 출력

[시간 복잡도]

모든 데이터가 양의 정수인 상황에서 데이터의 개수를 N, 데이터중 최대값의 크기를 K

라고 할 때, 계수 정렬의 시간 복잡도는 O(N + K) 입니다.

🎊 이상으로 데이터 정렬에 대한 정리를 마치겠습니다.

반응형