[알고리즘] 정렬알고리즘 (선택, 버블, 삽입 / 병합, 퀵, 힙)

원시 정렬 알고리즘

선택정렬 : Θ(n*n)
버블정렬 : 최악 Θ(n*n) 최상 Θ(n)
삽입정렬 : Θ(n*n)

선택정렬 알고리즘 : 

123456 -> 이건 인덱스
936405  : 가장큰수 9를 찾는다 n
536409 : 맨 뒤에 숫자와 바꾼다 1
            가장큰수 6를 찾는다 n-1
530469 : n-1번째 숫자와 바꾼다.

n+(n-1)+(n-2) ... +1 의 시간이 걸림

= n(n+1)/2 이므로 Θ(n*n) 이다.

버블정렬 알고리즘 :

956405 : 맨앞부터 두개씩 비교해나간다. 01 12 23 34...
596405 : 순서대로 되어있지 않으면 바꾼다 ...............상수
569405
564905
564095
564059 : 요까지 n-1 , 1바퀴

반복한다

n-1 + n-2 + n-3 + ... + 1 = n(n-1)/2 = Θ(n*n)

하지만 맨앞부터 두자리씩 비교하내가다가 결국 m바퀴 째에서 우연히 순서가 잘못되어 있는 것이 없다면
그 시점에서 정렬은 종료된다. 운이좋다면 처음부터 정렬되어 있는 배열일수도 있고 이때 시간은 Θ(n)이다,
최악의 경우(역순으로 정렬되어있을경우)에 Θ(n*n)의 시간이 걸린다.

삽입정렬 알고리즘 :
앞에서부터 적당한 위치를 찾아 정리한다.

956405 ... 9를 어디에 넣을것인가? .... 1
596405 ... 5를 어디에 넣을것인가?
569405 ... 6을 어디에 넣을것인가?
456905 ... 4을 어디에 넣을것인가? .... n-3
045695 ... 0을 어디에 넣을것인가? .... n-2
045569 ... 5를 어디에 넣을것인가? .... n-1

n-1 + n-2 + n-3 + ... + 1 = n(n-1)/2 = Θ(n*n)

고급정렬 알고리즘

병합정렬 Θ(n log n)
퀵정렬 평균 Θ(n*n) , O(n*n)
힙정렬 Θ(n log n)

병합정렬

9 23 96 3 2 7 49 33 12
        (mergeSort1)
9 23 96 3     2 7 49 33 12
 (mS2)           (mS7) 

9 23         96 3        2 7       49 33 12
(mS3)     (mS5)      (mS8)     (mS10) 
9    23      96  3        2    7     49    33 12

                                                  (mS11) 

                                                 33     12
                                                 (merge12)
                                                     12 33

(merge4)  (merge6)  (merge9)   (merge13)
9 23            3 96          2 7          12 33 49
      (merge3)                   (merge14)
       3 9 23 96                      2 7 12 33 49
                      (merge15)
                     2 3 7 9 12 23 33 49


퀵정렬
9 23 96 3 2 7 49 33 12

9 23 96 3 2 7 49 33 12   맨 뒤에 숫자를 기준으로 
9 3 2 7 12 23 96 49 33   작은 숫자는 왼쪽, 큰숫자는 오른쪽에 배치

9 3 2 7 12 23 96 49 33   왼쪽, 오른쪽 각각 독립적으로 위의 과정을 반복
3 2 7 9 12 23 33 96 49 

3 2 7 9 12 23 33 96 49
2 3 7 9 12 23 33 49 96  이렇게

힙정렬