⚫️ 요약 정리

데이터를 특정한 기준에 따라서 정렬하기 위해 사용하는 알고리즘이다. 대표적인 알고리즘들의 특징과 시간복잡도를 잘 알아두고 상황에 맞게 사용하자.

문제 상황에 따라 적절한 정렬알고리즘이 공식처럼 사용된다. 데이터의 개수가 적을때, 많지만 데이터의 범위가 한정적일때, 이미 데이터가 정렬되어있는 등 다양한 상황에서 적절한 알고리즘을 공식처럼 사용할 수 있도록 공부해보자.

이번 공부에서는 가장 많이 사용되는 ‘선택정렬’ , ‘삽입정렬’ , ‘퀵정렬’, ‘계수정렬’ 네 가지를 다룬다.

▪️ 시간복잡도

정렬 알고리즘	평균 시간복잡도	공간복잡도	특징
선택정렬	O(N^2)	O(N)	아이디어가 매우 간단하다.
삽입정렬	O(N^2)	O(N)	데이터가 거의 정렬되어 있을 때, 가장 빠르다.
퀵정렬	O(NlogN)	O(N)	대부분의 경우에 가장 적합하고, 충분히 빠르다.
계수정렬	O(N+K)
(K는 데이터 중에서 가장 큰 수)	O(N+K)
(K는 데이터 중에서 가장 큰 수)	- 데이터의 크기가 한정되어있는 경우에만 사용이 가능하다.

정렬 알고리즘	핵심 아이디어
선택정렬	가장 작은 데이터를 ‘선택’해서 정렬되지 않은 데이터중에 가장 앞쪽에 있는 데이터와 위치를 바꾸는 방법
삽입정렬	데이터를 앞에서부터 하나씩 확인하며 데이터를 적절한 위치에 ‘삽입’하는 방법
퀵정렬	기존 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법
계수정렬	특정한 값을 가지는 데이터의 개수를 ‘카운트’하는 방법

기준데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법
일반적인 상황에서 가장 많이 사용되는 알고리즘
병합정렬과 더불어 대부분의 프로그래밍 언어의 정렬 라이브러리의 근간이 되는 알고리즘
- C언어, 자바, 파이썬의 정렬 라이브러리도 퀵정렬을 채택한 하이브리드 정렬 방식을 사용중 (스위프트는??)
가장 기본적인 퀵 정렬은 첫 번째 데이터를 **기준 데이터(pivot)**으로 설정한다.

1️⃣ 현재 pivot의 값은 5이다. (첫번째 값) 왼쪽부터 5보다 큰 데이터를 선택하므로, 7이 선택되고, 오른쪽부터 5보다 작은 데이터를 선택하기에 4를 선택한다. (오름차순기준) 이제 두 데이터의 위치를 서로 변경한다.

Untitled