버블정렬 선택정렬 삽입정렬 퀵정렬

구현이 간단하지만 비효율적인 정렬방법 : 삽입 정렬, 선택 정렬, 버블 정렬

구현이 복잡하지만 효율적인 정렬방법 : 퀵 정렬, 힙 정렬, 합병 정렬, 기수 정렬

 

버블정렬

서로 인접한 두 원소를 비교하여 순서대로 교환한다.
1회전을 수행하고 나면 가장 큰 원소가 맨 뒤로 이동하므로 2회전에서는 맨 끝에 있는 원소는 정렬에서 제외된다.

정렬을 1회전 수행할 때마다 정렬에서 제외되는 원소가 하나씩 증가한다.

[버블정렬] 1회전

[버블정렬] 2회전

[버블정렬] 3회전

시간복잡도 O(n^2)

회차마다 비교를 n-1, n-2, … , 2, 1 번하므로 총 n(n-1)/2

 

선택정렬

최소값을 찾은 후 첫번째 원소와 교환한다.

1회전을 수행하고 나면 첫번째 원소를 제외한 최소값을 찾은 후, 두번째 원소와 교환한다.

정렬을 1회전 수행할 때마다 정렬에서 제외되는 원소가 하나씩 증가한다.

 

[선택정렬]

시간복잡도 O(n^2)

최솟값을 탐색하기 위한 비교를 회차마다 n-1, n-2, … , 2, 1 번하므로 총 n(n-1)/2

 

삽입정렬

두번째 원소와 좌측의 정렬된 원소와 비교하여, 순서에 맞는 올바른 위치를 찾아 원소를 삽입한다.

정렬된 원소를 역순으로 비교하며, 올바른 위치가 아닐 경우 한 칸씩 뒤로 이동시킨다.

 

[삽입정렬] 전체 흐름

[삽입정렬] 원소의 이동과 삽입

시간복잡도

O(n) : 이미 정렬된 최선의 경우, n-1번의 1회차 비교만 수행한다.

O(n^2) : 역순으로 정렬된 최악의 경우, 버블정렬와 선택정렬과 동일하다.

 

퀵정렬

피벗을 기준으로 왼쪽은 피벗보다 작은 원소, 오른쪽은 피벗보다 큰 원소가 위치한다.
low는 피벗보다 클 때까지 우측으로 이동하고, high는 피벗보다 작을 때까지 이동한다.

[퀵정렬] high와 low가 역전하기 전

 

[퀵정렬] high와 low가 역전한 후

 

시간복잡도

O(nlog₂n) : 불균형 분할 없이 계속 절반씩 분할되는 최선의 경우 (피벗이 항상 중간값일 경우)

• 1차: 31개의 데이터가 있을 때 15개씩 둘로 나뉘어 2 덩어리

• 2차: 7개씩 2덩어리, 총 4덩어리

• 3차: 3개씩 2덩어리, 총 8덩어리

• 4차:1개씩 2덩어리, 총 16덩어리 

따라서 둘로 나뉘는 횟수는 log₂n번, 피벗과 원소의 비교횟수는 n번이다.

불균형 분할이 없는 최선의 경우

O(n^2) : 계속 불균형 분할되는 최악의 경우 (피벗이 항상 최소값 또는 최대값일 경우)

둘로 나뉘는 횟수도 n번, 피벗과 원소의 비교횟수도 n번이다.