Sorting (정렬)

정렬이란 데이터를 특별한 기준에 따라 순서대로 나열한 것을 말한다.

 

※ 여러 가지 정렬 알고리즘

 

 (1) 선택 정렬(selection sort)

• 가장 우선순위가 높은 데이터부터 순서대로 앞쪽에 배치하는 정렬 방법
• 시간 복잡도: O(N(N+1)/2) ≈ O(N²)

 (2) 삽입 정렬(insertion sort)

• 데이터를 하나씩 확인하며 적절한 위치에 삽입하는 정렬 방법
• 시간 복잡도: O(N²) / O(N)  ← 이미 정렬된 데이터일 경우 (최선)

 (3) 퀵 정렬(quick sort)

• 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 정렬 방법
• 기준 데이터를 pivot이라 부른다.
• 호어 분할(Hoare partition): 주어진 배열의 가장 앞 데이터를 pivot으로 설정하는 분할방법
• 시간 복잡도: O(NlogN) / O(N²) ← 이미 정렬된 데이터일 경우 (최악)

 (4) 계수 정렬(Counting sort)

• 범위 내 각 값에 해당하는 데이터가 몇 개 있는지 세는(counting) 방법
• 특정 조건에 부합할 때만 사용할 수 있지만 매우 빠르다
• 조건: 데이터 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때
• 정렬해야 할 데이터 외에 또 하나의 배열 필요
• 시간 복잡도: O(N+K) (여기서 K는 데이터 중 최댓값의 크기)
• 공간 복잡도: O(N+K) → 때에 따라 굉장히 비효율적

※ 파이썬의 정렬 라이브러리

  - 최악의 경우에도 시간복잡도 O(NlogN)을 보장한다.

• sorted(변수명) - 리스트, 딕셔너리 자료형, 집합 자료형 등을 정렬할 수 있다. (반환값은 항상 list)

sorted() 함수 예시

• 변수명.sort(); - 리스트

sort() 함수 예시

"이것이 취업을 위한 코딩테스트다 with 파이썬(나동빈 저)"를 보고 정리한 내용

출처| 이것이 취업을 위한 코딩테스트다 with 파이썬(나동빈 저)