Sort

정렬(Sort)이란?

• 2개 이상의 자료를 특정 기준에 의해 작은 값부터 큰 값(오름차순: ascending) or 작은 값(내림차순: descending) 재배열하는 것
• 정렬에서 키란, 자료를 정렬하는 기준이 되는 특정 값을 의미한다.
  • 서류 번호대로 정렬하기, 카드 번호대로 정렬하기 ...

대표적인 정렬 방식의 종류

1. 버블 정렬 (Bubble Sort)
2. 카운팅 정렬 (Counting Sort)
3. 선택 정렬 (Selection Sort)
4. 퀵 정렬 (Quick Sort)
5. 삽입 정렬 (Insertion Sort)
6. 병합 정렬 (Merge Sort)

버블 정렬 (Bubble Sort)

• 인접한 두 개의 원소를 비교하며 자리를 계속 교환하는 방식
• 교환하며 자리를 이동하는 모습이 물 위에 올라오는 거품모양 같아서 버블 정렬이라고 함
• O(N^2)의 시간 복잡도를 가짐
• 정렬 과정
  1. 첫 번째 원소부터 인접한 원소끼리 계속 자리를 교환하면서 맨 마지막 자리까지 이동
  2. 한 단계가 끝나면 가장 큰 원소 또는 가장 작은 원소가 마지막 자리로 정렬됨

카운팅 정렬 (Counting Sort)

• 항목들의 순서를 결정하기 위해 지합에 각 항목이 몇 개씩 있는지 세는 작업을 하여, 선형 시간에 정렬하는 효율적인 알고리즘
• O(N)의 시간 복잡도를 가짐
• 정렬 과정
  1. 정수나 정수로 표현할 수 있는 자료에 대해서만 적용 가능한데, 이는 각 항목의 발생 횟수를 기록하기 위해, 정수 항목으로 인덱스되는 카운트들의 리스트를 사용하기 때문임
  2. 카운트들을 위한 충분한 공간을 할당하려면 집합 내의 가장 큰 정수를 알아야 함

퀵 정렬 (Quick Sort)

• O(NlogN)의 시간 복잡도를 가짐
• 정렬 알고리즘 ver1.
  1. 기준이 되는 데이터인 pivot을 하나 선택한다.
     • 일반적으로 가장 많이 사용되는 것은 주어진 arr의 첫 번째 요소이다.
  2. pivot을 기준으로 pivot보다 작은 데이터와 pivot보다 큰 데이터로 구분한다.
  3. pivot을 pivot보다 작은 데이터와 pivot보다 큰 데이터 사이에 위치시키면 pivot의 위치가 결정된다.
     • [pivot이하][pivot][pivot초과]
  4. pivot보다 작은 데이터와 pivot보다 큰 데이터 각각에서 동일하게 퀵 정렬을 수행한다. (재귀적으로 수행)

# 가장 일반적인 퀵 정렬 ver1.
def quick_sort(arr, start, end):
	if start >= end: return  # 원소가 1개인 경우
    pivot = start  # 피벗은 첫 요소
    left, right = start+1, 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[right], arr[left] = arr[left], arr[right]
    # 분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬 수행
    quick_sort(arr, start, right-1)
    quick_sort(arr, right+1, end)

• 정렬 알고리즘 ver2. (파이썬에 더 적합하게)
  1.동일하게 pivot에 arr의 첫 번째 요소를 넣고, pivot을 제외한 나머지 데이터를 tail로 지정한다.
  2. leftSide에 tail 중 pivot보다 작거나 같은 데이터를, rightSide에 tail 중 pivot보다 큰 데이터를 저장한다.
  3. quick_sort(leftSide) + [pivot] + quick_sort(rightSide)로 pivot의 위치를 정의하면서 재귀적으로 왼쪽, 오른쪽 부분을 다시 퀵 정렬한다.

# 퀵소트 ver2.
# 왼쪽, 오른쪽 부분을 나누는 과정에서 더 많은 비교 연산이 필요해 시간면에서 비효율적
# but, 더 직관적이고 이해하기 쉽다는 장점이 있다.
def quick_sort(arr):
	# 리스트가 하나 이하의 원소를 가지면 종료
    if len(arr) <= 1:
    	return arr
    
    pivot, tail = arr[0], arr[1:]
    
    leftSide = [x for x in tail if x <= pivot]
    rightSide = [x for x in tail if x > pivot]
    
    return quick_sort(leftSide) + [pivot] + quick_sort(rightSide)