Python/이것이코딩테스트다with파이썬

21~25강:: 정렬 알고리즘

묘걍 2023. 12. 5. 21:17

👉🏻 정렬 알고리즘

  • 정렬(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에 비례하는 만큼 발생할 것을 기대

더보기

이상적인 경우에서는 피벗을 선택할 때마다 정확히 중간에 위치한 경우가 가장 이상적입니다. 이렇게 되면 분할이 정확히 절반으로 이루어집니다. 이 때의 시간 복잡도를 알아보겠습니다.

  1. 첫 번째 분할: N개의 원소를 가진 배열을 피벗을 기준으로 두 부분으로 나누면, 각 부분은 약 N/2개의 원소를 가집니다.
  2. 두 번째 분할: 각 부분을 다시 피벗을 기준으로 나누면, 각 부분은 약 N/4개의 원소를 가집니다.
  3. 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_