Sort

특징

• 데이터를 특정한 기준에 따라서 순서대로(오름차순 or 내림차순) 정렬하는 것
• 정렬을 하면, 이진탐색이 가능해짐
• 상황에 적절하게 정렬을 사용하면 효율적인 프로그램을 짤 수 있음
• 면접에서도 자주 정렬에 대해 질문함

여러 정렬 알고리즘

선택 정렬

• 매번 가장 작은 것을 선택하여 해당되는 앞자리에 두는 방법

• O(N^2) : N-1 번 기준보다 뒤에 있는 원소들을 살펴보며 최소값을 찾음

• 파이썬에서는 swap 을 매우 편리하게 가능

  a, b = b, a

삽입 정렬

• 데이터를 하나씩 확인하여 적절한 위치에 삽입
• 선택 정렬보다는 빠르지만 조금 더 구현이 어려움
• 거의 정렬되어 있을 때 유용함
• 두번째 원소부터 정렬 시작, 이전에 있는 원소들은 정렬됐다고 가정
• O(N^2) : 최악의 경우 정렬된 모든 부분을 살펴볼 수 있음
• 최선의 경우 O(N) : 이미 정렬된 경우엔 앞을 보지 않음
• 입력이 거의 정렬된 경우에는 삽입 정렬이 퀵정렬보다 좋음

퀵 정렬

• 병합 정렬만큼 빠르고 가장 많이 사용됨

• 기준 데이터를 설정하고 기준보다 큰 데이터와 작은 데이터의 위치 바꾸기

• 호어 분할 방식에서는 첫 원소를 피벗으로 둠

  • 피벗 위치를 기준으로 오른쪽으로 가며 피벗의 값보다 큰 값과 끝에서부터 왼쪽으로 오며 피벗의 값보다 작은 값을 스왑한다.
  • 계속 스왑해나가다가, l 과 r 이 엇갈리면(if l > r) r 의 값과 피벗을 스왑한다. 피벗을 기준으로 왼쪽은 피벗보다 작은 값들이 있고 오른쪽은 피벗보다 큰 값들이 있게 된다.
  • 재귀적으로 피벗 왼쪽 구간들과 오른쪽 구간들을 각각 정렬해준다.
  • 리스트의 크기가 1 이 되면(if start ≥ end) 탈출한다. start 는 리스트의 시작 위치, end 는 리스트의 끝 위치.

• 다음은 위 방식보다는 비효율적이지만 파이썬의 장점을 살려 보기 간편한 코드

  def quick_sort(arr):
  	if len(arr) <= 1:
  		return arr
  
  	pivot = arr[0]
  	tail = arr[1:]
  
  	left = [x for x in tail if x <= pivot]
  	right = [x for x in tail if x > pivot]
  
  	return quick_sort(left) + [pivot] + quick_sort(right)
  
  sorted_arr = quick_sort(arr)

• 평균적으로 O(NlogN) : 왼쪽과 오른쪽으로 나뉘며 두갈래로 진행되기 때문

• 최악의 경우 O(N^2) : 모두 정렬된 경우

• C++, 파이썬 모두 피벗 설정에 추가적인 로직이 들어가 O(NlogN) 을 보장함

계수 정렬

• 특정한 조건이 부합할 때만 사용할 수 있는 매우 빠른 알고리즘
• 조건 : 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때, 무한한 범위를 가질 수 있는 실수 데이터는 안됨
• 일반적으로 가장 적은 데이터 값과 가장 큰 데이터 값 차이가 10^6 안넘어야 함, 모든 범위를 담을 수 있는 크기의 리스트 만들기 때문
• 최악의 경우에도 O(N+K) : N = 데이터 개수, K = 데이터 중 최댓값
• 기존 정렬과 다르게 다른 원소와 비교하지 않음
• 최댓값 크기로 리스트 생성, 모든 원소 순회하며 원소값에 해당하는 배열에 count 를 올림, 리스트를 순차적으로 순회하며 카운트 값만큼 적어내면 됨
• 기수 정렬과 더불어 현존하는 정렬 알고리즘 중 가장 빠름
• 값 범위가 적게 제한되어 있고 동일한 값이 많을 때 효율적

코테에서 정렬

파이썬의 정렬 라이브러리

• sorted() 함수
  • 병합 정렬 기반으로 만들어짐, 최악의 경우에도 O(NlogN) 보장
  • 정렬된 리스트 리턴함
• 리스트 내장 sort() 함수
  • 리스트 자동 정렬, 리턴 없음
• 매개변수 key 로 정렬 기준 설정 가능
• 단순 정렬 상황에서는 기본 정렬 라이브러리 사용하고, 데이터 범위가 한정되어 있으며 어 빠르게 동작해야 할 때는 계수 정렬 사용할 것

코테에서의 정렬 알고리즘

1. 정렬 라이브러리로 풀 수 있는 문제 : 라이브러리 사용해서 풀면 됨
2. 정렬 알고리즘 원리에 대해 물어보는 문제 : 선택 정렬, 삽입 정렬, 퀵 정렬 등의 원리를 알아야 풀 수 있음
3. 더 빠른 정렬 문제 : 퀵 정렬로도 풀 수 없는 문제. 계수 정렬 등으로 해결하거나 문제에서의 알고리즘 개선을 통해 해결 가능

참조

• 이것이 취업을 위한 코딩테스트다 with Python 도서, 나동빈