정렬(Sorting), Stable_Sorting

 

youtu.be/kPRA0W1kECg

 

정렬 알고리즘을 소리로 표현한 영상이다. 정렬 방법은 30가지가 넘는 여러가지가 있다., 

정렬 알고리즘의 종류로는 선택 정렬, 버블 정렬, 삽입 정렬, 퀵 정렬, 힙 정렬, 병합 정렬, ...... 등 여러가지가 있지만,

알고리즘 문제풀이에서 주로 사용하는 것들은 정렬시간이 O(NlogN)이 걸리는 정렬을 사용한다.

정렬을 직접 구현하는 것보다는 STL에 있는 sort를 사용하는 것이 좋다.

 

<연산자는 여러가지 템플릿에 오버로딩되어 있기 때문에 , 구조체나 다른 방식으로 정렬을 원 할 경우 

1. Compare 함수 만들기 2. 어나미어스 함수 3. 연산자 오버로딩 등의 방법이 있다.

template <class RandomAccessIterator>
  void sort (RandomAccessIterator first, RandomAccessIterator last);
  
template <class RandomAccessIterator, class Compare>
  void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);

sort(begin, end)를 실행하면 begin부터 end 바로 전까지 정렬을 하는 함수이다. ([begin, end)를 정렬)

//sort
//a[0]부터 a[n-1]까지를 정렬할 때
int n = 10;
int a[10] = {};
sort(a, a+n);

//vector를 정렬할 때
vector<int> a;
sort(a.begin(), a.end());

 

좌표등 두개의 수를 짝지어서 정렬 할 경우 pair을 사용하면 편하다.

int n;
scanf("%d", &n);
vector<pair<int,int>> a(n);
for(int i=0; i<n; ++i) scanf("%d%d", &a[i].first, &a[i].second);
sort(a.begin(), a.end());
for(autu p : a) printf("%d, %d", p[i].first, p[i].second);

 

위의 문제는 struct를 구현하여 해결할 수 도 있지만, 비교 함수를 만들어 줘야 한다.

struct Point {
	int x, y;
};

bool cmp(const Point &u, const Point &v) { // const와 &는 붙여야 한다.
	if(u.x < v.x) {
    	return true;
   	} else if (u.x == v.x) {
    	return u.y < v.y;
    } else {
    	return false;
    }
}
//2개이상 변수를 비교할때는 tuple를 사용하면 편하다.
#inclue <tuple>
bool cmp(const Point &u, const Point &v) {
	return make_tuple(u.x, u.y) < make_tuple(v.x, v.y);
}

vector<Point> a(n);
...
sort(a.begin(), a.end(), cmp);

여러개의 변수를 비교할 경우 tuple를 사용하면 편하다.

std::make_tuple
template< class... Types >
tuple<VTypes...> make_tuple( Types&&... args );

#include <iostream>
#include <tuple>
#include <functional>
 
std::tuple<int, int> f() // this function returns multiple values
{
    int x = 5;
    return std::make_tuple(x, 7); // return {x,7}; in C++17
}
 
int main()
{
    // heterogeneous tuple construction
    int n = 1;
    auto t = std::make_tuple(10, "Test", 3.14, std::ref(n), n);
    n = 7;
    std::cout << "The value of t is "  << "("
              << std::get<0>(t) << ", " << std::get<1>(t) << ", "
              << std::get<2>(t) << ", " << std::get<3>(t) << ", "
              << std::get<4>(t) << ")\n";
 
    // function returning multiple values
    int a, b;
    std::tie(a, b) = f();
    std::cout << a << " " << b << "\n";
}

어나미어스 함수를 사용 할 경우 좀 더 간결하게 표현 가능하다.

sort(a.begin(), a.end(), [](Point u, Point v) {
        return (u.x < v.y) || (u.x == v.x && u.y < v.y);
});

 

<연산자를 over loading 할 수도 있다. 이 경우에는 비교함수가 필요 없다.

struct Point {
	int x, y;
    bool operator < (const Point &v) const {
    	if(x < v.x) {
        	return true;
        } else if (x == v.x) {
        	return y < v.y;
        } else {
        	return false;
        }
    }
}

 

 

Stable Sorting

정렬을 할 때 같은 key값을 가진 node들이 정렬 전과 정렬 후에 순서가 뒤바뀌게 되면 그것을 ustable 정렬이라고 하며, 순서가 뒤바뀌지 않는다면 stable 정렬이라고 한다.

ex) 5(1), 4(2), 8(3), 8(4), 5(5), 3(6), 1(7), 10(8), 6(9)

 

()안의 숫자는 해당 노드가 들어 온 순서를 뜻한다. 만약 정렬 할 시에 key값을 기준으로 정렬 하되, 같은 key값을 가진 노드는 들어온 순서에 따라 정렬되어 있다면 stable 된 정보이다.

 

unstable : 선택 정렬, 퀵 정렬, 힙 정렬

stable : 버블 정렬, 삽입 정렬, 병합 정렬

 

STL에서는 stable_sort를 사용하면 된다.

template <class RandomAccessIterator>
  void stable_sort ( RandomAccessIterator first, RandomAccessIterator last );

template <class RandomAccessIterator, class Compare>
  void stable_sort ( RandomAccessIterator first, RandomAccessIterator last,
                     Compare comp );

 

입력의 개수가 클 경우 (O(NlogN)이 시간을 초과할 경우) 

변수의 가용 범위를 고려하여 배열을 만들어서 중복하여 저장하거나, map을 사용, 

부분정렬을 하여 quick selection이나 STL nth_element을 사용하는 것도 좋은 방법이다.

 

 

관련 문제 풀이

1181 단어 정렬 : https://www.acmicpc.net/problem/1181

#include <string>
#include <iostream>
#include <vector>
#include <algorithm>
#include <tuple>
#define endl '\n'
using namespace std;

int main(void) {
	int n;
	cin >> n;
	vector<string> v(n);
	for (int i = 0; i < n; ++i) 
		cin >> v[i];
	sort(v.begin(), v.end(), [](string &a, string &b) {
		return make_tuple(a.size(), a) < make_tuple(b.size(), b);
	});
	v.erase(unique(v.begin(), v.end()), v.end());
	for (string& s : v) cout << s << endl;
}