소프트웨어개발 - 빅오(O)표기법 종류

#1 버블정렬

인덱스0부터 시작하여 끝까지 비교를 한다
비교를 하는동안에 정렬 기준(오름차순,내림차순)에 따른 적합한 수가 가장 마지막 인덱스에 갈때까지 각 인덱스는 서로를 비교하여 정렬기준에 적합하게 자리를 바꿔준다.
정렬기준에 적합한 수가 마지막에 도달하면 마지막 인덱스는 동결된다
평균적인 시간복잡도 O(n제곱)

---

#2 삽입정렬

 

인덱스상 0과1을 비교하여 기준에 적합한(오름차순이면 낮은수가 왼쪽, 내림차순이면 큰수가 왼쪽)수가 정렬이 된다
정렬후에 인덱스0은 동결되고 인덱스 1과 2를 비교하여 기준에 적합한 수가 왼쪽(인덱스1번)에 온다. 이제 인덱스 0,1은 동결된다.
인덱스 2와 3을 비교하여 기준에 적합한수가 인덱스 2에 위치하고,
인덱스 0부터 2까지는 동결된다.
이런식으로 끝까지 간다
평균적인 시간복잡도 O(n제곱)

---

#3 선택정렬

인덱스 0의 숫자와 전체의 수를 비교하여
정렬 기준에 따라 인덱스 0에 위치하게 된다. 인덱스 0은 동결되게 된다.
만약 기존에 있던 인덱스0의 자리에 있던 숫자가 밀려난다면, 교환된 숫자 자리의 인덱스 위치로 가게된다
드리고 인덱스 0은 비교가 끝났으니 동결된다
다음으로는 인덱스 1과 전체의 수를 비교
이런식으로 끝까지 간다
평균적인 시간복잡도 O(n제곱)

---

#4 합병(병합)정렬

이거는 내가 잘 이해를 못한건지, 이해를 제대로 했다면 합리적인 방법은 아닌듯 하다

모든 수를 일단 인덱스 0과 1의 형태로 쪼갠다 (비교대상이 서로가 전부인 형태)
그러면 8개로 시작한 숫자세트라고 쳤을때
8개(0단계), 4개, 4개(1단계), 2개, 2개, 2개, 2개(2단계)
라고 되고
2단계에서 서로 비교가 끝난 수들에 대해서는 정렬기준에 따라 정렬을 하고
1단계에서 서로를 비교할때는 각각의 인덱스 0으로 정렬된것들을 인덱스 0끼리 비교를 하고 인덱스 1로 정렬된것들은 인덱스 1끼리 정렬을한다

평균적인 시간복잡도 O(nlog제곱n)