(Sort) 데이터 정렬 순서 정리

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)

​​

정렬이란?

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

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

)

​​

​​

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 – 한 번만 최소 수를 찾아 맨 앞으로 보냅니다.

또한 매번 최소 수를 찾기 위해 비교 연산이 필요합니다.

따라서 구현 코드의 시간 복잡도를 큰 표기법으로 나타내면 ​​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))

4. 계수 정렬 => 데이터의 크기 범위가 제한되며 정수 유형의 경우에만 사용 가능

계수 정렬은 앞에서 설명한 세 가지 정렬 알고리즘과 같이 직접 데이터 값을 비교한 후입니다.

위치를 변경하고 정렬하는 방법은 아닙니다.

통상은 다른 리스트를 선언한 후, 그 안에 정렬에 관한 정보를 넣는 방식입니다.

​​

📌 계수 정렬의 조건은 다음과 같습니다.

1. 데이터 크기 범위 제한되면
   • ex) 0 이상 100 이하의 성적 매칭

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

3. 최대 데이터와 최소 데이터의 차이가 1,000,000을 초과하지 않는 경우

​​

(작동 프로세스)

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

​​

계수 정렬은

1. 우선 최대 데이터와 최소 데이터 범위가 모두 맞도록

단일 목록을 생성합니다.

2. 첫 번째 목록의 모든 데이터는 0이 되도록 초기화합니다.

3. 데이터를 하나씩 확인하고 데이터 값과 동일한 인덱스의 데이터를 하나씩 늘리면

카운트 정렬이 완료됩니다.

​​

.📢 그 결과 목록에는 각 데이터가 몇 번 등장했는지 그 횟수가 기록됩니다.

​​

(소스 코드)

# 모든 원소의 값이 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=' ') # 띄어쓰기를 구분으로 등장한 횟수만큼 인덱스 출력