cs 기초 - 소팅

[yeomko22]

• 정렬 알고리즘들의 종류와 time complexity, 적합한 사용처 등을 조사한다.

[yeomko22]

Bubble sort

• 시간복잡도: O(n^2)
• 방식: 바로 뒤 요소와 비교하여 큰 값을 뒤로 보낸다. 한바퀴 돌 때마다 마지막 요소 하나가 정렬된다.
• 사용처: 가급적 쓰지 말 것

[yeomko22]

Selection Sort

• 시간복잡도: O(n^2)
• 방식: 첫번째부터 쭉 훑어서 가장 작은 값을 1번째로, 두번째부터 훑어서 가장 작은 값을 2번째로 가져오는 식으로 정렬
• 사용처: 쓰지마...

[yeomko22]

Insertion Sort

• 시간복잡도: O(n^2)
• 두번째 인덱스서부터 시작, 앞에 값들과 쭉 비교해나가면서 자기보다 크면 계속 스왑, 앞에 값이 자기보다 작으면 그 위치에서 insert
• 사용처: 이미 정렬되어 있는 자료구조에 자료를 하나씩 삽입/제거 하는 경우에 적합, 배열이 작은 경우에도 적합

[yeomko22]

Merge Sort

• 시간복잡도: O(nlogn)
• 반씩 쪼개어 sorting을 수행한다. 대표적인 분할 정복 알고리즘
• 데이터의 상태에 영향을 받지 않는다. 일반적으로 퀵 정렬보다 성능은 떨어진다.

[yeomko22]

Heap Sort

• 시간 복잡도: O(nlogn)
• 힙 자료 구조에 데이터를 삽입한다. 힙 자료구조에 대한 삽입 연산은 O(logn)이다.
• 항상 일정한 성능을 보여서 퀵정렬에 대한 장점이 있다.

[yeomko22]

Quick Sort

• 시간 복잡도: O(nlogn)
• 랜덤한 피벗을 잡고 그보다 작은 것은 왼쪽으로, 큰 것은 오른쪽으로 옮긴다. 그 다음 다시 왼쪽과 오른쪽에서 다시 피봇을 잡고 소팅을 진행한다.
• 일반적으로 가장 빠르다고 알려져있다. 그러나 극단적인 경우에는 최대 O(n^2)이 될 수 있다. 떄문에 피벗 값을 잘 정할 수 있도록 다양한 기법들이 제시되었다.