정렬

버블정렬

가장 큰 값이 가장 뒤로 떠오른다(bubble)

시간복잡도 n^2
실제연산은 n(n-1) / 2
숫자가커질수록 대략적으로 n^2에 가깝게 증가
0인덱스부터 옆자리와 비교하면서 위치를 바꾸면서 뒤로간다 그러다보면 가장 오른쪽 제일 큰수부터 하나씩 완성하는것
4개 6회
10개 45회
100개 4950회
1000개 499500회

n^2의 절반에 가깝게증가함


4321
3421
3241
3214
2314
2134
1234

선택정렬

버블정렬과 반대로 앞에서 최솟값부터 채워나간다.
가장앞 인덱스를 최솟값으로 지정
배열전체를 탐색하며 최솟값을 갱신
최솟값지점과 가장앞 인덱스를 교체
그 다음 인덱스도 반복
시간복잡도 n^2
실제연산은 n(n-1) / 2

4321
1324
1234

버블정렬보다 스왑은 2배 적지만 모든 배열을 탐색하므로 시간복잡도는n(n-1) / 2
스왑이 적어 버블정렬보단 약 2배 삔르다