[코테정리] C++ 정렬문제

sort 사용

크기 비교가 가능한 형들에 대한 모든 정렬을 적용할 수 있다. (int, char, string 등)

#include <iostream>
#include <algorithm>

using namespace std;

int main(){

    int arr[5];
    arr[0] = 0;
    arr[1] = 4;
    arr[2] = 3;
    arr[3] = 1;
    arr[4] = 5;
    sort(arr, arr + 5);

    for (int i = 0; i < 5; i++)
        cout << arr[i] << endl;

    return 0;
}

https://www.acmicpc.net/blog/view/22

STL sort 튜토리얼

인덱스번째 정렬하기

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int nn;
bool cmp(string a,string b){
    if(a.at(nn)!=b.at(nn)){
        return a.at(nn)<b.at(nn);
    }
    else return a<b;
}
vector<string> solution(vector<string> strings, int n) {
    vector<string> answer;
    nn=n;
    sort(strings.begin(),strings.end(),cmp);
    answer=strings;
    return answer;
}

프로그래머스 LV1 - 문자열 내 마음대로 정렬하기

정렬하고 싶은 요소의 인덱스를 전달시키면된다.

 

 

중복된 것 제거

#include <vector>
#include <iostream>

using namespace std;

vector<int> solution(vector<int> arr) 
{
    vector<int> answer;
    answer.push_back(arr[0]);
    for(int i=1;i<arr.size();i++){
         
        if(arr[i]!=arr[i-1]) answer.push_back(arr[i]);
    }
    return answer;
}

프로그래머스 LV1 - 같은 숫자는 싫어
단순하게 앞뒤가 다르면 넣어준다.

 

버블정렬

for(int i=0;i<people.size()-1;i++){
        for(int j=i+1;j<people.size();j++){
            if(people[i]<people[j]){
                int temp=people[i];
                people[i]=people[j];
                people[j]=temp;
            }
        }
    }​

 

시간복잡도 - O(n^2) 정렬 중 젤느리다.

퀵소트

void quickSort(int i, int j)
{
	if(i>=j) return;
	int pivot = quick[(i+j)/2];
	int left = i;
	int right = j;
	
	while(left<=right)
	{
		while(quick[left]<pivot) left++; //내림차순하고싶으면 >
		while(quick[right]>pivot) right--; //내림차순하고싶으면 <
		if(left<=right)
		{
			swap(quick[left],quick[right]);
			left++; right--;
		}
	}
	quickSort(i,right);
	quickSort(left,j);
}​

#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;
int arr[5000001];
int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	int n, k;
	cin >> n >> k;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}
	nth_element(arr, arr + k, arr + n);
	cout << arr[k-1];
}

시간복잡도 - O(nlogn)
nth_element를 이용하여 퀵소트를 응용한 STL라이브러리 정렬함수
부분적으로 정렬시키는 함수이다.
K번째 자리가 확정날 때 까지만 정렬을 진행한다.