정렬 알고리즘 알아보기 (1) - 기본 정렬 알고리즘

들어가며

이번 시간에는 기본 정렬 알고리즘에는 어떤 것들이 있는지 알아보겠습니다.

버블 정렬(Bubble sort)

리스트의 첫 원소부터 시작해 인접한 두 원소를 비교하여 정렬하는 가장 단순한 알고리즘입니다.

동작 과정은 다음과 같습니다.

1. 리스트의 첫 번째 원소부터 마지막 원소까지 인접한 두 원소를 비교합니다.
2. 앞의 원소가 뒤의 원소보다 크다면 두 원소의 위치를 서로 바꿉니다.
3. 이 과정을 리스트의 마지막 원소까지 반복합니다.
4. 이 과정을 리스트가 정렬될 때까지 반복합니다.

 

위키피디아 - 버블 정렬 예시

 

시간 복잡도

O(n²)

최선의 경우 O(n). 리스트가 이미 정렬되어 있는 경우 정렬을 한 번만 수행하면 됩니다.

 

공간 복잡도

O(1)

 

특징

• 안정 정렬
• 제자리 정렬
• 리스트가 이미 정렬되어 있는 경우 효율적
• 거의 모든 상황에서 최악의 성능

 

정렬이 이루어지는 모습이 버블이 올라오는 것처럼 보여 버블 정렬이라는 이름이 붙었습니다.

이해가 쉽고 구현이 매우 간단해 주로 교육용으로 사용됩니다.

선택 정렬(Selection sort)

주어진 리스트에서 최솟값을 찾아 리스트의 맨 앞으로 옮기며 정렬을 수행합니다.

 

동작 과정은 다음과 같습니다.

1. 리스트에서 최솟값을 찾습니다.
2. 최솟값을 리스트의 맨 앞 위치로 옮깁니다.
3. 리스트의 두 번째 원소부터 마지막 원소까지 반복하여 최솟값을 찾아 옮깁니다.
4. 이 과정을 리스트가 정렬될 때까지 반복합니다.

 

위키피디아 - 선택 정렬 예시

 

시간복잡도

O(n²)

공간 복잡도

O(1)

 

특징

• 불안정 정렬
• 제자리 정렬
• 리스트 정렬 여부와 상관없이 걸리는 시간이 동일

 

인간이 사용하는 정렬 방식과 유사합니다.

 

삽입 정렬(Insertion sort)

리스트의 두 번째 원소부터 시작하여 그 앞의 원소들과 비교하여 적절한 위치에 삽입함으로써 정렬을 수행합니다.

 

동작 과정은 다음과 같습니다.

1. 두 번째 원소부터 시작하여 그 앞의 원소들과 비교합니다.
2. 현재 원소가 앞의 원소들보다 작다면, 현재 원소를 적절한 위치에 삽입합니다.
3. 이 과정을 리스트의 마지막 원소까지 반복합니다.
4. 이 과정을 리스트가 정렬될 때까지 반복합니다.

 

위키피디아 - 삽입 정렬 예시

 

시간 복잡도

O(n²)

공간 복잡도

O(1)

 

특징

• 안정 정렬
• 제자리 정렬
• 리스트가 이미 정렬되어 있거나 거의 정렬되어 있는 경우 효율적
• 소규모 데이터 처리에 효과적

 

인간이 사용하는 정렬 방식과 유사합니다.

 

정렬 비교 사이트

아래 사이트에서 정렬 알고리즘이 어떻게 수행되는지를 확인할 수 있습니다. 

https://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html

 

마치며

이번 시간에는 기본 정렬 알고리즘에 대해 알아봤는데요.

이들은 구현이 간단하지만, 시간복잡도가 O(n²)으로 크기가 작은 데이터 셋이 아니라면 사용하기가 어렵습니다.

이 세 정렬 알고리즘 중에는 삽입 정렬이 제일 효율적인 편으로 가장 많이 쓰인다고 볼 수 있습니다.

 

지적이나 다른 의견은 언제나 환영합니다 :D

감사합니다.

 

See also

JavaScript의 sort는 어떤 정렬 알고리즘을 사용할까?

정렬 알고리즘 알아보기 (2) - 효율적인 정렬 알고리즘

 

References

https://en.wikipedia.org/wiki/Bubble_sort

https://en.wikipedia.org/wiki/Selection_sort

https://en.wikipedia.org/wiki/Insertion_sort