Sorting 알고리즘

* sorting 알고리즘

리스트를 입력받아서 increasing order로 된 순열 (걍 정렬된 리스트)를 리턴함

1. Insertion sort

a. 원리

: 정렬된 쪽에 키를 하나씩 넣는다. 키 넣을 땐 정렬된 쪽의 젤 큰거부터 작은거까지 비교하면서 자리를 찾는다

-> 비교 대상이랑 키를 비교하고, 비교대상이 더 크면 비교대상을 뒤로 민다. 그리고 끝까지 이 과정을 하고 비어있는 자리 (i+1)에 저장해둔 키를 넣는다

 

b. pseudo code 슈도코드

INSERTION-SORT(A)

  for j=2 to A.length

    key=A[j] //key 저장해둠

    i=j-1 //i는 비교 대상

    while i>0 and A[i]>key //크면 그 큰친구를 오른쪽으로 밀고, 작으면 걍끝냄!

           A[i+1]=A[i]

           i=i-1 // 다음 비교 대상 설정 (바로 이전꺼~)

    A[i+1]=key //저장해둔 키를 밀어서 비어있는 자리에 넣음 (마지막에 while끝날 때 비교대상으로 이전꺼 설정햇으므로 i+1해줘야함)

 

c. runnung time 

* 러닝 타임 -> instrunction의 총 개수를 구하는 것. -> input size에 가장 많이 영향 받음!!!!!

-> 인풋 사이즈 n을 변수로 러닝타임을 정의하게됨 -> T(n)  

이 경우의 러닝타임은 cost x time의 합 !

-> running time

-> best case, average case, worst case가 존재한다 !! (  tj가 어떻게 되냐에 따라 달라짐 )

1. Best case

: A가 이미 sorted 리스트라서, tj가 항상 1인경우 (걍 루프 실행xx)!

->

= an + b

2. worst case

: A가 역순으로 정렬되어 있어서 tj가 항상 j일 경우 (루프 i~0 이렇게 다 시행해야됨 -> 결국 j번이 됨) (max 숫자)

 

---

2. Merge sort

a. 원리

: 두 sorted list를 합친다. 각각 리스트의 맨첨 애를 비교해서 작은 애를 새로운 리스트에 넣는 방식

-> 리스트를 1개 될때까지 다 절반으로 divide 한 담에 차례로 merge 합니다

 

1.divide

2. conquer

머지하는 순서도 썻더욤 ㅎㅎ

* 머지할 때, 밑에가 다 처리된 애들만 Merge한다 !!!!

 

b. 슈도 코드

맨끝까지 가서 합치고 그다음친구의 끝까지가서 합치고 위로가면서 하나씩 합치면서 위의꺼 끝내고, 똑같이 밑에꺼 감 

c. running time

* 연산횟수 구할 때 -> 루프 말고는 다 상수니까 루프에 집중!

*combine- 머지함수

-> T(n) = ?

 

 

-> recursion tree를 그려서 계산한다 !!

 

 

 

 

 

-> recursion tree