2025.03.16

TIL(TODAY I LEARN)

---

WEEK01 :
배열, 문자열, 반복문과 재귀 함수, 복잡도(BigO,시간,공간), 정렬, 완전 탐색, 정수론

자료구조와 함계 배우는 알고리즘 입문 책과 함께이론을 다시 해보자😊
어제에 이어서 공부를 계속 해보자

📖 6. 정렬 알고리즘

---

정렬 알고리즘의 핵심은 교환, 선택, 삽입

정렬 알고리즘의 안정성

• 안정적인(stable) 알고리즘 / 불안정한(unstable) 알고리즘
  값이 같은 원소의 순서가 정렬한 후에도 유지되는 것 / 유지되지 않는 것

버블 정렬(Bubble sort)

• 이웃하는 원소를 비교해 교환하면서 정렬
• stable sort
• O(n^2) 시간복잡도를 가짐

a = [3,2,5,1]

for i in range(len(a)-1):
    for j in range(i+1,len(a)):
        if a[i] > a[j]:
            a[i], a[j] = a[j], a[i]
         
print(a)
>>>[1, 2, 3, 5]

• 버블 정렬의 개선

1. 이미 정렬을 마친 상태라면 그 이후의 패스는 원소 교환을 하지않음
2. 각각 패스에서 비교, 교환을 하다가 어떤 특정한 원소 이후에 교환하지 않는다면 그 앞쪽 원소는 이미 정렬 된 것

• 셰이커 정렬(shaker sort)

[9,1,3,4,6,7,8] <- 거의 정렬이 완료된 상태
- 9만 뒤로가면 정렬이 끝남
- 그래서 정렬을 앞뒤로 한번씩 번갈아 수행하면서 작업 속도를 향상시킬 수 있음

단순 선택 정렬(straight selection sort)

• 배열에서 가장 작은(큰) 수를 선택해 맨 앞의 수와 교환
• 이미 정렬된 배열을 제외한 나머지 배열에서 위를 반복
• unstable sort
• O(n^2) 시간복잡도를 가짐

def selection(a: list):
    for i in range(len(a)-1):
        j = a.index(min(a[i+1:]))
        if a[i] > a[j]:
            temp = a[j]
            a[j] = a[i]
            a[i] = temp
            
selection(a)
print(a)

단순 삽입 정렬(stragiht insertion sort)

• 선택 정렬과 비슷해보이지만 다름
• 정렬된 배열 / 정렬되지 않은 배열 <- 형태를 가짐
• 정렬되지 않은 배열의 맨앞에서 수를 꺼내 이미 정렬된 배열에 삽입시킴.
• stable sort
• O(n^2) 시간복잡도를 가짐

def insertion(a):
    for i in range(1,len(a)): #정렬 안된 배열에서 하나씩 뽑음
        for j in range(i,0,-1):
            if a[j-1] > a[j]:
               a[j-1], a[j] = a[j], a[j-1]
insertion(a)
print(a)

셸 정렬(shell sort)

• 단순 삽입 정렬을 보완한 정렬 방법
  *멀리 떨어진 요소들을 먼저 비교 및 교환하면서 간격을 점차 줄여나감
• unstable sort
• 최악의 경우 O(n^2) 시간복잡도를 가짐
• GAP을 우선 설정함(list 길이의 절반)
• GAP을 줄여나가며 삽입정렬을 수행

퀵 정렬(quick sort)

• 피벗을 정해서 좌우로 피벗보다 작은 / 큰 배열로 나눔
• 큰 문제를 작은 문제로 분할해서 정렬
• unstable sort
• O(nlogn) 최악의 경우 O(n^2)
• 피벗을 잘 선택하는 것이 코드에 영향을 많이 줌

병합 정렬(merge sort)

• 배열 앞, 뒤 부분으로 나누어 각각 정렬한후 병합을실시
• 병합을 진행할 때 각각의 부분 배열에서 원소값의 대소비교를 진행하면서 병합
• 새로운 저장공간(buff)가 필요함. 공간 복잡도에서 불리
• stable sort
• O(nlongn)

힙 정렬(heap sort)

• heap - 부모의 값이 자식 노드의 값보다 항상 크거나 작은 완전 이진 트리

• 힙은 1차원 배열로 표현이 가능함. 최댓값은 항상 루트에 존재한다(max_heap)
  

부모 = a[(i-1)//2]
왼쪽 자식 = a[i*2+1]
오른쪽 자식 = a[i*2 + 2]

• 배열을 힙으로 만든 뒤 루트 노드를 계속 빼내서 정렬된 배열을 만드는 방법
• 힙에서 최대값을 빼내는건 O(n), 힙을 재생성하는 과정이 O(logn)
• unstable sort
• O(nlongn)

도수 정렬(counting sort)

• 입력 배열의 원소값의 범위를 알 때 나타나는 빈도의 누적합을 이용해 정렬을 하는 방법
• 중복값이 있을 수 있기 때문에 수 하나를 처리할때 누적합에서 -1 필요
• 입력 배열에서 역순으로 조회를 하면서 정렬을 해야함
• stable sort
• O(n + k)

	n = 입력 데이터의 개수 (리스트 길이)
	k = 값의 범위 (가장 큰 값)

매번 sort() 쓰다가 정렬 직접하려니 힘들다.