1) 선택정렬
선택정렬은 최솟값을 하나씩 찾아서 그 값을 배열에 첫 부분부터 차례대로 채우는 방식이다
최선,평균,최악 다 동일하게 O(n^2)이 걸린다.
#include<iostream>
#include<vector>
using namespace std;
void select(vector<int>& arr) {
int n = arr.size();
for (int i = 0; i < n - 1; i++) {
int midIdx = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[midIdx]) {//최솟값의 주소를 찾는거임
midIdx = j;
}
}
swap(arr[i], arr[midIdx]);//위에서 찾은 최솟값의 주소의 주소값을 원래 배열과 변경해주어 작은 순서대로 입력되게 바꿈
//ex) arr=4,3,2,1,5
//1단계를 거치면
//arr=1,3,2,4,5
}
}
int main() {
int N;
cin >> N;
vector<int> arr(N);
for (int i = 0; i < N; i++) {
cin >> arr[i];
}
select(arr);
for (int num : arr)cout << num << '\n';
return 0;
}
2) 버블정렬
배열에서 인접한 두 요소를 비교하고 필요하면 교환한다. 한 번의 이동이 끝나면 가장 큰 값이 맨 끝으로 이동하고 이를 반복하여 정렬한다.
1) 선택정렬과 달리 큰값을 먼저 구해서 맨 끝으로 보낸다고 생각하면 됨
최선: O(n)
평균: O(n^2)
최악: O(n^2)
#include<iostream>
#include<vector>
using namespace std;
int main() {
int N;
cin >> N;
vector<int> arr(N);
for (int i = 0; i < N; i++) {
cin >> arr[i];
}
int n = arr.size();
for (int i = 0; i < n - 1; i++) {//몇번 반복할지 정하는거임 마지막은 하나밖에 안남으니 n-1번 반복
for (int j = 0; j < n - 1-i; j++) {
if (arr[j] > arr[j + 1]) {#크면 하나씩 자리를 변경해서 큰값이 가장 뒤로 가게 한다.
swap(arr[j], arr[j + 1]);
}
}
}
for (int num : arr) cout << num << '\n';
return 0;
}
3) 삽입정렬
두 번째 요소부터 시작해서 앞의 정렬 된 부분과 비교해서 적절한 위치에 삽입한다.
최선:O(n)
평균,최악:O(n^2)
#include<iostream>
#include<vector>
using namespace std;
void select(vector<int>& arr) {
int n = arr.size();
for (int i = 1; i < n; i++) {//비교할 주소
int key = arr[i];
int j = i - 1;//바로 전에 주소
while (j >= 0 and arr[j] > key) {//비교하기 전에 있는 배열은 이미 정렬이 되어있으므로
//arr[i-1]이 제일 큰 값임
//근데 이 값이 arr[i]값을 넘어서면 비교할 필요가 없음
arr[j + 1] = arr[j];//비교하는 값에 arr[j]값을 입력함
j -= 1;//1씩 줄이면서 계속 값을 넣어보는거임
}
arr[j + 1] = key; //정렬이 되면 바로 다음 주소에 key값을 넣어줌
}
}
int main() {
int N;
cin >> N;
vector<int> arr(N);
for (int i = 0; i < N; i++) {
cin >> arr[i];
}
select(arr);
for (int num : arr)cout << num << '\n';
return 0;
}
4) 셸 정렬
3)을 개선한 방식으로 일정한 간격으로 떨어진 요소들을 그룹으로 정렬한 후에 점차 간격을 줄이면서 최종적으로는 3)삽입정렬을 수행한다.
최선:O(n)
평균:O(n^1.5)
최악:O(n^2)
gap에 따라 비교를 시작함 예를 들어서 gap=3이면
arr[0]과 arr[3]
arr[1]과 arr[4]
이런식으로
arr[n-3]과arr[n]
을 비교하여 자리를 바꿈
그러다가 gap이 1이 되면
3)선택정렬이 되어버려서 선택정렬로 마무리가 됨
#include <iostream>
#include <vector>
using namespace std;
// 간격에 따른 삽입 정렬 수행
void insertionSortWithGap(vector<int>& arr, int n, int gap) {
for (int i = gap; i < n; i++) {
int temp = arr[i];
int j;
for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
arr[j] = arr[j - gap];
}
arr[j] = temp;
}
}
// 셸 정렬 함수
void shellSort(vector<int>& arr) {
int n = arr.size();
// 초기 간격 설정
for (int gap = n / 2; gap > 0; gap /= 2) {
// 간격에 따른 삽입 정렬 수행
insertionSortWithGap(arr, n, gap);
}
}
int main() {
vector<int> arr = {12, 34, 54, 2, 3};
cout << "정렬 전 배열: ";
for (int num : arr) {
cout << num << " ";
}
cout << endl;
shellSort(arr);
cout << "정렬 후 배열: ";
for (int num : arr) {
cout << num << " ";
}
cout << endl;
return 0;
}
5)퀵 정렬
배열에서 하나의 요소를 선택하고 그것을기준으로 작은 값은 왼쪽으로 큰 값은 오른쪽으로 분할한다. 그리고 각 부분에 대해서 재귀적으로 반복한다.
최선,평균=O(n log n)
최악:O(n^2)-이미 정렬된 경우 피벗 선택이 나쁠 때
#include<iostream>
#include<vector>
using namespace std;
int partition(vector<int>& arr, int low, int high) {
int pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
swap(arr[i], arr[j]);
}
}
swap(arr[i + 1], arr[high]);
return i + 1;
}
void quickSort(vector<int>& arr, int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
int main() {
int N;
cin >> N;
vector<int> arr(N);
for (int i = 0; i < N; i++) {
cin >> arr[i];
}
quickSort(arr, 0, N - 1);
for (int num : arr) cout << num << '\n';
return 0;
}
파이썬으로 이해하는 것이 더 빨라보인다.
def quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2] # 중앙값을 피벗으로 선택
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quick_sort(left) + middle + quick_sort(right)
arr = [5, 3, 8, 4, 9, 1, 6, 2, 7]
sorted_arr = quick_sort(arr)
print(sorted_arr)
6) 병합 정렬
배열을 절반으로나누어서 각각 정렬하고 다시 병합한다.
최선,평균,최악:O(n log n)
코드가 많이 복잡하다
#include<iostream>
#include<vector>
using namespace std;
void merge(vector<int>& arr, int left, int mid, int right) {
vector<int>leftArr(arr.begin() + left, arr.begin() + mid + 1);
vector<int>rightArr(arr.begin() + mid + 1, arr.begin() + right + 1);
int i = 0, j = 0, k = left;
while (i < leftArr.size() && j < rightArr.size()) {
if (leftArr[i] <= rightArr[j]) arr[k++] = leftArr[i++];
else arr[k++] = rightArr[j++];
}
while (i < leftArr.size()) arr[k++] = leftArr[i++];
while (j < rightArr.size()) arr[k++] = rightArr[j++];
}
void mergeSort(vector<int>& arr, int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
}
int main() {
int N;
cin >> N;
vector<int> arr(N);
for (int i = 0; i < N; i++) {
cin >> arr[i];
}
mergeSort(arr, 0, N - 1);
for (int num : arr) cout << num << '\n';
return 0;
}