21~25강:: 정렬 알고리즘
👉🏻 정렬 알고리즘
- 정렬(Sorting)이란 데이터를 특정한 기준에 따라 순서대로 나열하는 것
- 일반적인 문제 상황에 따라서 적절한 정렬 알고리즘이 공식처럼 사용된다
- 데이터의 개수가 적을 때
- 데이터의 개수가 많지만 데이터의 범위가 특정 범위로 한정되어있을 때
- 이미 데이터가 거의 정렬되어 있는 경우
- 값을 기준으로 정렬한 결과를 어떻게??
- 사람은 한 눈에 보이지만, 컴퓨터는 구체적 알고리즘을 통해 명시해주어야한다
1️⃣ 선택 정렬
- 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는데 이터와 바꾸는 것을 반복한다
- 매번 현재의 범위에서 가장 작은 데이터를 골라 가장 앞으로 보내주는 것이다
- 첫 번째 원소 정렬 완료
- 나머지 중에서 가장작은 1
- 처리되지 않은 원소가 하나 남았을 때는 앞으로 보내봤자 자기 자신의 자리와 동일하기 때문에 처리하지 않는다
- 탐색 범위는 반복할 때 마다 줄어든다
- 매번 가장 작은 원소를 찾기 위해, 탐색 범위만큼 데이터를 하나씩 확인해서 가장 작은데이터를 찾아야 하기 때문에
매번 선형 탐색을 수행하는 것과 동일함
- 이중 반복문을 이용해 선택 정렬을 구현할 수 있다
🧩 선택 정렬 소스 코드
- i 값은 0 ~ (데이터개수 - 1)까지 반복
- i는 가장 작은 데이터와 위치가 바뀔 데이터의 인덱스
- 결과적으로 i는 매번 앞으로 보내고자 하는 앞쪽 원소의 위치 (??)
- 반복할 때 마다 매번 가장 작은 원소의 인덱스를 고를 수 있도록 한다
- 처음엔 가장 앞쪽 원소가 가장 작은 원소
- j는 (i + 1) ~ (전체 원소 개수 -1) 차례로 증가하며 선형 탐색
- 현재 가장 작은 원소보다 더 작은 원소가 있다면 그 위치 인덱스 값을 min_index로 담기게 함
- 안쪽 반복문 수행 완료 시 가장 작은 원소 인덱스가 min_index에 담김
- 가장 앞 원소와 가장 작은 원소를 서로 바꿔줌
- 파이썬 스와프 연산
* C++ ver
* Java ver
👉🏻 선택 정렬의 시간 복잡도
- 선택 정렬은 N번 만큼 가장 작은 수를 찾아서 맨 앞으로 보내야 한다
- 구현 방식에 따라서 사소한 오차는 있을 수 있지만, 전체 연산 횟수는 다음과 같다
- 이는(N² + N - 2) / 2로 표현할 수 있는데, 빅오 표기법에 따라서 O(N²)이라고 작성한다
2️⃣ 삽입 정렬
- 처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입한다
- 선택 정렬에 비해 구현 난이도가 높은 편이지만, 일반적으로 더 효율적으로 동작한다
- 데이터를 하나씩 확인하면서 이 데이터는 어느 위치에 들어가는 것이 맞은지 매번 계산해서 적절한 위치에 넣어줌
- 앞 쪽 원소들이 이미 정렬되어있다 가정 (7이 정렬되어있다 판단)
- 뒷쪽 원소를 앞쪽 원소의 위치 중에서 한 곳으로 들어가도록 만드는 방식으로 동작 (5가 7의 왼쪽으로? 오른쪽으로?)
* 기본적으로 정렬 알고리즘에 대해 다룰 때 오름차순 정렬을 수행한다고 가정하고 살펴보는 중
- 5위 의 위치를 바꾼 뒤 다음 원소인 9의 위치를 정하기
- 왼쪽 데이터와 비교해서 자리를 정함
- 5, 7, 9 보다 작기 때문에 매번 비교해가면서 가장 첫 번쨰 위치까지 들어가도록 함
- 매번 왼쪽 데이터와 위치를 바꿔가면서 최종적으로 첫 번째 원소의 위치로 가게 함
- 원소의 위치를 바꿔가면서 위치를 바꿈
🧩 삽입 정렬 소스코드
- 두 번째 원소부터 시작, 왼쪽으로 이동해나가면서 위치를 바꾼다
- range() 함수 안에 3개의 인자가 들어갈 경우 start, end, step이다
- j는 삽입하고자 하는 원소의 위치
- 왼쪽보다 작다면 스와핑
- 왼쪽보다 크거나 같다면 그 자리에
- 두 번째 데이터 ~ 마지막 데이터 어떤 위치에 들어갈지 안쪽 반복문을 통해 찾음
* C++ ver
* Java ver
👉🏻 삽입 정렬의 시간 복잡도
- 삽입 정렬의 시간 복잡도는 O(N²)이며, 선택 정렬과 마찬가지로 반복문이 두 번 중첩되어 사용된다
- 삽입 정렬은 현재 리스트의 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작한다
- 최선의 경우 O(N)의 시간 복잡도를 가진다
- 이미 정렬되어 있는 상태에서 다시 삽입 정렬을 수행하면 어떻게 될까?
- 1부터 시작했을 때 왼쪽 0이 자신보다 작기 때문에 멈춤... 모두 마찬가지
- 오름차순 정렬 수행하는데 이미 오름차순 정렬 되어있다면
각 원소가 들어갈 위치를 고를 때 선형 탐색을 수행, 탐색 과정이 바로 멈춰지기 때문에
사실상 왼쪽 데이터 중에 자신이 어디로 들어갈지 고르는 부분이 상수 시간으로 대체되기 때문에
전체 정렬을 위한 시간 복잡도가 O(N)이 된다
- 이중 for문이 사용되었다고 해서 반드시 O(N²)인 것은 아니다.
만약 반복문 안에 별도의 함수가 호출된다면 그 함수의 시간복잡도까지 고려해야 함
- 위 예시는 단순히 이중 반복문 안에서 비교연산 + 스와핑 연산이 수행되기 때문에 O(N²)라고 말할 수 있다
3️⃣ 퀵 정렬
- 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법이다
- 일반적인 상황에서 가장 많이 사용되는 정렬 알고리즘 중 하나이다
- 병합 정렬과 더불어 대부분의 프로그래밍 언어의 정렬 라이브러리의 근간이 되는 알고리즘이다
- 가장 기본적인 퀵 정렬은 첫 번째 데이터를 기준 데이터(Pivot)로 설정한다
- 이름에서 알 수 있든 굉장히 빠른 정렬 알고리즘 중 하나이다
- 일반적으로 데이터의 특성과 관련 없이 우리가 표준적으로 사용할 수 있는 정렬 알고리즘 중 하나
- C언어, JAVA, Python의 표준 정렬 라이브러리도
퀵 정렬 / 병합 정렬의 아이디어를 채택한 하이브리드 방식의 정렬 알고리즘 사용
- 정렬 수행 과정에서 기준 데이터(pivot)를 설정한 뒤에 정렬을 수행
👉🏻 퀵 정렬 동작 예시
- 10개의 데이터
- 첫 번째 원소인 5를 pivot으로 설정
- 왼쪽에서부터 피벗보다 큰 데이터를 고르고, 오른쪽에서부터 피벗보다 작은 데이터를 고름
- 왼쪽에서 5보다 큰 7이 바로 선택됨
- 오른쪽에서 5보다 작은 값인 4가 선택됨
- 7과 4의 위치를 바꿔줌
- 다시 피벗을 기준으로 왼쪽에서는 더 큰 데이터를 고르고 오른쪽에서는 더 작은 데이터를 골라 위치를 바꿈
- 여기서는 9와 2
- 이번에도 왼쪽에서는 피벗값보다 큰 값을, 오른쪽에서는 피벗값보다 작은 값을 고른다
- 6과 1
- 그런데 이번에는 서로 위치가 엇갈렸다
- 이렇게 위치가 엇갈릴 경우, 작은 데이터와 피벗값의 위치를 바꿔준다
- 이를 반복하면 피벗값의 위치가 중간으로 들어감
- 데이터가 왼쪽과 오른쪽으로 분할됨
- 피벗값을 중심으로 왼쪽은 모두 피벗보다 작은 데이터, 오른쪽은 모두 피벗보다 큰 데이터가 된다
✅ 분할 / partition
- 하나의 피벗값에 대해 정렬을 위한 데이터의 범위가 왼쪽과 오른쪽으로 나뉨
- 왼쪽에 있는 데이터들과 오른쪽에 있는 데이터들 각각을 하나의 배열로 판단
- 왼쪽 데이터에 대해서 다시 한 번 퀵 정렬 수행
- 첫 번째 원소인 1이 피벗으로 설정된다
- 왼쪽에서부터는 피벗보다 큰 값, 오른쪽에서부터는 피벗보다 작은 값을 선택해 서로 바꿔주는 방식
- 오른쪽 데이터에 대해서도 퀵 정렬을 수행
- 첫 번째 원소인 6이 피벗으로 설정된다
- 왼쪽에서부터는 피벗보다 큰 값, 오른쪽에서부터는 피벗보다 작은 값을 선택해 서로 바꿔주는 방식
* 퀵 정렬이 수행되는 과정은 재귀적으로 수행된다
* 수행될 때 마다 정렬을 위한 범위가 점점 좁아진다
👉🏻 퀵 정렬이 빠른 이유
🧩 직관적인 이해
- 이상적인 경우 한 번 분할이 일어날 때 마다 데이터의 범위를 절반에 가깝게 분할시킬 수 있다면
전체 연산 횟수로 O(NlogN)을 기대할 수 있다
- 실제로는 피벗값을 기준으로 해서 왼쪽과 오른쪽으로 분할이 이루어진다고 봐야하지만
지금은 단순하게 데이터를 절반씩 묶어 분할
- 분할이 이루어질 때 마다 이상적인 경우 데이터의 범위가 절반씩 줄어듦
- 전체 높이를 확인했을 때 logN
- 데이터의 범위가 절반씩 줄어들기 때문에 밑이 2인 logN이라고 표현 가능 (log₂N)
- 연산 과정을 직관적으로 이해하고자 한다면
너비(데이터의 개수) = N
높이 = logN
전체 연산 횟수가 NlogN에 비례하는 만큼 발생할 것을 기대
이상적인 경우에서는 피벗을 선택할 때마다 정확히 중간에 위치한 경우가 가장 이상적입니다. 이렇게 되면 분할이 정확히 절반으로 이루어집니다. 이 때의 시간 복잡도를 알아보겠습니다.
- 첫 번째 분할: N개의 원소를 가진 배열을 피벗을 기준으로 두 부분으로 나누면, 각 부분은 약 N/2개의 원소를 가집니다.
- 두 번째 분할: 각 부분을 다시 피벗을 기준으로 나누면, 각 부분은 약 N/4개의 원소를 가집니다.
- k번째 분할: k번째 분할에서 각 부분은 약 N/2^k개의 원소를 가지게 됩니다.
이렇게 진행되면 분할 횟수는 logN이 되고, 각 분할 단계에서의 연산은 N번 진행되므로 전체 시간 복잡도는 O(NlogN)이 됩니다. 따라서, 퀵 정렬은 이상적인 경우에 대해 매우 효율적인 정렬 알고리즘으로 알려져 있습니다.
로그(logarithm)는 특정한 수를 다른 수로 몇 번 곱해야 하는지를 나타내는 수학적 개념입니다. 여기서 주로 사용되는 로그는 밑(base)이 2인 로그를 나타내는 log₂입니다.
log₂(N)는 "2를 몇 번 거듭제곱해야 N이 되는가"를 나타냅니다. 예를 들어, log₂(8)은 3이 됩니다. 왜냐하면 2³(2를 3번 곱한 값)이 8이기 때문입니다.
이제 퀵 정렬에서 말한 logN의 의미를 알아보겠습니다. 퀵 정렬에서는 각 분할마다 배열의 크기가 대략적으로 절반으로 줄어들기 때문에, 분할 횟수가 logN이 됩니다.
예를 들어, 배열의 크기가 8일 때, 첫 번째 분할에서는 대략 절반인 4로 나뉘고, 두 번째 분할에서는 4의 절반인 2로 나뉘어집니다. 세 번째 분할에서는 2의 절반인 1로 나뉘면서 분할이 종료됩니다. 이때 총 분할 횟수는 log₂(8)이므로 3이 됩니다.
따라서 퀵 정렬에서의 logN은 배열의 크기가 얼마나 빨리 절반으로 줄어들 수 있는지를 나타내며, 이는 효율적인 정렬 알고리즘의 중요한 특징 중 하나입니다.
👉🏻 퀵 정렬의 시간 복잡도
- 퀵 정렬은 평균의 경우 O(NlogN)의 시간 복잡도를 가진다
- 하지만 최악의 경우 O(N²)의 시간 복잡도를 가진다
- 첫 번째 원소를 피벗으로 삼을 때, 이미 정렬된 배열에 대해서 퀵 정렬을 수행하면 어떻게 될까?
- 첫 번째 원소인 0 이 pivot
- 왼쪽에서부터 큰 데이터를 찾으면 1
- 오른쪽에서부터 작은 데이터를 찾으면 (계속 없음)
결국 0이 골라짐
- 피벗값 자기 자신에서 자기 자신의 위치로 변경
분할이 이루어졌을 때 왼쪽은 존재하지 않고 오른쪽만 존재하는 것과 동일
- 오른쪽 부분에 대해서 다시 1을 pivot으로 설정해 퀵정렬 수행
- 매번 분할이 이루어질 때 마다 오른쪽만 남는 형태
- 최악의 경우 분할 수행되는 횟수가 N에 비례
- 분할 위해서 매번 선형탐색 수행
- 전체 시간 복잡도가 O(N²)이 되는 것
- 엄밀히 말하면 pivot값을 어떻게 설정하느냐에 따라서 분할이 절반에 가깝게 이루어지지 않고
한쪽 방향으로 편향된 분할이 발생할 수 있다
- 다양한 프로그래밍 언어에서 표준 정렬 라이브러리를 제공할 때 퀵 정렬을 기반으로 라이브러리가 작성되어있다면
최악의 경우에도 NlogN을 보장할 수 있는 형태로 구현되어있다
* 첫 번째 원소를 pivot으로 설정하면 최악의 경우 O(N²)의 시간복잡도가 나올 수 있음과
표준 라이브러리를 사용하면 최악의 경우에도 NlogN을 항상 보장함을 기억할 것
💡 일반적인 방정식
- 총 10개의 데이터
- 현재 정렬을 위한 데이터의 범위에 하나의 데이터만 포함되어있다면 종료
- 그렇지 않고 정렬할 데이터가 여러개인 경우
- 첫 번째 원소를 피벗값으로 설정
- 첫 번째 원소를 제외하고 오른쪽 원소들 중에서 가장 왼쪽을 left, 가장 오른쪽(마지막)을 right으로 설정
- 엇갈릴 때 까지 반복
- left가 가리키는 인덱스보다 right이 가리키는 인덱스의 값이 작다면 엇갈린 것이므로 그 때 반복문을 탈출
- 반복할 때 마다 피벗보다 큰 데이터를 찾을 때 까지 left를 1씩 증가
- 반복할 때 마다 피벗보다 작은 데이터를 찾을 때 까지 right을 1씩 감소
→ left는 항상 오른쪽으로 가고 right은 항상 왼쪽으로 가기 때문에 이 과정 자체를 선형 탐색이라고 볼 수 있다
- 결과적으로 left와 right값을 확인해서 위치가 엇갈렸다면 작은 데이터와 피벗 값의 위치를 바꿔준다
- 엇갈린 이후 right이 가리키는 값이 더 작은 값이 되기 때문에 array[right]과 array[pivot]의 위치를 바꿔주면 된다
- 엇갈리지 않았다면 작은 데이터와 큰 데이터의 위치를 바꿔준다
- 분할 이후 왼쪽 부분과 오른쪽 부분 각각에서 정렬 수행
- 재귀적으로 quick_sort함수를 호출
- 이상적인 경우 왼쪽과 오른쪽이 균형있게 분할이 이루어져 빠르게 동작할 것을 기대
- 오름차순 정렬 수행된 결과
* C++ ver
* Java ver
https://github.com/ndb796/python-for-coding-test/blob/master/6/4.java
💡 파이썬의 장점을 살린 방식
- 리스트 슬라이싱과 리스트 컴프리헨션을 활용해 짧은 코드로 간결하게 작성 가능
- 피벗값을 설정할 때 첫 번째 값으로
- 피벗을 제외한 리스트는 두 번째 원소부터 마지막 원소까지 모든 원소를 하나의 리스트로 만들어 tail변수에 담아
- 피벗을 제외한 리스트의 각 원소를 확인하면서 피벗보다 작은 경우 왼쪽 리스트에 담기게
- 피벗을 제외한 리스트의 각 원소를 확인하면서 피벗보다 큰 경우 오른쪽 리스트에 담기게
- 왼쪽 부분에 대해 퀵정렬 수행한 결과 리스트에
현재 피벗값을 붙이고
오른쪽 부분에 대해 퀵 정렬 수행한 결과 리스트를 붙임
- 전체 리스트는 모든 원소에 대해 정렬이 수행된 결과와 같다
👉🏻 정렬 알고리즘 비교하기
- 앞서 다룬 네 가지 정렬 알고리즘을 비교하면 다음과 같다
- 추가적으로 대부분의 프로그래밍 언어에서 지원하는 표준 정렬 라이브러리는 최악의 경우에도 O(NlogN)을 보장하도록 설계되어 있다
- 삽입 정렬은 일반적으로 선택 정렬에 비해서 조금 더 빠르게 동작한다
- 특히 데이터가 거의 정렬된 경우 O(N)으로 가장 빠르게 동작한다
- 퀵 정렬은 구현 방식에 따라 최악의 경우 시간 복잡도가 O(N²)이 나올 수 있다
- 문제에서 별도로 정렬함수를 구현하도록 요구하지 않는다면
일반적으로 정렬 기능을 위해서는 단순히 표준 정렬 라이브러리를 호출해서 정렬을 수행하는 것을 추천
💡 선택 정렬과 기본 정렬 라이브러리 수행 시간 비교
- 정렬을 수행시킬 목적으로 랜덤한 10,000개의 데이터 이용
- randint 활용
- 실행 시간을 측정하기 위해 알고리즘 밖에 start_time과 end_time이 선언되어있다
* 파이썬에서 기본적으로 제공하는 표준 정렬 라이브러리
- 병합 정렬과 삽입 정렬을 결합한 하이브리드 정렬 알고리즘(팀소트)을 사용하기 때문에
- 최악의 경우에도 O(NlogN)의 시간복잡도를 보장
- 선택 정렬과 비교해 1초보다도 짧은 시간에 정렬을 수행한다
(근데 0.0으로 나오는 게 맞는지는 모르겠다)
👉🏻 문제: 두 배열의 원소 교체
🧩 문제 설명
🧩 문제 조건
🧩 문제 해결 아이디어
💡 예시 답안
(그냥 a, b = b, a로 하면 되는 줄 몰랐네..)
* C++ ver
* Java ver
https://github.com/ndb796/python-for-coding-test/blob/master/6/12.java
출처: https://youtu.be/jpyslMwprao?si=3keO4Jc1AU9EuEC-
https://youtu.be/DRkL5EBZ7KY?si=KYJRK1bbGLZX5mkn
https://youtu.be/EuJSDghD4z8?si=UlYE-Q3wnXyIhrSR
https://youtu.be/_kdE7ykab4Q?si=Ll9qhnyXzzryf7e_