[알고리즘] 정렬(Sort)

n개의 숫자가 입력으로 주어졌을 때, 이를 사용자가 지정한 기준에 맞게 정렬하여 출력하는 알고리즘

1. 선택 정렬(Selection Sort)

• 현재 위치에 들어갈 값을 찾아 정렬하는 배열
• 현재 위치에 저장 될 값의 크기가 작냐, 크냐에 따라 __최소 선택 정렬(Min-Selection Sort)과 최대 선택 정렬(Max-Selection Sort)로 구분
• 최소 선택 정렬은 오름차순, 최대 선택 정렬은 내림차순

로직

1. 정렬 되지 않은 인덱스의 맨 앞에서부터, 이를 포함한 그 이후의 배열값 중 가장 작은 값을 찾아간다.

---

C++ STL : sort

• algorithm 헤더파일에 속해 있다.
• sort(start, end)를 이용하여 start 이상, end 미만에 있는 인자를 오름차순(default)으로 정렬해주는 함수이다.
• Quick Sort(퀵 정렬) 기반으로 함수가 구현되어있어, 평균 시간복잡도는 n log n 이다.

원형 및 사용법

template <typename T>
void sort(T start, T end);

template <typename T>
void sort(T start, T end, Compare comp);

3번째 인자에 사용자가 정의한 함수를 기준으로 정렬을 할 수 있다.

• sort(arr, arr+n);
• sort(v.begin(), v.end());
• sort(v.begin(), v.end()), compare); // 사용자 정의 함수 사용
• sort(v.begin(), v.end(), greater<자료형>()); // 내림차순
• sort(v.begin(), v.end(), less<자료형>()); // 오름차순

예제

1. Array sort : 오름차순(default)

#include<iostream>
#include<algorithm>
using namespace std;

int main(void) {
    int numberOfInput = 0;

    cout << "How many Inputs? : ";
    cin >> numberOfInput;

    int* arr = new int[numberOfInput];

    for (int i = 0; i < numberOfInput; i++) {
        cout << "arr[" << i << "] : ";
        cin >> arr[i];
    }

    sort(arr, arr + numberOfInput);

    for (int i = 0; i < numberOfInput; i++) {
        cout << arr[i] << " ";
    }
    return 0;
}

2. Vector/Array container sort : 내림차순

#include<iostream>
#include<ctime>
#include<algorithm>
#include <vector>
using namespace std;

void Print(vector<int> &v) {
    for (int i = 0; i < v.size(); i++) {
        cout << v[i] << " ";
    }
    cout << endl;
}

int main(void) {
    srand((int)time(NULL));

    int numberOfInput = 0;

    cout << "How many Inputs? : ";
    cin >> numberOfInput;

    vector<int> v;

    for (int i = 0; i < numberOfInput; i++) {
        v.push_back(rand() % 10 + 1);
    }

    Print(v);
    sort(v.begin(), v.end(), greater<int>());
    Print(v);

    return 0;
}

#include<iostream>
#include<ctime>
#include<algorithm>
#include <vector>
using namespace std;

int main(void) {
    int numberOfInput = 0;

    cout << "How many Inputs? : ";
    cin >> numberOfInput;

    int* arr = new int[numberOfInput];

    for (int i = 0; i < numberOfInput; i++) {
        cout << "arr[" << i << "] : ";
        cin >> arr[i];
    }

    sort(arr, arr + numberOfInput, greater<int>());

    for (int i = 0; i < numberOfInput; i++) {
        cout << arr[i] << " ";
    }
    return 0;
}

3. compare 함수를 만들어서 sort : 오름차순

#include<iostream>
#include<ctime>
#include<algorithm>
#include <vector>
using namespace std;

class Point {
public :
    int x;
    int y;
    Point() {
        x = 0;
        y = 0;
    }
    Point(int a, int b) {
        x = a;
        y = b;
    }
};

bool comparePoint(Point a, Point b) {
    if (a.x == b.x)
        return a.y < b.y;
    else
        return a.x < b.x;
}

int main(void) {
    int numberOfInput = 0;

    cout << "How many Inputs? : ";
    cin >> numberOfInput;

    Point* pointArr = new Point[numberOfInput];

    for (int i = 0; i < numberOfInput; i++) {
        cout << "Point [" << i << "] : ";
        int x, y;
        cin >> x >> y;
        pointArr[i] = Point(x, y);
    }

    sort(pointArr, pointArr + numberOfInput, comparePoint);

    for (int i = 0; i < numberOfInput; i++) {
        cout << pointArr[i].x << ", " << pointArr[i].y << endl;
    }
    return 0;
}

기본적으로 x값 오름차순으로 하되, x 값이 같을 경우 y 값을 오름차순으로 정렬한다.