정렬 알고리즘에는 여러가지가 있지만 구현하기 매우 간단한 3가지만 먼저 살펴보자

선택 정렬

선택 정렬이란 말 그대로 정렬해야 할 배열에서 가장 큰 수를 선택한 뒤 배열의 마지막 위치로 보내버리는 정렬이다

간단하게 작동 과정을 살펴보면

시간 복잡도는 O(n^2)

버블 정렬

버블 정렬은 옆의 수와 비교한 뒤 비교한 수보다 크면 둘의 위치를 바꾸고 다시 옆의 수와 비교해서 자리를 바꾸며 찾아가는 정렬이다

[3,2,1,4,5]의 배열을 버블 정렬을 이용해서 정렬해보자

제일 첫 수인 3을 바로 옆에있는 2와 비교한다 3이 더 크니까 두개의 자리를 바꾼다

[2,3,1,4,5]

이제 3과 1을 비교해서 3이 더 크니 둘의 자리를 바꾼다

[2,1,3,4,5]

3과 4를 비교해서 3이 더 작으니 그대로 놔두고 비교 대상을 4로 옮긴다

[2,1,3,4,5]

4와 5를 비교해서 4가 더 작으니 5를 비교 대상으로 옮기는데 이미 인덱스의 마지막으로 와 버렸으니 마지막 인덱스에는 가장 큰 수가 와 있다

그렇기 때문에 마지막 인덱스를 제외하고 [2,1,3,4,5] 위의 정렬을 반복해주면 된다

시간 복잡도는 O(n^2)

삽입 정렬은 위의 두개처럼 직관적이진 않은데 비어있는 배열에 숫자를 하나씩 받아서 제자리에 놔두는 방식으로 정렬을 한다고 느끼면 된다

마찬가지로 [3,2,1,4,5]을 삽입 정렬로 정렬해 보면

제일 처음으로 3을 가져와서 삽입한다 [3] 이 상태의 배열은 정렬되었다고 볼 수 있다 [2,1,4,5]

그 뒤에 2를 가져와서 삽입하는데 이때 3과 비교해서 2를 넣을 위치를 결정하고 삽입한다 [2,3]은 정렬되어있고 남은 것은 [1,4,5]

이를 반복하면된다

근데 이 삽입을 구현할 때 주의해야 하는 점이있는데

예를 들어서 [1,2,3,4,6,7,8,9,10] 에 마지막 수인 5를 삽입한다고 할 때

5의 위치를 찾기 위해서는 1부터 찾아 올라가는 방법과 10에서 내려가는 방법 두가지가 있다

두개 다 시간 복잡도에는 영향이 없을 거라고 생각하지만 1에서부터 위치를 찾고 5를 넣기 위해서는 배열의 6,7,8,9,10을 한칸씩 뒤로 밀어줘야해서

결국 배열 전체를 순회하는 시간 복잡도를 가지게 된다

반대로 10에서 부터 찾는 방법은 5가 들어갈 위치를 찾음과 동시에 한칸씩 뒤로 미는 작업을 수행하면 된다 그렇게 하면 1,2,3,4는 순회하지 않아도 되는 것

시간 복잡도는 최악일 경우 O(n^2)

최선일 경우 O(n)