비교 정렬(버블, 선택, 삽입)

정렬을 하는 알고리즘 중 가장 쉬운 알고리즘으로 값을 비교해서 정렬하여준다.

버블정렬은 거품이 일어나듯이 정렬을 하며, 맨 앞에서부터 뒤로 한칸씩 확인해 큰 값이 뒤로가게 만들어서 정렬해준다.
시간복잡도는 O(n^2)의 시간복잡도가 걸리게 된다. 단점은 계속해서 변경해주는 함수가 호출된다는 단점이 있다.

선택정렬은 버블정렬의 계속해서 스왑해주는 과정을 없애기 위해 최대값 혹은 최소값을 찾아 위치에 넣어주는 알고리즘이다. 만약 오름차순으로 정렬을 한다면 0~n 중에서 최소를 0번 위치에 그 다음 1~n중 최소를 1번위치에 옮겨주어 구현한다. 버블보다 스왑이 적게 일어난다는 장점이 있지만, 시간복잡도는 최선 혹은 최악 모두 O(n^2)이라는 시간이 걸린다.

삽입정렬은 앞부분이 정렬되어 있다고 가정하고 값을 하나씩 정해진 위치에 삽입시키는 정렬알고리즘이다. 삽입정렬의 장점은 이미 정렬되어 있는 경우 O(n)만에 해결할 수 있다. 최선의 경우 O(n), 최악의 경우 O(n^2)이다.