내부 정렬

외부 정렬

정렬해야할 것들이 메모리 외부에 있음 하드에나
그래서 메인 메모리에 들어갈만큼 잘라서 정렬하고 하드에 넣어서.. 반복하다가 각각 정렬된 걸 또 지들끼리 병합merge해서 하드에 원소 하나 남을 때까지...근데 이렇게 하면 결국 하드에 있는 모든 데이터 크기를 메.메에 넣게되는 거 아님?
~~아 전체 크기/2 까지는 수용 가능해야되네 ~~
아니 그게 아니라 주기억장치의 용량은 그냥 그대로 작은대로고 거기에 맞게 하드에서 데이터 조금씩 긁어와서
??아니 그럼 뒤에 더 작은 값의 데이터가 있을지 어떻게 앎? 야 이미 정렬된 데이터들이잖아 그니까 각자 자료의 앞값만 보고도 바로 하드에 저장 정렬할 수 있는???? 정렬에는 1기가만 써도 됨(그림)
난 또 데이터를 처음부터 전체 다 메메에 불러오는 줄
그럼 메메에서 비교하고 정렬저장은 바로 하드에서?

https://dudri63.github.io/2019/02/03/algo32/

Performance evaluation 성능평가

하드와 메인메모리 사이의 이동 횟수
비교를 몇 번 했냐

Selection sort

n개 원소에서 선형 탐색으로 제일 작은 놈 or 큰 놈 찾아서 min max에 저장하고 탐색 끝나면 그 놈을 제일 왼쪽 or 오른쪽에 저장
SWAP하는 거임
그림처럼 하드에 저장한다고 하니까 별개의 리스트나 저장공간을 만드는 것같은데 결론은 원래 하드에 다시 집어넣는 거라 swap이라고 보면 됨
첫번째 놈보다 작은 거 찾기. 첫번째랑 스왑, 첫번째는 제외하고 두번째 놈보다 작은 거 찾기..
그럼 (N-1)! 아님? 하나씩 제외되니까
아니 (N-1) (N-2) ... 1 이 아니라
(N-1) + (N-2) + ... 1 이잖냐!!!!!!!!!!!!!!!
그래서 등차수열로 하면 어쩌고.라서
O(n**2)

코드

a=list(map(int,input().split()))

count=0
 #오름차순이니까 min 찾기
for j in range(len(a)):
    min=a[j]
    for i in range(j,len(a)): #자기 자신과도 비교해야 한 번 할 때마다 count가 갱신됨. j+1로 하면 6 5 4(count=2) -> 4 5 6(count=2) -> 4 6 5
        if min<a[i]:
            continue
        else:
            min=a[i]
            count=i #min이 있는 곳
    a[j],a[count]=a[count],a[j]
print(a)

버블 정렬

코드

a=list(map(int,input().split()))

 #오름차순이니까 min 찾기
while True: #정렬될 때까지
    count=0 #count 여기다 해야됨 for 안에다 하면 n-2인덱스랑 n-1이 정렬된 상태에서 count=0이 돼서 거기서break됨
    for j in range(len(a)-1): #한 줄 쫙 돌기
        if a[j]>a[j+1]: 
            a[j],a[j+1]=a[j+1],a[j]
            count+=1
    if count==0: #한 번도 정렬 안 됐으면 완성
        break
print(a)