이진 삽입 정렬
단순 삽입 정렬은, 배열 원소수가 많아지면
원소 삽입에 필요한 비교, 교환 비용이 커진다.
그러나 이진 검색법을 사용하여 삽입정렬을 하면,
이미 정렬을 마친 배열을 제외하고 원소를 삽입해야할 위치를 검사...
...
이를 binary insertion sort, 이진 삽입 정렬이라고한다.
일단 잘 이해가 안 가는군
아무래도 앞부분 정렬을 검색하는데,
사실 앞부분?은 이미 정렬되어있는 거니까,
이진 탐색법으로 삽입 정렬을 하면 편하다는 말 같은데.
하...
뼈빠지게 구현해봄..
n = len(a)
pl= 1
pr= 1
pc = 1
for i in range(n):
temp = a[i]
while pr != n and temp < a[pc]:
pr = pc
pc = (pl+pr)//2
...
그래서 elif로 temp>a[pc]인 조건이랑,
temp와 값이 일치하는 조건을 넣어서 반복하는 문이었음.
헷갈려도...울지마세요
시간없어요..
여기 정답코드에서는
인덱스를 항상 갱신시켜주기 위해 for문으로 pl, pr, key를 n으로 뽑아서 반복시킨 다음,
while 문으로 뽑아서 일치하는 값을 찾을 때까지 반복시키고,
찾고 나면 삽입해야할 위치의 인덱스를, 반복시켜서 얻은 pl, pr, pc 값으로 만들어준다음,
인덱스를 찾았으니 일일이 거기서부터 목표지점까지 하나씩 옮겨주고 최종 목적지에 key값을 넣어줌.
난 또 목적지 찾으면 또 바로 그 값을 대입시켜주려고했군...
마지막 부분은 생각 못했어...
나보고 한 번 더 써보라고하면..
쓸...수있을까...
울면서 써본 것
for i in range(n):
pl = i
pr = n-1
key = a[i]
while True :
pc = (pl+pr)//2
if key == a[pc]:
break
elif key >= a[pc]:
pl = pc
else:
pr =pc
pd = pc + 1 if?
for j in range(pd, i, -1):
a[j] = a[j-1]
a[pd] = key
틀린 것 :
1. pl과 pr은 정렬된 부분 범위이기때문에
0부터 i-1까지다.
- 그 외에 조건에 따라
pl = pc +1
pr = pc -1 이어야함.
- 그러다 if 뒤에 나오는건,
pl은 더해지고, pr은 빼지기 때문에,
완전히 일치하는 값이 없으면
둘의 위치가 뒤바뀔 때가 나옴.
그 때는 pc로 지정해주지 않고,
pr+1로 인덱스를 지정해준다.
- 마지막에 밀 때 i번째부터 pd까지 역순으로 하는거라서 range(i, pd, -1)이다.
한 시간이 걸렸고
한 게 낫긴한데(어제의 나보다...어쩌고.)
할..필요가 있었나? 싶기도.
그렇지만 이진 탐색할때 그 값이 없으면
pl과 pr의 자리가 뒤바뀌는 점..
그리고 새로 할때마다 pl과 pr 범위 지정을 해줘야한다는 점..을 생각하면
의미 있었는듯!
? 단순 삽입 정렬 알고리즘, bisect 모듈의 insort() 함수.
for i in range(1, len(a):
bisect.insort(a, a.pop(i), 0, i)로 넣으면 된다.
a라는 리스트에서, i를 넣을 건데,
0부터 i사이에 넣을 거다.
라는 뜻.
셸 정렬(shell sort)
단순 삽입 정렬의 장점은 살리고,
단점은 보완하여 더 빠르게 정렬하는 알고리즘.
단순 삽입 정렬의 장점과 단점은 이렇다.
- 장점 : 이미 정렬을 마쳤거나, 거의 끝나가는 상태에서는 속도가 아주 빠르다.
- 단점 : 삽입할 위치가 멀리 떨어져있으면 이동 횟수가 많아진다.
예를 들어, 맨 끝에 0이 있다면,
앞이 다 정렬되어있더라도, 앞으로 오기까지 계속 갱신해야할 것이다.
셸 정렬 알아보기
셸 정렬은 먼저 정렬할 배열의 원소를 그룹으로 나눠,
각 그룹별로 정렬을 수행한다.
그 후 정렬된 그룹을 합치는 작업을 반복하여,
원소의 이동 횟수를 줄인다.
일단,'4-정렬'을 한다.
4개 떨어진 원소를 비교하여, 정렬을 시켜준다.
그 다음, 2칸 떨어진 원소를 모두 꺼내
두 그룹으로 나누고, '2-정렬'을 수행한다.
그리고 마지막으로 '1-정렬'을 수행한다.
즉, 배열 전체를 대상으로 적용하여 정렬을 끝내는 것이다.
이러한 셸 정렬 과정에서 수행하는 각각의 정렬을
h-정렬 이라고 한다.
h값을 4, 2, 1로 감소시키면서 정렬을 7번 수행하여 정렬을 완료하는 것이다.
4정렬과 2정렬 후 마지막으로 단순삽입 정렬을 하는 것이다.
정렬 횟수는 늘어나지만, 전체적으로 원소의 이동 횟수가 줄어들어 효율적이다.
원래의 단순 삽입 정렬과 거의 같은데
주목하는 원소와 비교하는 원소가 서로 이웃하지않고
h개만큼 떨어져있다고..
...
해봐야겠지..하습하..
def insert_sort(x:Any) -> None:
n = len(a)
for i in range(4,n):
j = i
tmp = a[i]
while j > 0 and a[j-4] < tmp:
a[j] = a[j-1]
j -= 1
a[j] = tmp
대단한 걸 틀린 건아니고..
아니 솔직히 말하면 모든 걸 틀린 거나 다름없지만
비교값만 바꿔주는게 아니라,
뒤바꾸는 값의 인덱스,
인덱스 증가량도 바꿔야한다.
그리고 따로 넣는 값을 주는게 아니다.(그냥 정렬이니까.)
리스트만 입력한다.
def shell_sort(a: MutableSequence) -> None:
n = len(a)
h = n //2
while h > 0:
for i in range(h,n):
j = i - h
tmp = a[i]
while j >= 0 and a[j] > tmp:
a[j + h] = a[j]
j -= h
a[j+h] = tmp
h // = 2
하아..
이해하느라 혼났네
while문 부터,
값이 왼쪽이 크면 왼쪽값을 오른쪽 자리에 복사해준뒤,
j -= h를 한다.
이게 뭐냐면, 만약 배열이 충분히 길다면,
여기서 한번 더 h칸 뒤로 가서,
일반적인 삽입 정렬처럼 옆의 값이 작은지 큰지 확인한 뒤 바꾼후 아무튼 끝까지 가서 멈추거나 왼쪽값이 충분히 작다면 멈추고,
우리가 저장해뒀던 값을 제일 앞에 넣어주는거다.
7빼주기
(7)
(6) 4칸 (8) 4칸 (7)
왼쪽이 크니까 값 옮기기
(7)
(6) 4칸 (8) 4칸 (8)
도달했으니까 넣어주기
(7)
(6) 4칸 (7) 4칸 (8칸)
그리고 h를 따로 빼서,
2분의 1값씩 진행하도록 while로 h>0으로 전체적으로 묶어주고, 계속 나눠서 0이 나오는 지점을 만들게 함..
그래서 정렬을 반복함! 끝!
h값 선택
어떤 수열로 감소 시켜야 효과적인 정렬을 할 수 있는가?
음...
배수면 나누어서 정렬했지만
충분히 그 기능을 못한다고 한다.
예시는 봤지만 잘 이해가 안 된다.
아무튼 배수를 쓰지 말라니까 뭐.(언젠간 알게 되겠지!)
1부터 시작하여 3배한 값에 1을 더하고 있지만,
h의 초깃값이 지나치게 크면 효과가 없으므로,
배열의 원소 수인 n을 9로 나누었을 때 그 몫을 넘지 않도록 해야한다.
for i in range(n//9):
h = i*3 +1인가?
h = 1
while h < n//9:
h = h*3 +1
똑같은 말인 듯...
대신 이걸 넣어주면 마지막으로 나눌때 2가 아니라 3으로 나눠줌!
그러면 h값이 1이 된다고.
셸 정렬의 시간 복잡도는 O(n**1.25)로 단순 정렬 시간 복잡도보다 매우 빠르다.
그러나 이웃하지 않고 떨어져있는 원소를 교환하므로,
안정적이지 않다.
퀵 정렬(quick sort)
알고리즘 정렬 속도가 매우 빠르다 하여 고안자가 붙인 이름.
피벗(pivot)을 설정하는데,
이는 그룹을 나누는 기준이다.
(예를 들어, 키 168cm인 학생을 기준으로 한다면,
168 이상, 168 미만으로 나눌 수 있을 것이다.
나눈 후 나눈 그룹에서도 피벗을 설정하며 나누다보면,
개개의 크기 정도로 나누어지고,
나누어지면서 정렬 된다.
모양은 이진 트리와 흡사하다)
배열을 두 그룹으로 나누기
피벗을 x, 왼쪽 끝 인덱스를 pl(왼쪽 커서),
오른쪽 끝 인덱스를 pr(오른쪽 커서),
라고 하자.
그룹을 나누려면,
피벗 이하인 원소를 배열 왼쪽으로,
피벗 이상인 원소를 배열 오른쪽으로 이동시켜야한다.
- a[pl] >= x 가 성립하는 원소를 찾을 때까지 pl을 오른쪽 방향으로 스캔합니다.
- a[pr] <= x 가 성립하는 원소를 찾을 때까지 pr을 왼쪽 방향으로 스캔합니다.
이 과정을 거치면,
pl은 피벗 이상인 원소에,
pr은 피벗 이하의 원소에 위치합니다.
그 다음 a[pl]과 a[pr]을 교환합니다.
그러면 피벗 이하 값은 왼쪽에, 피벗 이상 값은 오른쪽에 위치합니다.
그것을 반복하며 나아가다보면,
pl과 pr이 서로 교차합니다.
교차하면 그룹을 나누는 과정이 끝나고,
배열은 두 그룹으로 나뉩니다.
- 피벗 이하인 그룹 a[0] .... a[pl-1]
- 피벗 이상의 그룹 a[pr+1] ... a[n-1]
또 그룹을 나누는 작업이 끝난다음,
pl > pr +1 일 때에 한해서,
다음과 같은 그룹이 만들어집니다.
- 피벗과 일치하는 그룹 : a[pr+1] ... a[pr-1]
(이동해도, 같은 값이기때문에 교환하지 않는...
피벗과 일치하는 값의 그룹.)
이 과정에서
한번 pl > pr +1이 되기 직전,
pl = pr 이 되는 지점,
즉 피벗 위에 위치하게 되는 부분이 있다.
그래서 불필요하게 한번 교환한 다음에
pl > pr + 1이 되지만,
pl과 pr이 같은 위치인지 확인하는 것보다
한번 그냥 같은 값을 교환하는 게 나으므로 그대로 한다.
아무튼, 피벗이 일치하는 그룹이 만들어지면
그때 멈추면 되는 거니까.
이제 퀵 정렬을 구현해보자.
def quick_sort(a: MutableSequence, x:int)-> None:
pl = 0
pr = len(a)
while pl > pr + 1:
if a[pl] >= x:
if a[pr] <=x:
a[pl], a[pr] = a[pr], a[pl]
pr -=1
pl +=1
뭔가 잘 한 것 같은데...
정답 코드 보겠다.
def partition(a: MutableSequence)-> None:
n = len(a)
pl = 0
pr = n-1
x = a[n//2]
while pl <= pr:
while a[pl] < x : pl +=1
while a[pr] > x : pr -=1
if pl <= pr:
a[pl], a[pr] = a[pr], a[pl]
pl += 1
pr -= 1
하..
나쁜 정답코드 자식..
두개 도달하는 지점을 어떻게 동시에 하나 했더니
조건 하나 만족하면 바로 다음 줄로 넘어가는걸로
가능하다니...
내가 한건 pl만 쭉 옮긴다음에, pr을 쭉 옮겨서 체크하기 때문에 비효율적이겠지...
그리고 x를 넣어주는 값이 아니라 내가 그냥 중간값으로 설정하는 거군...
그리고 while문이라 pl>pr+1이 아니라 그 반대의 경우로 설정을 해줬어야했고...
교환하고나면 pl과 pr을 옮겨주는 작업도 빼먹었군..
-
두 개의 조건을 충족할때까지 반복해야한다면, 그냥 병행해서 나열하자. 줄바꿈도 순서다!
-
교환 후에는 ..... 아무튼 처리를 잘 하자!
이 프로그램에서는
배열 가운데에 있는 원소를 피벗으로 선택했지만,
피벗을 어떤 값으로 하느냐에 따라
배열을 나누는 것과, 정렬하는 성능(performance)에
영향을 끼친다.
이 내용은 피벗 선택하기에서 알아보자.
퀵 정렬 만들기
여기서 조금만 더 발전시켜보자.
두 그룹으로 나눈 뒤,
다시 각각을 두 그룹으로 나누는 것을 반복하면,
원소수 1개인 그룹까지 나누어진다.
원소수 1개는 나눌 필요 없으니,
원소 수 2개 이상인 그룹만 다음과 같이 반복해서 나눈다.
- pr이 a[0]보다 오른쪽에 위치하면 (left<pr) 왼쪽 그룹을 나눕니다.
- pl이 a[n-1] 보다 왼쪽에 위치하면 (pl<right) 오른쪽 그룹을나눕니다.
5장에서 살펴본 8퀸 문제와 같은,
분할 정복 알고리즘이므로 재귀 호출을 사용하여
구현할 수 있습니다..
(저 그거 안 봤어요 선생님)
qsort() 함수는 배열 a,
나누는 구간의 첫번째 원소(left), 마지막 원소(right)의 인덱스를 전달 받아 퀵 정렬을 수행합니다.
그닥...
울고싶지 않으니 한번 8퀸 문제를 들여다보겠다.
보고 왔습니다
경우의 수를 모조리 나열하는 거니까
재귀 호출 쓰고.. 뭐...
분기 나누고...
나눈 다음.. 한정할 거 한정하고...
해봅시다!
def qsort(a: MutableSequence, left:int, right:int)
-> None:
pl = left
pr = right
x = a[(pl+pr)//2]
n = len(a)
while pl <= pr:
while a[pl] < x : pl +=1
while a[pr] > x : pr -=1
if pl <= pr:
a[pl], a[pr] = a[pr], a[pl]
pl += 1
pr -= 1
qsort(a[:pl-1],0,pl-1)
qsort(a[pr+1:],pr+1,n-1)
하..
정답 코드..
볼게요..
def qsort(a: MutableSequence, left:int, right:int)
-> None:
pl = left
pr = right
x = a[pl+pr//2]
while pl <= pr:
while a[pl] < x : pl +=1
while a[pr] > x : pr -=1
if pl <= pr:
a[pl], a[pr] = a[pr], a[pl]
pl += 1
pr -= 1
if left < pr : qsort(a,left,pr)
if pl < right : qsort(a,pl,right)
아아...
그냥 a를 마저 넣어서 인덱스는 그대로 쓸수 있어서
레프트랑 라이트랑 값 그대로 쓰고
pr로 깔끔하게 해결해버렸어..
그리고 다 정렬한 후에 재귀 함수 호출해야하는거고.
근데?
슬라이싱이 뭐가 잘못된 거지?
난 잘 모르겠군.
아 pl-1로 자르면 pl-2까지 나온다니 인덱스가 잘못되었을지도.
음...
아니 근데 부분배열로 잘라질거 고려해서
처음에 레프트랑 라이트를
0, pl-1
0, ... 아 여기 뒷부분에 넣을.. pr뒤의 크기를 나타낼만한 값이 없네... 뭐 len(a)-pr같은걸로 만들 수는 있겠지만..
비재귀적인 퀵 정렬 만들기
05-2절에서 배운 재귀함수 recur()를
비재귀적으로 구현하는 방법과 같이 만들 수 있다...
같이 qsort() 함수를 비재귀적으로 구현해보자!
젠장!!!
시험당하고있어
아..
나 이 부분 공부? 안 했나
하고왔습니다
def qsort(a: MutableSequence, left:int, right:int)
-> None:
pl = left
pr = right
x = a[pl+pr//2]
while pl <= pr:
while a[pl] < x : pl +=1
while a[pr] > x : pr -=1
if pl <= pr:
a[pl], a[pr] = a[pr], a[pl]
pl += 1
pr -= 1
if left < pr : qsort(a,left,pr)
if pl < right : qsort(a,pl,right)
- left < pr 이면 qsort에 left에 left를, right에 pr을 인자로 전달하고 qsort 시켜줍니다...
위를 할 수 있다면 아래도 할 수 있겠지.
if left < pr :
right = pr
당신 어떻게 while 시키실 거에요
last = right
while pl <= pr:
while a[pl] < x : pl +=1
while a[pr] > x : pr -=1
if pl <= pr:
a[pl], a[pr] = a[pr], a[pl]
pl += 1
pr -= 1
if left < pr and last = right :
right = pr
last = left
if pl < right and last = left :
left = pl
last = right
저 제법 괜찮죠??
능력 있죠??
정답 코드
range = Stack(right - left + 1)
range.push((left,right))
while not range.is_empty():
pl, pr = left, right = range.pop()
x = a[(left+right) //2]
while pl <= pr:
while a[pl] < x : pl +=1
while a[pr] > x : pr -=1
if pl <= pr:
a[pl], a[pr] = a[pr], a[pl]
pl += 1
pr -= 1
if left < pr : range.push((left,pr))
if pl < right : range.push((pl,right))
우니?
안.. 울어...
울면..선물... 흑흑
우는 것을 그릇되다고 하는 문화는..
아니 근데 애들 달래려고 하는 말이니까 뭐
울면 선물 안 주신대 = 안 울면 선물줄게!
근데 이젠 난 선물도 못 받는..
흠 이거 어떻게 한 거지?
-
스택을 잘리는 그룹 범위 만큼 만들어놓음
-
레프트와 라이트 값을 넣음
-
안 비어있으면 꺼내서 pl과 pr을 레프트와 라이트로 설정함. 피벗도 그걸로 설정함.
-
두 그룹으로 자름
-
아직 자를만한가? 새 범위 넣음
-
아직 자를 만한가? 나머지 범위 넣음
-
범위 스택에 남아있지? 5번에서 넣었던 범위 꺼내서 넣음
-
또 나누고 있음...
...
다 나누면...
아직 범위가 남아있기 때문에,
처음에 넣어놨던 6번 범위로 다시 반복함.
내가 한 코드는....
....
전부를 보는게 아니라
쭉 내려가서
하나의 조합만 보게 됨...
그치만 여기는..
스택에 여태까지의 모든 오른쪽 왼쪽을 저장해놨음...
아무든 while로 한번 더 감싸고
조건문을 설정하고
그 조건문 체크 포인트를 주는게
비재귀적 전환의 핵심인듯..
내가 생각할 수 있을 지는 모르겠지만
새삼 스택이 재귀함수의 비재귀에 정말 적합하군
만약 인덱스를 직접 지정해서 호출해야한다 하면 꼬였을텐데
나중에 들어온 놈이 먼저 나감..을
반복해서 문제가 안 생김
진행 내역을 저장해서 반복하는 방법, 추천합니다.
스택의 크기
스택의 크기는
정렬 대상인 배열의 원소 수와 같은 값으로 한다.
그러면 스택의 크기는 어느정도가 적당할까?
스택에 푸시하는 순서를 정할 때,
다음 2가지 규칙을 고려할 수 있다.
규칙 1. 원소 수가 많은 쪽의 그룹을 먼저 푸시한다.
규칙 2. 원소 수가 적은 쪽의 그룹을 먼저 푸시한다.
아... 왜?
굳이 순서를..??
이 규칙의 차이가 무엇인지 알아보자.
...
원소수가 많은 그룹을 먼저 푸시하면...
적은 쪽이 나중에 들어온 걸 빨리 처리하기 때문에
처리 속도가 빠르다고 한다.
스택에 동시에 쌓이는 데이터 개수가 적다고 해야할까.
그래서...
규칙 1에서 배열의 원소 수가 n이면,
스택에 쌓이는 데이터의 최대 개수는 log n보다 적다.
그래서, 원소 수 n이 100만개라도
스택의 최대 크기는 20개로 충분하다!
피벗 선택하기
피벗을 선택하는 방법은
퀵 정렬의 실행 효율에 큰 영향을 미친다.
예를 들어,
가장 큰 값을 피벗으로 고른다면,
1개의 그룹과 다른 수많은 원소를 가진 그룹으로 나누어져,
정렬 속도에 큰 영향이 없을 것이다.
그래서,
전체에서 중앙값을 피벗으로 하는 게 이상적이다.
그러나 중앙값을 따로 구하기 위해 전체를 확인한다면,
이것만으로 많은 계산 시간이 걸려서 피벗을 선택하는 의미가 없어질 수 있다.
그래서,
다음 방법을 사용하면 최악의 경우는 피할 수 있다.
방법1. 나누어야할 배열의 원소 수가 3 이상이면, 배열에서 임의의 원소 3개를 꺼내 중앙값인 원소를 피벗으로 선택합니다.
방법 1을 한 단계 더 발전 시키면,
다음과 같은 방법 2가 나온다.
방법2. 나누어야할 배열의 맨 앞 원소, 가운데 원소, 맨 끝 원소를 정렬한 뒤 가운데 원소와 맨 끝에서 두 번째 원소를 교환합니다.
맨 끝에서 두번째 원솟값 a[right-1]이 피벗으로 선택되었고, 그 동시에 나눌 대상을 a[left +1] ~ a[right -2]로 좁힙니다.
4 8 0
0 4 8
0 8 4
8 : right-1 피벗
왜...
이런 짓을..
아니구나
8 4 1 0
0 4 1 8
에서
맨끝에서 두번째라
0 1 4 8
로 교환.
4를 피벗으로 설정.
맨끝에서 두번째랑 교환하는 이유는
이미정렬한 피벗이하값 -----스캔값 ----- 피벗값 이미정렬한 피벗이상값
구조로 만들기 위함...
- 왼쪽 커서 pl의 시작 위치 : left -> left +1 (첫 스타트 지점 다음 칸)
- 오른쪽 커서 pr의 시작 위치 : right -> right -2 (첫 스타트 지점에서 뒤로 두 칸)
이러면 나누는 그룹이 한쪽으로 치우치는 걸 피할 수 있고,
스캔 원소를 3개 줄여서,
이 방법을 사용하지 않을 때보다 조금 더 빠른 속도로 정렬할 수 있다.
(생각해봤는데,
그냥 세개를 뽑아 정렬하면
세 개를 또 스캔해야하지만,
스캔한 김에 정렬 라인에 합치게 한 거.. 같다.)
퀵 정렬의 시간 복잡도
퀵 정렬은
배열을 조금씩 나누어 보다 작은 문제를 푸는 과정을 반복하므로
시간 복잡도는 O(n log n)이다.
그런데 정렬하는 배열의 초깃값이나,
피벗을 선택하는 방법에 따라,
실행 시간 복잡도가 증가하는 경우도 있다.
예를 들어 매번 1개의 원소와 나머지 원소로 나누어진다면,
n번의 분할이 필요하다.
이러한 최악의 경우,
시간 복잡도는 O(n**2)가 된다.
퀵 정렬은 원소 수가 적은 경우에는
그다지 빠른 알고리즘이 아닌 것으로 알려져있다.
그래서 개선하여
다음 2가지 방법을 선택한다.
- 원소 수가 9개 미만인 경우 단순 삽입 정렬로 전환한다.
- 피벗 선택은 방법 2를 채택한다.
? sorted() 함수로 정렬하기
이 함수는
전달받은 이터러블 객체의 원소를 정렬하여
list 형으로 반환한다.
정렬을 직접 수행하지않고(inplace)
정렬을 수행한 뒤 새로운 리스트로 생성하여 반환
합니다.
a, b = sorted([a,b])
이건 unpack하여 각각 a,b에 정렬된 값을 반환하는 수식임.
sorted() 함수는 오름차순을 기본으로 하지만,
reverse에 True값을 주면 내림차순으로 정렬해준다.
x = sorted(x,reverse = True)같은 형식!
튜플은 이뮤터블 속성을 가지므로,
튜플 자체를 정렬할 수는 없다.
튜플을 정령해야한다면,
다음과 같은 2단계 방법을 사용한다.
- 1단계 : sorted() 함수로 정렬한 원소의 나열에서 새로운 리스트를 생성한다.
- 2단계 : 생성한 리스트를 튜플로 변환한다.
x = (1,3,2)
x = tuple(sorted(x))
x
>> (1, 2, 3)(즉, 튜플을 sorted 시키는 건 가능하지만,
리스트가 되므로 다시 튜플로 변환시켜줘야함.)
