[백준] 정렬

<< 내용 >> 

1. sort(begin,end)

    1) array 정렬 : sort(a,a+n);//a[0] ~a[n-1]까지 정렬

    2) vector 정렬: sort(a.begin(),a.end());

2. compare함수

   1) sort함수의 3번째 인자로 함수 이름을 넘김

   2) const,  & 붙일 것

 

3.stable sorting(안정 정렬)

    1) 같은 것이 있는 경우, 정렬하기 전 순서가 유지되는 정렬 알고리즘

    2) merge sort(NlogN),bubble sort(N^2) 혹은 stable_sort STL 으로 구현 가능

    3) 예제(나이순 정렬)

        -가입자들의 나이와 이름이 가입한 순서대로 주어질 때, 나이 순으로 정렬(나이가 같으면 먼저 가입한 사람이 오게 정렬)

        -유의: 가입한 순서는 입력으로 들어오지 않기 때문에, 따로 저장해야 함

        -풀이: stable_sort(v.begin(),v.end(),compare);

                 compare(const Person& a, const Person& b) { return a.age < b.age; }

 

<<예제>>

 1. 국영수

1) 문제

 - 국어 점수 내림차순, 국어 같으면 영어 오름차순, 국어 영어 같으면 수학 내림차순, 모든 점수가 같으면 이름 사전 순(대문자는 사전 순 앞)

 

 

2) 구현 유의 사항

 - 구조체 입력 받아서 벡터에 삽입하는 법

• Person a; 으로 선언 후 cin >> a.age>>a.name; 으로 입력 받아 v.push_back(a); 으로 벡터에 삽입

• vector<Person> v(n) (n)써서 처음부터 메모리 할당!! //cin >> v[i].age>>v[i].name으로 바로 받을 수 있음

  - tuple이용한 compare 함수 만드는 법(#include<tuple>) : a.kor 하면 자동으로 내림차순 정렬 됨

 

2. 수 정렬하기3

1)문제

-N개의 수를 정렬하시오(단, N은 10,000,000개 주어짐, 값은 10000이하)

 

2) 유의 사항 & 핵심

- N의 범위가 크고, 값이 작으면 개수를 세는 방식으로 정렬하기

- cnt[10001]; ///   cin >> num;   ///   cnt[num]++;  /// 후에 횟수만큼 출력

 

 

3. 카드

1)문제

- 가장 많이 가지고 있는 카드의 번호를 구하라

 

2) 유의 사항 & 핵심

- 가장 많이 가진 숫자 구하기 => 정렬 후 연속된 숫자 횟수 cnt 하기

-실수한 부분: for문으로 cnt구할 때, 젤 마지막 원소도 비교할 것!! (for문 나오고 다시 한번 cnt값 비교)

4. K번째 수

1)문제

- N개 수가 주어질 때, 정렬 후 앞에서 K번째에 있는 수를 출력하라

- 숫자 개수 N(5,000,000 이하), 수의 값은 -10^9~10^9사이

 

2) 유의 사항 

* nth_element함수(알고리즘 헤더) : 정렬 후 n번째 요소를 알려줌. 해당 자리가 확정날 때까지만 정렬을 진행    

    - nth_element(v.begin(), v.begin()+ v.size()/2, v.end()); // 벡터 내 중간 값을 반환 

    -nth_element(a,a+k,a+n) // array의 k+1번째 값을 반환, index는 0부터 (두번째 값을 찾고 싶으면 k=1 )

 

 

5. 버블 소트

1)문제

- 버블 소트가 총 몇 단계로 이루어져 있는지를 구하라

 

2) 핵심

버블 소트는 한번 진행될 때마다 각 숫자 좌측으로 한칸씩 이동이 가능