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)
-기본 아이디어
-> 버블 정렬과 비슷
-> 1등을 뽑아내고, 나머지 원소에서 1등을 계속 뽑아내면서 정렬
버블 정렬과 다른 점
-> 버블 정렬: 남은 원소에서 1등을 다시 비교를 통해서 찾는다.
-> 힙 정렬: 힙을 이용하면, 1등을 뽑아낸 뒤, 나머지 원소에서 1등을 뽑을 때 다시 비교할 필요 없이 2등이 자동으로 1등이 된다.
-> min heap 기준으로, 부모 노드에 2를 곱하면 왼쪽 자식 노드가 되고, 보모 노드에 2를 곱하고 1을 더하면 오른쪽 자식 노드가 된다.
루트 원소는 가장 큰 값(max heap)
-> 루트가 제거되면, 이 자리에 가장 마지막 원소를 옮김.
-> 이 원소와 원래 노드의 두 자식, 총 세 값을 비교
세 개의 노드중 가장 큰 노드가 올라가고, 이 과정을 계속 반복
-> 당장의 부모 노드와 비교해서, 내가 부모 노드보다 크면 부모를 내리고 내가 올라감. 아니면 밑에 있음.
-> 시간 복잡도: n log n
-> 일단 배열이 힙이라 생각하고 힙으로 만든 다음에, 힙을 하나씩 쪼개서 정리를 해나간다.
-> 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번을 함.
핵심 아이디어: 정렬될 데이터가 자릿수라는 개념이 있다면 이를 이용한다.
예를 들어, 정렬된 데이터가 택배 주소라면, 전체를 다 보지 않더라도 처음 위치를 보고 데이터를 분류할 수 있다.
주소지가 여러가지 있다고 가정하면, 같은 시끼리 모을 수 있음.
가장 좋은 경우
-> c개의 버킷으로 모든 원소가 균등하게 배분되어 각각 n/c개가 들어갔을 때
-> n/c개를 O(n/c log (n/c)) 시간에 정렬할 수 있고 ,이를 다시 합치면
-> c(n/c) log (n/c) = n(log n - log c)
가장 나쁜 경우
-> 하나의 버킷으로 모든 원소가 몰렸을 때
-> 이 경우는 버킷을 사용하지 않은 것과 같다
stalbe sorting 과 unstable sorting이 정확히 무엇이냐?
[출처] https://godgod732.tistory.com/10
기수 정렬의 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)
n개의 숫자를 정렬하는데 걸리는 시간은 O(n)
-> 각 숫자가 나온 횟수를 세는데 O(n)
-> 이는, 숫자들이 나올 수 있는 범위가 좁아서 O(1) 시간에 찾아갈 수 있기 때문
-> 다시 숫자를 정렬된 리스트에 채워넣는데 O(n)
만약 숫자들의 범위가 크다면?
-> 최대값 - 최소값 의 범위만큼 테이블이 필요하기 때문에, 숫자들의 편차가 너무 크면 안 좋음.
-> S가 숫자가 나온 횟수를 세는 테이블이라고 하면, 이 테이블을 다시 읽어야 하기 때문에 정확한 시간 복잡도는 O(n+|S|) 이다.
선택 문제를 푸는 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) 이다.