sea5727   1년 전

랜덤한 배열이 있습니다 a[2][10] 입니다


quick소팅을 구현하긴했는데 조금 까다로운 조건이 있어서 글을 올립니다.


먼저 되어야할 소팅은 a[i][1]의 값들입니다.  그후에 a[i][1]의 값이 동일할때는 a[i][0] 의 값을 기준으로 소팅이 되어야 합니다.


어떤식의 알고리즘을 구현해야할까요?


저는 먼저 a[i][1] 을 소팅을 한후에 

(ex : { 5, 5} { 3, 5} {10,7} {6 , 11} { 7 , 11} ... 1열의 숫자만으로 소팅을 먼저함) 

a[i][1]의 값이 중복이되어 나열된다면 a[i][0]을 기준으로 소팅되게 했습니다. 그런데 시간초과가 나더라구요

(ex: 처음부터 a[i][1] 의 값이 같은 첫index와 끝index를 구해서 소팅시킴.. 같은글자가 없이 한번만되면 넘어가도록함)


너무 탐색을 오래하는거같긴한데 어떤식으로 알고리즘을 짜야할까요?

(아무래도 문자열소팅과 비슷한 느낌인데 어떤 식으로 알고리즘을 작성해야하나요???)


dreamsboat   1년 전



pair<int, int> 를 first , 만약 같으면 second 로 sorting 하고싶으시다는건가요??


bool cmp (pair<int,int> p, pair<int,int> q)

{

return p.first < q.first || (p.first == q.first && p.second < q.second);

}


sort(v.begin(), v.end(), cmp);

where v is vector<pair<int, int> >


엄청 별거아닌데 이게아니라면 삭제할게요..~!

sea5727   1년 전

C++ 은 대단하네요.. ㅠ_ㅠ


C로 저런거 지원없이 코딩하려면


먼저 한쪽꺼부터 소팅시켜놓은후에 반대편꺼중에 같은거범위지정해서 소팅하는식으로 하는게 정석이겠죠?


한쪽거 소팅하면서 나머지 반대꺼까지 동시에 맞출수는 없는거겠죠?

lsc4719   1년 전

이산수학 책에 있는 Relation 부분을 읽어보신 뒤,

Totally ordered set에 관한 내용을 찾아보시면 문제를 해결하실 수 있을 것 같습니다.

---

'Comparison based' sorting 알고리즘을 구현하시기 위해선,

Comparison 연산이 무엇인지 정의해주셔야 합니다.

Comparison 연산은 보통 < (strict weak order)로 정의됩니다.

Totally ordered set 만이 sorting 가능하다고 알고있습니다.

methylene   1년 전

long long int 타입의 배열을 만들어 거기에

시작시간은 1 ~ 32 번 비트를 이용해 계산하고

끝나는 시간은 33 ~ 64 번 비트를 이용해 계산한 값을 더해 넣어준 후 그걸 기준으로 한꺼번에 소팅을 하면 해결될 겁니다.

ex)

long long arr[100001];

arr[i] = a[i][0] + pow(2.0, 32) * a[i][1];

이런 식으로 배열에 값을 저장한 후에 이걸 정렬 기준으로 잡는 겁니다.(정렬 기준인 배열도 정렬 하고자 하는 배열과 함께 정렬해야합니다.)

참고로 pow는 math.h 헤더파일에 들어있는 거듭제곱 함수입니다.


methylene   1년 전

시작시간 + 끝나는 시간 *2^32을 배열에 저장하고

주의 할점은 배열이 long long 이므로 함수의 (배열) 파라미터와 정렬할 때의 temp값, pivot값들을 long long으로 해야 한다는 것입니다.

배열 파라미터를 받기 싫으시면 그냥 전역 변수로 선언하는 방법도 있습니다.

댓글을 작성하려면 로그인해야 합니다.