[알고리즘] 3강 - 정렬(1)

✅ 1. 정렬 기본 개념

(1) 정렬 이란?

• 정렬 수행 시점에 데이터가 어디에 저장되어 있는지에 따라 내부 정렬, 외부 정렬로 나뉨.
• 내부 정렬: 주기억장치에 전체 데이터를 저장한 후 정렬 하는 방식
• 외부 정렬: 보조기억장치에 전체 데이터 저장 후 일부 데이터만 주기억장치로 옮겨서 정렬하는 방식

(2) 내부 정렬 알고리즘

• 내부 정렬 알고리즘은 정렬 방식에 따라 비교 기반 알고리즘, 데이터 분포 기반 알고리즘 으로 나뉨.
• 비교 기반 알고리즘: 두 데이터의 값을 직접 비교하여 위치를 교환하는 방식이며, 일반적으로 많이 사용됨. ( 요소간의 비교 )
• ** 비교 기반 알고리즘 성능: 키값의 비교 횟수가 알고리즘 성능의 척도가 됨. **
• 데이터 분포 기반 알고리즘: 값들 간의 직접적인 비교를 하지 않고, 데이터의 특성(값의 범위, 자릿수 등)을 이용하여 데이터를 특정 버킷에 분산시킨 뒤 정렬하는 방식임.
• ** 쉽게 말해, 데이터 요소간의 비교가 아닌 미리 정의된 규칙에 따라(조건) 절대적인 위치를 찾아 정렬이 되는 방식임. **
• ** 데이터 분포 기반 알고리즘 성능: 데이터의 이동 횟수 **

(3) 정렬 관련 개념 - 안정적 정렬

• 안정적 정렬: "동일한 값" 데이터를 정렬 할 때, 정렬 전과 후에도 상대적 위치가 그대로 유지되는 정렬을 의미함.
• ** 대표적으로 삽입정렬, 거품정렬, 병합정렬이 있으며, 반면 불안정 정렬로는 선택정렬, 퀵정렬, 힙정렬이 있음. **

(4) 정렬 관련 개념 - 제자리 정렬

• 제자리 정렬: 주어진 데이터 더미 안에서 요스들의 위치만 바꿔가며 정렬을 하는 방식이며, 메모리 공간을 추가적으로 거의 사용을 하지 않음.
• ** 대표적으로 버블정렬, 선택정렬, 삽입정렬, 퀵정렬, 힙정렬이 있음. **

(5) 정렬 알고리즘의 기본 가정

• 해당 가정을 통해서 앞서 배울 정렬 방식을 설명 할 예정임.

---

✅ 2. 선택 정렬

(1) 선택 정렬 이란?

• 선택 정렬: 입력 배열에서 가장 작은 값부터 순서대로 선택해서 정렬하는 방식이다.
• ** 추가적인 배열은 사용하지 않고 입력 배열 내부에서 가장 작은값을 찾아서 맨 앞으로 옮기는 방식이라고 보면 됨. **

(2) 선택 정렬 - 처리 과정 (flow chart)

• (1) i < n - 1: 데이터의 개수만큼 반복 ( 즉, 배열의 크기만큼 반복한다고 보면되고 n 은 요소의 개수 n - 1 은 인덱스를 의미 )
• (2) 미정렬 배열을 순회하면서 최소값을 찾음.
• (3) 배열의 인덱스 제일 첫 번째 요소와 최소값과 자리를 바꿈.
• (4) 첫 번째 순회로 첫 인덱스는 제일 최소값을 가지는 정렬이 되게 됨.
• (5) 첫 번째 인덱스는 정렬이 되어있으므로, 다음 인덱스에 최소값을 또 넣으며 해당 과정을 반복

• 코드로써 구현은 2중 for 문을 활용을 함.
• 내부 for문: 배열의 모든 요소를 순회하며 최소값을 찾고 정렬 될 제일 작은 값을 첫 번째 인덱스와 위치를 교환을 해줌.
• 즉, 내부 for 문은 배열의 모든 요소를 순회하며 최소값을 하나만 찾아서 정렬을 해주는 하나의 단계라고 보면 됨.
• 외부 for문: 내부 for 문만 있으면 최소값 하나만 정렬을 해주기 때문에 배열의 인덱스 만큼 돌려서 모든 정렬을 수행해줌.
• ** 즉, 코드를 보면 가장 작은 값을 가지는 데이터의 위치인 j 를 min 변수에 담음으로써 위치를 기억해두었다가 반복문 한 사이클이 종료되는 시점에 해당 최소값 인덱스 번호를 통해 제일 첫 번째 인덱스 요소와 교환을 시킴. **

• 즉, 선택 정렬은 단계별로 최소값을 찾아서 교환을 해주고 교환 된 최소값은 건드리지 않고 다음 인덱스들에서 찾는 것임.
• ** 30과 20 = 20, 20과 40 = 20, 20과 35 = 5, 5와 10, 45, 50, 25, 15 = 5 이런식으로 진행됨 **

(3) 선택 정렬 - 성능과 특징

• 입력 데이터 n: 정렬 할 대상인 배열의 모든 요소들의 개수 ( 즉, 인덱스 )
• 시간 복잡도: 2중 for 문을 활용하기에 상수값을 제외한 n^2 의 시간복잡도를 가짐.

• 입력 데이터의 상태(배열 요소들의 비정렬 모습)와 상관없이 항상 동일한 성능인 O(n^2)을 가짐.
• ** 즉,입력 데이터인 비정렬 배열의 순서에 대해서 민감하지 않다는 의미임. **
• 제자리 정렬 알고리즘: 입력 배열 A[] 이외에 상수 개 저장 공간인 i, j, min, tmp 만 필요하기 때문에 제자리 정렬 알고리즘임.
• 불안정 정렬: 동일한 요소 값에 대해서도 위치를 바꿔주는 연산을 하기 때문에 불안정 정렬로 볼 수 있음.

---

✅ 3. 버블 정렬

(1) 버블 정렬 이란?

• 버블 정렬: 인접한 모든 두 데이터를 차례대로 비교 후 조건(크고 작은)에 따라 자리를 바꾸는 과정을 반복하는 정렬 방식임.
• 왼쪽에서 오른쪽 진행: 두 데이터 비교시 오른쪽 끝에 큰 값을 위치 시킴.
• 오른쪽에서 왼쪽 진행: 두 데이터 비교시 왼쪽 끝에 작은 값을 위치 시킴.

(2) 버블 정렬 - 처리 과정

• 왼쪽 그림: 오른쪽으로 비교를 시작하며, 더 큰 값을 오른쪽으로 정렬
• 오른쪽 그림: 왼쪽으로 비교를 시작하며, 더 작은 값을 왼쪽으로 정렬

• 외부 for문: 해당 배열의 요소 개수인 인덱스 수만큼 반복을 시켜줌.
• 내부 for문: 모든 요소를 순회 하며, 왼쪽 데이터와 오른쪽 데이터 비교 후 정렬을 반복함.
• i < n - 1: 반복 조건식은 n - 1 번 만큼만 도는데 그 이유는, 숫자 5개가 있다고 가정하면 4개의 위치를 다 찾아주면 자연스럽게 마지막 하나의 위치도 정렬이 된 상태이므로 굳이 한 번더 돌 필요가 없기 때문임.

오른쪽에서 왼쪽으로 이동하며 정렬하는 방식	왼쪽에서 오른쪽으로 이동하며 정렬하는 방식

• 2중 for 문 활용: 단계별로 왼쪽과 오른쪽 비교 후 정렬을 진행하며, 단계마다 비교시
• 오른쪽->왼쪽: 단계별로 왼쪽과 오른쪽 비교 후 큰 값과 작은 값을 비교 후 자리를 교환해주는데, 이때 오른쪽에는 더 큰 값이 가고 비교시점에 오른쪽 값이 더 크다면 교환을 할 필요가 없기에 다음 요소와 비교를 하는 과정을 반복함.

(3) 버블 정렬 - 성능과 특징

• 바깥쪽 반복문(i루프): 정렬을 총 몇 번 반복할지 결정함.
• 안쪽 반복문(j루프): 실제로 인접한 두 숫자를 비교하고 자리를 바꾸는 과정임.
• 시간 복잡도: 2중 for문 활용 -> 입력 데이터 n 증가율 최고차항 n^2 = O(n^2) 의 시간복잡도를 가짐.

• 안정적 정렬 알고리즘: 인접한 두 데이터가 동일한 경우에는 위치 교환을 하지 않으므로 안정적 정렬에 속함.
• 제자리 정렬 알고리즘: 입력 배열 A[] 이외에 상수 개의 저장 공간만 필요하므로 제자리 정렬로 볼 수 있음.
• 선택 정렬보다 비효율적: 선택 정렬은 배열의 데이터 전체를 훑으며 가장 작은 값을 가지는 인덱스의 번호를 변수에 저장해 둔 상태로 반복문 한 사이클을 돌고 난 뒤 마지막에 배열의 제일 첫 번째 요소와 최소값 인덱스 위치 요소와 위치를 교환해주기 때문에 한 사이클에 딱 한 번 위치 교환이 일어남.
• 하지만, 그에 비해 버블 정렬은 한 사이클 내에서 여러 번 요소간 위치를 교환해주기 때문에 데이터 교환이 많이 발생함.

(4) 버블 정렬 - 개선된 버블 정렬

• 처리 단계의 수: 기존 버블 정렬의 경우 이미 모두 정렬된 경우에도 반복문 횟수에 맞게 수행이 되다 보니 비효율적임.
• 인접한 두 데이터의 비교 횟수: 기존 버블 정렬의 경우 인접한 두 데이터를 반복문 횟수에 맞게 비교를 하다 보니, 이미 정렬된 데이터가 존재한다고 해도 모든 배열의 요소를 확인하는 작업을 하게 되므로 비효율적임.
•  **이러한 개선이 필요한 부분이 존재함. **

• (n - 1) - i: 반복 횟수에 - i 를 하는 이유는, 한 바퀴 돌 때마다 맨 뒤의 i개는 이미 완벽하게 정렬이 된 상태이므로 굳이 또 비교할 필요가 없기 때문에 단계별 반복마다 i 만큼 줄게 만드는 것임.
• Sorted = TRUE: TRUE 값으로 초기화를 시켜주며, 자리바꿈이 발생해 FALSE인 상태로만 돈다면 이상하기 때문임.
• Sorted = FALSE: 버블 정렬 데이터간의 비교 중에 자리 바꿈이 일어나면 Sorted 상태를 FALSE(미정렬 상태)로 바꿈.
• if (Sorted == TRUE) break: 루프를 다 돌았는데 자리가 단 한 번도 안바뀌었다면 그건 이미 완벽하게 정렬이 되었다는 것이므로, Sorted 에는 TRUE가 든 상태임을 알 수 있음. ( 더 이상 반복을 할 필요가 없기에 break 됨. )

• 시간 복잡도: O(n^2) 이지만, 입력 데이터의 상태에 따라서 성능이 달라짐.
• 쉽게 말해, 데이터가 역순으로 정렬된 경우 모든 비교를 다 하고 난 뒤 종료가 되지만, 원하는 순서로 이미 정렬이 된 경우에는 개선된 버블 정렬 조건에 따라 반복이 바로 종료가 될 수 있음 이때 최선의 경우 시간복잡도 O(n) 이 될 수 있음.

---

✅ 4. 삽입 정렬

(1) 삽입 정렬 이란?

• 삽입 정렬: 입력 배열을 정렬 부분과 미정렬 부분으로 구분해서 처리하는데, 이때 데이터를 하나씩 뽑아서 입력 배열에 삽입함.

• (1) 제일 첫 번째 요소는 정렬 부분으로 간주한다.
• (2) 첫 번째 요소 다음 요소를 왼쪽 정렬 부분과 비교 후 삽입 ( 현재는 5밖에 없으니 5와 비교 후 작으니 앞으로 3 삽입 )
• (3) 다음 비정렬 부분 맨 앞 8을 정렬 부분인 3, 5를 비교 하는데 둘 보다 크기 때문에 제자리에 있음.
• (4) 현재 상태는 정렬 부분(3, 5, 8) / 비정렬 부분(1, 2, 7) 이렇게 되어있으며, 이러한 과정을 반복하는 정렬 방식임.

• val = A[i]: 미정렬 부분의 첫 번째 데이터를 val 변수에 할당하는 연산임.
• for(j=i; j > 0 && A[j-1] > val; j--): i 의 값은 현재 미정렬 부분의 첫 번째 원소를 가리키고 있기 때문에 A[j-1] 을 통해서 미정렬의 마지막 부분의 값을 비교 할 수 있음.
• 또한, 만약 미정렬 부분의 마지막 인덱스 부분이 더 크다면 j-- 를 통해 그 이전 미정렬 부분 인덱스를 비교 할 수 있음.
• A[j] = A[j-1]: 정렬 부분의 데이터를 미정렬 부분의 제일 첫 번째 인덱스로 이동 즉, 덮어씌움. ( val 에 저장되어있음 )
• A[j] = val: 기존에 미정렬 첫 번째 데이터를 val 에 저장을 해두었으므로 val 값을 A[j] 에 삽입 ( 즉, 교환 된 것이 됨. )
• ** 이러한 과정을 반복하는 것이 삽입 정렬임. **

(2) 삽입 정렬 - 예시

• 위의 코드를 동작시키면 위와 같이 그림의 형태로 표현이 가능함.
• 1단계: 제일 첫 번째 요소인 30을 정렬부분으로 정해놓고, 미정렬 첫 번째 인덱스인 20과 비교 후 삽입 정렬
• 2단계: 미정렬 부분 첫 번째 40과 정렬 부분 30과 비교 후 30이 작으므로, 제자리에 있게 됨.
• 3단계: 35와 40을 비교 40이 더 크기 때문에 40이 35의 자리를 차지하게 되며, 35는 또 30과 비교를 하게 되며, 30보다는 크기 때문에 기존의 40이 있던 자리를 차지하는 원리임.
• ** 이러한 과정을 반복하는데 여기서 핵심은 정렬 부분의 데이터가 먼저 이동을 해서 삽입이 되며, 삽입이 되어 덮어씌워진 데이터는 기존의 변수에 저장을 해두었다가 정렬 부분과 비교를 다 끝마치면 해당 자리를 찾아서 삽입되어 정렬되는 방식임. **

(3) 삽입 정렬 - 성능과 특징

• 시간복잡도: O(n^2)
• 2중 for 문: 2번 반복문을 돌리는데 루프 j의 경우도 최대 n-1 번까지 비교를 할 수 있음. 즉 O(n^2)의 시간복잡도를 가짐.
• 또한, 부등호만 변경해주면 오름차순이 아닌 내림차순으로도 정렬이 가능함.

• 안정적인 정렬 알고리즘: 삽입 정렬의 경우 인접한 두 데이터가 정렬된 상태면 위치 교환을 하지 않음.
• 이유는, 정렬 부분과 비정렬 부분간의 비교를 통해서 정렬이 되기 때문임.
• 입력 데이터의 원래 순서에 민감: 쉽게 말해, 입력데이터가 정렬된 상태로 주어진다면 O(n) 의 시간복잡도를 가질 수 있으며, 그렇지 않고 역순으로 주어지는 최악의 경우 O(n^2) 의 시간복잡도를 가지게 됨.

• 역순으로 주어지는 경우(최악) O(n^2), 제순서대로 주어진 경우(최선) O(n) 이 된다.

---

✅ 5. 셸 정렬

(1) 셸 정렬 이란?

• 셸 정렬: 삽입 정렬의 장점은 살리고 단점은 보완한 방식의 정렬임.
• 삽입 정렬 단점: 미정렬 부분의 데이터를 정렬 부분에 삽입하는 과정에서 두 데이터의 대소 비교를 통해서 제자리를 찾아가는데 이때 제자리가 멀더라도 한 자리씩만 이동해서 찾아가야하는 단점이 있음.

삽입 정렬의 문제
- [9,1,2,3,4,5,6,7,8]

(삽입정렬 과정)
- 1 → 9 앞
- 2 → 9 앞
- 3 → 9 앞
...

- 9가 뒤로 가기 위해: 9 → 8칸 이동

• 즉, 이와 같이 멀리 떨어진 값 이동이 매우 비효율적이며, 시간복잡도가 O(n^2) 이 될 가능성이 높은 단점이 있음.
• 셸 정렬: 이러한 삽입 정렬의 단점을 보완하고자 입력 배열을 부분 배열로 나누어 부분 배열간 비교 및 교환(삽입 정렬)을 통해서 정렬을 하는 방식이기 때문에 멀리 떨어져 있는 원소도 한 번에 이동시킬 수 있어 삽입 정렬보다 효율적인 정렬이 가능함.
•  ** 또한, 부분배열은 조건문과 반복문을 통해서 부분배열이 존재하는 것처럼 보이는 논리적인 존재이다. **

<< 셸 정렬 >>
[16,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]: n = 16

( 1단계 비교: gap = n(16) / 2 = 8 )
- index 간격: gap(8)인 그룹 생성 = 8 group
- [16,1,2,3,4,5,6,7],[8,9,10,11,12,13,14,15] => 16, 9 비교 교환 ...
- Group 1:[16, 8], Group 2:[1, 9] ... Group 8:[7, 15] ( 총 8개 그룹 )
- 총 8개의 각 그룹에서 삽입 정렬 수행
- 1단계 결과: [8,1,2,3,4,5,6,7,16,9,10,11,12,13,14,15]

( 2단계 비교: gap = 8 / 2 = 4 )
- index 간격: gap(4)인 그룹 생성 = 4 group
- Group 1: [8,4,16,12] → [4,8,12,16]
- Group 2: [1,5,9,13] → 변화 없음
- Group 3: [2,6,10,14] → 변화 없음
- Group 4: [3,7,11,15] → 변화 없음
- 2단계 결과: [4,1,2,3,8,5,6,7,12,9,10,11,16,13,14,15]

( 3단계 비교: gap = 4 / 2 = 2 )
- index 간격: gap(2)인 그룹 생성 = 2 group
- Group 1: [4,2,8,6,12,10,16,14] → [2,4,6,8,10,12,14,16]
- Group 2: [1,3,5,7,9,11,13,15] → [1,3,5,7,9,11,13,15]
- 3단계 결과: [2,1,4,3,6,5,8,7,10,9,12,11,14,13,16,15]

( 4단계 비교: gap = 2 / 2 = 1 )
- 일반 삽입 정렬 수행 -> 이전 1~3단계는 간격(gap)이 있는 삽입 정렬임.
- 4단계 결과: [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16]

• 결론: 마지막 단계를 제외한 모든 단계에서는 간격(gap)이 있는 삽입 정렬을 진행하며, 마지막 gap = 1 단계에서는 일반 삽입 정렬을 진행한다. 또한, gap = 1 단계에서 삽입 정렬을 하면 배열의 모든 요소는 무조건 정렬이 됨.
• 또한, 부분배열의 각 거리간 비교를 통해서 멀리 떨어진 값간의 비교를 함.

(2) 셸 정렬 알고리즘

• D: 부분 배열의 개수(간격의 크기)를 의미하며, 나누기 2를 하면서 간격을 점차 줄이는 반복문임.
• 2중 for문: 부분 배열의 크기만큼 반복해서 돌리면서 부분배열에 대한 삽입 정렬을 진행하는 역할을 함.

def shellSort(A):
    n = len(A)
    D = n // 2 # 버림 나눗셈
    while D >= 1:
        for i in range(D, n): # D ~ n 까지 반복
            val = A[i] # 8번째 인덱스의 값을 넣어줄듯.
            j = i

            while j >= D and A[j - D] > val:
                A[j] = A[j - D]
                j -= D # 8 - 8 = 0

            A[j] = val
        D //= 2
            
A = [16,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]
shellSort(A)
print("정렬 결과:", A)

• 셸 정렬을 파이썬 코드로 하면 위와 같은 코드로 구현이 가능함.

(3) 셸 정렬 예시

• 2로 반복적으로 부분배열을 논리적인 단위인 거리로 나누게 됨.
• 이후, 내부 for 문을 통해서 반복적으로 비교 후 부분 정렬을 진행함.

(4) 셸 정렬 특징

• 어떤 순열을 사용하느냐에 따라서 성능이 달라지며, 가장 좋은 간격을 찾는 것은 미해결 과제임.
• 쉽게 말해, 정렬되지 않은 배열은 수학적으로 하나의 순열로 보며, 해당 순열의 성능 척도는 역전의 개수로 볼 수 있으며, 해당 역전은 [3, 1, 2] 라는 순열에서 (3, 1) 과 (3, 2)는 순서가 뒤집혀 있으므로 역전으로 보는 것이다.
• ** 일반적인 삽입 정렬은 인접한 값끼리만 비교해서 이 역전을 한 번에 하나씩만 제거를 하기 때문에 매우 느림 **
• ** 하지만, 셸 정렬은 D만큼 떨어진 값들을 비교함으로써, 한 번의 이동으로 수많은 역전 관계를 동시에 해결을 함. **
• ** 즉, 순열의 상태를 아주 빠르게 정렬에 가까운 상태로 바꿔주는 것임. **
• 시간복잡도: 최선 O(nlogn) / 최악 O(n^2)

• 제자리 정렬 알고리즘: 셸 정렬은 추가적인 메모리 공간을 사용하지 않고, 제자리에서 이동을 함.
• 안정적이지 않은 정렬 알고리즘: 삽입정렬의 경우 하나씩 비교를 하면서 제자리를 찾아가기 때문에 같은 수끼리의 위치는 변하지 않지만, 셸 정렬은 멀리 떨어진 값과 비교를 하기 때문에 같은 값끼리 순서가 뒤섞일 수 있음.