정렬 알고리즘

정렬(Sort)이란 자료의 원소들을 특정 기준에 의해 작은 값부터 큰 값 혹은 그 반대 순서로 재배열하는 것. (오름차순 정렬 / 내림차순 정렬)
아래에 제시한 소팅들의 정렬 과정은 모두 오름차순 기준이다.

버블 정렬(Bubble Sort)

시간복잡도

O(n^2)

버블 정렬은 매번 연속된 두 수를 비교하여 큰 값이 작은 값보다 앞에 있으면 자리를 바꾸고 그게 아니라면 그대로 자리률 유지하는 로직을 반복하는 방식이다. 첫 번째 원소부터 마지막 원소까지 반복하여 한 단계가 끝나면 가장 큰 원소가 마지막 자리에 위치해 있다. 리스트 전체를 비교하는 단계는 원소의 개수만큼 해주면 된다.

선택 정렬(Selection Sort)

시간복잡도

O(n^2)

선택 정렬은 이름에 맞게 현재 위치에 들어갈 원소를 찾아 떠나는 정렬이다.
한 바퀴 돌 때 가장 작은 값을 찾아 맨 앞의 값과 교환하는 방식으로 앞에서부터 정렬해나가는 특성을 가지고 있고어 버블 정렬과 마찬가지로 최악의 성능을 가진 알고리즘이다.

삽입 정렬(Insertion Sort)

시간복잡도

O(n^2)

삽입 정렬은 현재 위치에서 자신보다 작은 위치의 원소들과 비교해 자신이 들어갈 위치를 찾아, 그 자리에 들어가는 정렬이다. 정렬된 그룹에 원소를 늘려가며 추가되는 원소를 알맞은 자리에 삽입하는 방식이다.

합병 정렬(Merge Sort)

시간복잡도

O(n*(logn))

합병 정렬은 분할 정복(Divide and Conquer)을 이용한 방식으로 설계된 정렬 방식이다. 큰 문제를 작은 문제로 쪼개 문제를 해결하는 방식으로 문제의 크기가 1이 될 때까지 쪼갠다. 배열을 1이 될 때까지 쪼갠 후, 배열들의 원소를 각각 비교하여 오름차순으로 정렬하면 된다.

퀵 정렬

시간복잡도

O(n*(logn))

정렬할 전체 원소에 대해서 정렬을 수행하지 않고, pivot point라는 기준 값을 기준으로 작은 값은 왼쪽으로, 큰 값은 오른쪽으로 정렬하는 방법이다. 이를 반복하여 분할된 배열의 크기가 1이면 모두 정렬된 것이다. 합병 정렬과 마찬가지로 분할 정복 알고리즘으로 빠른 시간복잡도를 가진다. 때문에 많은 언어의 정렬 내장 함수로 퀵 정렬을 선택하고 있다.