sort()

sort()

범위 내 배열의 값을 오름차순으로 정렬한다.

구문

#include <algorithm>

sort(s.begin(), s.end());
sort(s.begin(), s.end(), Compare comp);

sort (arr, arr + arr의 길이);
sort (arr, arr + arr의 길이, Compare comp);

반환값

반환값은 없습니다. 배열이 재정렬될 뿐입니다.

Compare comp

세 번째 인자로 들어가는 함수를 통해 정렬 순서를 정할 수 있습니다.

bool compareLength(string a, string b)
{
    return a.length() < b.length();
}

sort(arr, arr + 배열의 길이, compareLength);

위 예제는 배열의 처음부터 끝까지의 범위 내에서 compareLength의 기준으로 정렬하는 것입니다.

comp의 반환값에 따른 정렬

comp => true : a가 b보다 앞에 있다. (index가 빠르다.)
comp => false : a가 b보다 뒤에 있다. (index가 느리다.)

시간 복잡도

quick sort(퀵 정렬)을 기반으로 함수가 구현되어있어, 평균 시간복잡도는 n log n 입니다.

백준 1181번 예제 코드

#include <iostream>
#include <algorithm>
#include <string>

using namespace std;

bool compareLength(string a, string b)
{
    return a.length() < b.length();
}

bool compareAlphabet(string a, string b)
{
    if (a.length() < b.length())
        return true;
    else if (a.length() > b.length())
        return false;
    else
    {
        for (int i = 0; i < a.length(); i++)
        {
            if (a[i] < b[i])
                return true;
            else if (a[i] > b[i])
                return false;
            else
                continue;
        }
        return false;
    }
}

int main()
{
    int count;
    cin >> count;

    string arr[count];
    for (int i = 0; i < count; i++)
    {
        cin >> arr[i];
    }

    sort(arr, arr + count, compareLength);
    sort(arr, arr + count, compareAlphabet);

    for (int i = 0; i < count; i++)
    {
        if (arr[i] == arr[i - 1])
            continue;
        else
        {
            cout << arr[i] << "\n";
        }
    }

    return 0;
}