📚 정렬

정렬(Sorting)이란 데이터를 특정한 기준에 따라 순서대로 나열하는 것을 말한다
일반적으로 문제 상황에 따라서 적절한 정렬 알고리즘이 공식처럼 사용된다

정렬에는 선택 정렬, 삽입 정렬, 퀵 정렬, 계수 정렬 등등이 있다

---

📕 선택정렬

데이터가 무작위로 여러 개 있을 때 이중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정

정렬에서 시간 복잡도가 중요한데 반복문의 중첩에 따라 달라진다
선택정렬 같은경우 시간 복잡도는 O(N^2)이다

#include <iostream>

using namespace std;

int n = 10;
int arr[10] = {7, 5, 9, 0, 3, 1, 6, 2, 4, 8};

int main()
{
    for (int i = 0; i < n; i++)
    {
        int min_index = i;
        for (int j = i + 1; j < n; j++)
        {
            if (arr[min_index] > arr[j])
                min_index = j;
        }
        swap(arr[i], arr[min_index]);
    }
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    return 0;
}

---

📘 삽입 정렬

처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입한다
선택 정렬에 비해 효율적

선택정렬과 시간복잡도는 같지만 배열이 거의 정렬이 되어있다면 선택정렬보다 빠르게 동작한다

#include <iostream>

using namespace std;

int n = 10;
int arr[10] = {7, 5, 9, 0, 3, 1, 6, 2, 4, 8};

int main()
{
    for (int i = 1; i < n; i++)
    {
        for (int j = i; j > 0; j--)
        {
            if (arr[j] < arr[j - 1])
                swap(arr[j], arr[j - 1]);
            else
                break;
        }
    }
    for(int i = 0; i < n; i++)
        cout << arr[i] << ' ';
    return 0;
}

---

📙 퀵 정렬

기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법
일반적인 상황에서 가장 많이 사용되는 정렬 알고리즘 중 하나이다
병합 정렬과 더불어 대부분의 프로그래밍 언어의 정렬 라이브러리의 근간이 되는 알고리즘이다
가장 기본적인 퀵 정렬은 첫 번째 데이터를 기준 데이터(Pivot)로 설정합니다

다음과 같이 피벗을 설정하고 왼쪽에서 피벗보다 큰 데이터 선택하고 오른쪽에서 부터 피벗보다 작은 데이터를 선택한 후에 위치를 변경한다 계속반복하다가 두 값이 엇갈린 경우에 피벗의 위치를 작은 데이터와 피벗의 위치를 변경하여 분할한 후 새로운 피벗을 설정하고 반복한다
시간복잡도는 O(NlogN)이지만 최악의경우 O(N^2)가 나오기도 한다

#include <iostream>

using namespace std;

int n = 10;
int arr[10] = {7, 5, 9, 0, 3, 1, 6, 2, 4, 8};

void quickSort(int* arr, int start, int end)
{
    if (start >= end)
    	return; 
    int pivot = start;
    int left = start + 1;
    int right = end;
    while (left <= right)
    {
        while (left <= end && arr[left] <= arr[pivot])
            left++;
        while (right > start && arr[right] >= arr[pivot])
            right--;
        if (left > right)
            swap(arr[pivot], arr[right]);
        else
            swap(arr[left], arr[right]);
    }
    quickSort(arr, start, right - 1);
    quickSort(arr, right + 1, end);
}

int main()
{
    quickSort(arr, 0, n - 1);
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
}

코드는 시작지점과 끝지점 두개를 지정해두고 정렬한다

---

📗 계수 정렬

특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠르게 동작하는 알고리즘이다
계수 정렬은 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때 사용 가능하다
데이터의 개수가 N, 데이터(양수) 중 최댓값이 K일 때 최악의 경우에도 수행시간 O(N+K)를 보장한다

데이터를 모두 담을수 있는 배열을 선언하고 각 인덱스에 데이터가 몇번 등장했는지 저장해놓고 출력한다

#include <iostream>
#define MAX_VALUE 9

using namespace std;

int n = 15;
int arr[15] = {7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2};
int cnt[MAX_VALUE + 1];

int main()
{
    for (int i = 0; i < n; i++)
    	cnt[arr[i]] += 1;
    for (int i = 0; i <= MAX_VALUE; i++)
    {
        for (int j = 0; j < cnt[i]; j++)
            cout << i << ' ';
    }
}

---

📄 정렬 알고리즘 비교

---

📚 예제

📕위에서 아래로

수열을 내림차순으로 정렬하는 프로그램을 만드시오

#include <iostream>
#include <algorithm>

using namespace std;

int arr[501];

bool compare(int a, int b)
{
    return a > b;
}

int main()
{
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> arr[i];
    sort(arr, arr + n, compare);
    for (int i = 0; i < n; i++)\
        cout << arr[i] << " ";
    return 0;
}

단순하게 배열을 선언하고 정렬 라이브러리를 이용하였다 비교를위해 compare 함수를 따로 만들었다.

---

📘 성적이 낮은 순서로 학생 출력하기

N명의 학생의 이름과 성적 정보가 주어졌을 때 성적이 낮은 순서대로 학생의 이름을 출력하라

예전에 백준에서 푼 문제가 똑같아서 쉽게 풀었다 pair를 이용해서 string, int 형으로 받고 비교를 한 후 출력해주었다 안정정렬은 입력한 순서대로 나오는걸 말한다
참고문제
10814 나이순정렬

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

bool comp(pair<string, int> x, pair<string, int> y)
{
    return x.second < y.second;
}

int N;
vector<pair<string, int>> v;

int main()
{
    cin >> N;
    for (int i = 0; i < N; i++)
    {
        string a;
        int b;
        cin >> a >> b;
        v.push_back({a, b});
    }
    stable_sort(v.begin(), v.end(),comp);

    for(auto c : v)
        cout << c.first << " ";
}

---

📙 두 배열의 원소 교체

동빈이는 두개의 배열 A와 B를 가지고 있다 두 배열은 N개의 원소로 구성되어 있으며, 배열의 원소는 모두 자연수이다. 동빈이는 최대 K번의 바꿔치기 연산을 수행할 수 있는데, 바꿔치기 연산이란 배열 A에 있는 원소 하나와 배열 B에 있는 원소 하나를 골라서 두 원소를 서로 바꾸는 것을 말한다. 동빈이의 최종 목표는 배열 A의 모든 원소의 합이 최대가 되도록 하는 것이다

두개의 배열을 각각 오름차순, 내림차순으로 정렬을 하고 두 배열의 원소를 첫 번째 인덱스부터 차례로 확인하고 A의 원소가 B의 원소보다 작을경우 바꿔주면 된다

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;


vector<int> a, b;

bool compare(int x, int y)
{
    return x > y;
}

int main()
{
    int n, k;
    cin >> n >> k;
    for (int i = 0; i < n; i++)
    {
        int x;
        cin >> x;
        a.push_back(x);
    }

    for (int i = 0; i < n; i++)
    {
        int x;
        cin >> x;
        b.push_back(x);
    }
    sort(a.begin(), a.end());
    sort(b.begin(), b.end(), compare);
 
    for (int i = 0; i < k; i++)
    {
        if (a[i] < b[i])
            swap(a[i], b[i]); 
        else
            break;
    }
    long long result = 0;
    for (int i = 0; i < n; i++)
        result += a[i];
    cout << result << "\n";
}

---

➕ 3273 두 수의 합

n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 (ai, aj)쌍의 수를 구하는 프로그램을 작성하시오.

처음 생각으로는 정렬한 후 두 수를 이중반복문으로 돌려가면서 더해보려고 했는데 인터넷에 찾아보니 시간초과가 난다고 나와있어서 좀 특이한 코드가 있길래 참고해보았다

#include <iostream>

using namespace std;

int num[2000001];

int main()
{
    int n, a, b;
    int cnt = 0;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> a;
        num[a]++;
    }
    cin >> b;
    for (int i = 0; i < (b + 1)/2; i++)
    {
        if (num[i] == 1 && num[b - i] == 1)
            cnt++;
    }
    cout << cnt << endl;
}

이런식으로 풀면 애초에 정렬을 할 필요도 없어지고 단순히 인덱스만 참조하여서 풀 수 있어서 좀더 간단한 방법인거 같다