Algorithm_Week_5

퀵 정렬 시간 분석

• 가장 좋을 때: 기준의 왼쪽, 오른쪽에 같은 수의 원소가 이동함
  -> T(n) = 2T(n/2) + n
  -> T(n) = O(n log n)
• 가장 나쁜 경우: 기준의 왼쪽 또는 오른쪽 한 쪽으로만 원소가 쏠림
  -> T(n) = T(n-1) + n
  -> T(n) = O(n^2)
• 평균적인 경우: 복잡
  -> 다음과 같은 극단적인 경우에도 T(n) = O(n log n)
  -> T(n) = T(99n/100) + T(n/100) + n
  -> 기준을 첫 번째 원소가 아니라 랜덤으로 고름

import random

def randomizedquicksort(L):
   if (len(L) == 1) or (len(L) == 0):
      return L
   pivot = int(random.random() * len(L))
   # 0~1 사이의 실수에다가 배열의 길이만큼 곱해주고, 정수를 취함.
   left = []
   right = []
   for x in L[:pivot]+L[pivot+1:]:
      if (x < L[pivot]):
         left.append(x)
      else:
         right.append(x)
   return randomizedquicksort(left) + [L[pivot]] + randomizedquicksort(right)

힙 정렬(Heapsort)

-기본 아이디어
-> 버블 정렬과 비슷
-> 1등을 뽑아내고, 나머지 원소에서 1등을 계속 뽑아내면서 정렬

• 버블 정렬과 다른 점
  -> 버블 정렬: 남은 원소에서 1등을 다시 비교를 통해서 찾는다.
  -> 힙 정렬: 힙을 이용하면, 1등을 뽑아낸 뒤, 나머지 원소에서 1등을 뽑을 때 다시 비교할 필요 없이 2등이 자동으로 1등이 된다.
  -> min heap 기준으로, 부모 노드에 2를 곱하면 왼쪽 자식 노드가 되고, 보모 노드에 2를 곱하고 1을 더하면 오른쪽 자식 노드가 된다.

• 루트 원소는 가장 큰 값(max heap)
  -> 루트가 제거되면, 이 자리에 가장 마지막 원소를 옮김.
  -> 이 원소와 원래 노드의 두 자식, 총 세 값을 비교

• 세 개의 노드중 가장 큰 노드가 올라가고, 이 과정을 계속 반복

힙을 만드는 방법 1

-> 당장의 부모 노드와 비교해서, 내가 부모 노드보다 크면 부모를 내리고 내가 올라감. 아니면 밑에 있음.
-> 시간 복잡도: n log n

힙을 만드는 방법 2

-> 일단 배열이 힙이라 생각하고 힙으로 만든 다음에, 힙을 하나씩 쪼개서 정리를 해나간다.

Heapsort in C++ 11

-> STL이라는 도구가 얼마나 강력한지 보여줌.

#include <iostream>
#include <algorithm>
#include <array>
int main()
{
   std::array<int, 6> v = {3, 1, 4, 1, 5, 9}; // C array의 wrapper
   std::make_heap(v.begin(), v.end()); // v의 시작부터 끝까지 원소로 힙을 만든다. ㄹㅇ 개 쩐다. 
   //여기서 v.end는 실제로 마지막 '다음' 칸임.
   
   for (auto i : v) // v의 원소 하나하나를 i로 줌. 파이썬이랑 비슷함. auto는 변수의 형태를 자동으로 추정. 
 
      std::cout << i << ' ';
      
   std::cout << '\n';
   
   for (auto last = v.end(); last != v.begin(); last--)
      std::pop_heap(v.begin(), last); // 루트 원소를 last 위치로 이동
      //pop_heap은 호출될 시, 부모노드를 맨 마지막 자식노드인 end와 교환하고 부모노드를 재정렬 한다.
      //이때 거꾸로 차곡차곡 쌓이기 시작한다. 약간 뭔가 조금 뒤죽박죽이었던 것을 내림차순 혹은 오름차순
      //으로 다시 정렬하는 느낌..?
   for (auto i : v)
      std::cout << i << ' ';
      
   std::cout << '\n';
   return 0;

비교에 기반한 정렬의 시간 복잡도 한계

-> 원소 3개를 비교하는 과정에서 운좋으면 2번, 나쁘면 총 3번을 함.

• 위 트리(?)는 이진 트리임(2개를 계속해서 비교해 나가는 형식이기 때문에)
• 트리의 리프 수 L은 n개의 값을 정렬하는 모든 경우를 포함한다.(여기 무슨 소린지 모르겠음. 하나도)
• 따라서, 두 원소의 비교에 기반한 정렬 알고리즘은 Ω(n log n) 보다 빠르게 동작할 수 없다.

비교에 기반하지 않은 정렬: 버킷 정렬(bucket sort)

• 핵심 아이디어: 정렬될 데이터가 자릿수라는 개념이 있다면 이를 이용한다.

• 예를 들어, 정렬된 데이터가 택배 주소라면, 전체를 다 보지 않더라도 처음 위치를 보고 데이터를 분류할 수 있다.

• 주소지가 여러가지 있다고 가정하면, 같은 시끼리 모을 수 있음.

• 가장 좋은 경우
  -> c개의 버킷으로 모든 원소가 균등하게 배분되어 각각 n/c개가 들어갔을 때
  -> n/c개를 O(n/c log (n/c)) 시간에 정렬할 수 있고 ,이를 다시 합치면
  -> c(n/c) log (n/c) = n(log n - log c)

• 가장 나쁜 경우
  -> 하나의 버킷으로 모든 원소가 몰렸을 때
  -> 이 경우는 버킷을 사용하지 않은 것과 같다

"stable" sorting

• 둘 이상의 키로 이루어진 데이터를 정렬할 때, 동점이 있을 때 발생하는 문제
  -> 어떤 정렬은 성립하고, 어떤 정렬은 성립하지 않음.
  -> 만약 한 키에대해 겹쳐서, 우선 1차적으로 정렬이 되었을 경우, 다른 키에 대해 2차적으로 정렬을 해야함.
  -> 최종 정렬 결과는 일정해야함.
  -> 나중에 정렬한 결과가, 먼저 정렬한 결과를 바꾸면 안됨.

stalbe sorting 과 unstable sorting이 정확히 무엇이냐?

[출처] https://godgod732.tistory.com/10

정렬 방법과 stable 여부

• 퀵 정렬
  -> 만약 기준이 두개 이상인데 동점이 있을 경우, 정렬 기준과 원래 원소의 위치를 고려해야 함. => stable
• 버블 정렬
  -> stalbe. Why? => 버블 정렬은 어차피 동점일 때 순서를 서로 바꾸지 않으니까
• 삽입 정렬
  -> stable. Why? => 버블 정렬과 비슷한 논리
• 힙 정렬
  -> stble 하지 않음.
  -> 힙을 만드는 순간, 입력받았던 원소의 순서가 파괴됨.

기수 정렬(radix sort)

• 완전히 비교를 제외한 정렬 방법
• 낮은 자리에서 높은 자리로 기준을 바꾸어 가면서 정렬
• ex) 일의 자리로 정렬하고, 십의 자리로 정렬하고, 백의 자리로 정렬함.

기수 정렬의 python 구현

import math

def radixsort(L):
   temp = list(L) #배열 L 복사
   for x in range(int(math.log(max(L), 10))+1): #배열 L에 있는 가장 큰 수의 자리수를 얻을 수 있음
      bucket = [[] for _ in range(10)]# 길이가 0인 리스트 10개 생성
      for l in temp:
         digit = (l % int(math.pow(10, x+1))) / int(math.pow(10,x))
         bucket[digit].append(l)
      temp = []
      for i in range(len(bucket)):
         temp = temp + bucket[i]
         bucket[i] = []
      return temp
>>> X = [153, 262, 37, 598, 433, 855]
>>> print radixsort(X)

계수 정렬(counting sort)

• 비교에 기반하지 않는 또다른 정렬
• 실제로는 굉장히 유용한 정렬
  -> 범위가 좁은 수들이 굉장히 많을 때 유용
• 범위가 작은 수들을 빠르게 정렬
  -> a. 각 수가 나온 횟수를 센다.
  -> b. a의 결과를 이용하여 각 수보다 작은 숫자가 몇 개 있는지 센다.
  -> a 와 b 를 둘 다 해주는 이유는, 정렬된 값도 알고 싶고, 그 값들이 몇 등인지 빠르게 알고 싶어서 이다. 물론 a만 해줘도 등수를 알 수 있긴한데, 누적값들을 따로 계산해줘야되는 작업이 필요할 뿐이다. 예를들어 수학성적이 40점인 사람이 2만명있다고 치면, 2만명을 다 셀 수는 없는 노릇이니..

계수 정렬: 분석

• n개의 숫자를 정렬하는데 걸리는 시간은 O(n)
  -> 각 숫자가 나온 횟수를 세는데 O(n)
  -> 이는, 숫자들이 나올 수 있는 범위가 좁아서 O(1) 시간에 찾아갈 수 있기 때문
  -> 다시 숫자를 정렬된 리스트에 채워넣는데 O(n)

• 만약 숫자들의 범위가 크다면?
  -> 최대값 - 최소값 의 범위만큼 테이블이 필요하기 때문에, 숫자들의 편차가 너무 크면 안 좋음.
  -> S가 숫자가 나온 횟수를 세는 테이블이라고 하면, 이 테이블을 다시 읽어야 하기 때문에 정확한 시간 복잡도는 O(n+|S|) 이다.

선택 문제

• 주어진 n개의 원소중에서, 크기 순으로 k번째 원소를 찾는 문제
• 해법
  -> 원소를 크기 순으로 정렬하면 바로 풀 수 있다.
  -> 하지만, 나는 모든 원소를 정렬하지 않고 이 문제를 풀고 싶다.

퀵 정렬의 응용

• 퀵 정렬에서, 항상 한 기준 원소의 등수가 결정됨
  -> 기준의 등수가 k등일 때: 기준이 원하는 답
  -> 기준의 등수가 k보다 클 때: 기준보다 작은 원소들 중에서 k등을 고르면 된다.
  -> 기준의 등수가 k보다 작을 때: 기준보다 작은 원소들이 a개 있다면, 기준보다 큰 원소들 중에서 k-(a+1) 등을 고르면 됨

선택 문제를 푸는 python 코드

def selectk(L, k):
   if (len(L) == 1):
      return L[0]
   pivot = L[0]
   left = []
   right = []
   for x in L[1:]:
      if (x < pivot):
         left.append(x)
      else:
         right.append(x)
   if (len(left) == k-1):
   # 왜 k-1 이냐면, return 값으로 pivot를 줄 것이기 때문에, k-1이어야 함. 
      return pivot
   elif (len(left) >= k):
      return selectk(left, k)
   else:
      return selectk(right, k-(len(left)+1))
      # left 배열에있는 원소 개수 + pivot 까지 포함이니 까 k-(len(left)+1) 이다.

• 시간 복잡도
  -> 기준값에 의해서 어떻게 범위가 나누어짐에 따라 다름
  -> 가장 좋을 때: T(n) = T(n/2) + n => 양쪽중 하나만 선택하므로
  -> 가장 나쁠 떄: T(n) = O(n^2)
  -> 극단적인 경우에도: T(1) + 100n = O(n) 맨 끝쪽에 있다고 가정 할 때 => 잘 모르겠음