정렬 (Sorting)

정렬 (Sorting)

특정한 기준에 따라 데이터를 늘어놓는 알고리즘

(아래에 제시한 정렬들은 모두 오름차순 기준)

 

---

1. 선택 정렬 (Selection Sort)

💡 정의

순차적으로 가장 작은 수를 선택하고 교환하는 것을 반복하는 정렬

 

💡 과정

1. 리스트에서 가장 작은 수를 선택한다.
2. 가장 왼쪽의 원소와 교환한다.
3. 반복한다.

 

💡 특징

- 시간복잡도: worst, average, best 모두 O(n^2)

 

---

2. 삽입 정렬 (Insertion Sort)

💡 정의

자신보다 작은 수가 나올 때 까지 오른쪽로 밀어 삽입하는 정렬

 

💡 과정

1. 자신의 왼쪽에 자신보다 작은 수가 나올 때까지 오른쪽으로 민다.
2. 왼쪽에 자신보다 작은 수가 나오면 삽입한다.
3. 반복한다.

 

💡 특징

- 시간복잡도: worst, average 일 때 O(n^2) / best 일 때 O(n)

 

---

3. 버블 정렬 (Bubble Sort)

💡 정의

인접한 두 수를 비교하여 왼쪽값이 자신보다 크면 교환하는 정렬

 

💡 과정

1. 인접한 두 수를 비교하여 왼쪽값이 자신보다 크면 교환한다.
2. 반복한다.

 

💡 특징

- 시간복잡도: worst, average 일 때 O(n^2) / best 일 때 O(n)

 

---

4. 퀵 정렬 (Quick Sort)

💡 정의

왼쪽값과 오른쪽값을 축값과 비교하고 서로 교환한 후 재귀적으로 분할하는 정렬

 

💡 과정

1. 리스트에서 하나의 값(피벗)를 고른다.
2. 피벗을 제외한 나머지 수들 중에서, 왼쪽부터는 피벗보다 큰 수를 찾고, 오른쪽부터는 피벗보다 작은 수를 찾는다.
3. 큰 수와 작은 수의 위치를 교환하고, 큰 수의 위치와 작은 수의 위치가 엇갈릴때까지 해당 과정을 반복한다.
4. 피벗보다 큰 수의 위치와 작은 수의 위치가 엇갈린 경우엔, ‘작은 수의 위치와 피벗의 위치를 교환한다. (분할)
5. 피벗이 이동한 상태에선, 피벗의 왼쪽에 있는 수들은 모두 피벗보다 작고, 피벗의 오른쪽에 있는 수들은 모두 피벗보다 크게 된다.
6. 왼쪽 리스트와 오른쪽 리스트 각각에서도 피벗을 설정하여 퀵 정렬을 진행한다.
7. 분할된 리스트의 데이터 개수가 1개인 경우에는 정렬을 종료한다.

 

💡 특징

- 시간복잡도: average, best 일 때 O(nlogn) / worst 일 때 O(n^2)

 

---

 

[출처 및 참고]

https://coding-factory.tistory.com/615

https://roka88.dev/98