stable 검색 결과

해당 글 3건
파이썬 문자열 다중정렬 : sort가 stable 하다는 것을 이용합시다.

저번 시간에 tuple을 이용해서 다중 정렬을 손쉽게 하는 법을 배웠습니다. 특히 정수는 오름차순 반대인 내림차순으로 비교하기 위해서, 앞에 -만 붙이면 매우 간단하게 비교할 수 있어요. 그런데 문자열은 그게 되지 않습니다. 문제 상황을 보면서 어떻게 구현하면 좋을지 천천히 생각해 보도록 합시다. 개인적으로 아래 두 개의 글을 먼저 보고 오시는 게 좋아 보입니다. [관련글] tuple로 정렬 기준을 떨어트리는 방법을 알아봅시다. 안정 정렬에 대해서 알아봅시다. solution 함수를 구현해야 하는데요. list에는 튜플이 들어 있어요. 튜플의 1번째, 2번째 요소는 소문자로만 이루어진 문자열이 들어 있어요. 1차 정렬 기준은, 1번째 요소를 사전순 내림차순으로 돌립니다. 만약에, 1번째 요소가 같은 문자..
코딩/파이선 2021. 9. 24. 23:39
c언어 qsort 함수 예제 : 두 문제를 풀면서 이해해 봅시다.

알고리즘에, 정렬 시리즈를 계속 올리고 있습니다. C언어에서도, 손쉽게 빠른 정렬을 쓸 수 있는데요. 에 빠른 정렬을 하는 qsort 함수가 있습니다. 이것의 원형은 다음과 같습니다. void qsort(void *base, size_t num, size_t size, int (*compare)(const void *,const void *)); 뭔가 원형이 복잡해 보이는데요. 특히 4번째 인자가 조금 복잡해 보입니다. 이게 무엇인지 천천히 해석해 보겠습니다. 먼저 identifier를 찾을 건데요. compare입니다. 오른쪽부터 볼 건데요. (나 )를 만날 때 까지 읽어요. compare 뒤에 바로 )가 있으니까, 왼쪽을 봅니다. 보는데 *가 있네요. 즉, compare is pointer라는 겁니다..
레퍼런스/예제 2019. 8. 5. 22:23
stable sort : 우선 순위가 같은 데이터들은 어떻게 정렬될까요?

stable sort는, 정렬 알고리즘을 논할 때 간과하고 넘어가기 쉬운 키워드입니다. 하지만, 간과해서는 안 되는 것입니다. 이것이 대체 무엇을 의미할까요? 우선순위가 같은 데이터가 여러 개 있을 때, 정렬이 끝난 후에도, 순서가 유지되는 정렬을 stable sort라 합니다. 그렇지 않다면 unstable하다고 합니다. 예제를 하나 봅시다. n개의 데이터를 정렬한다고 해 봅시다. 매 회전마다 [i,e] 구간에 있는 원소들을 탐색해서, 가장 우선순위가 높은 원소가 있었던 위치를 lo라고 해 봅시다. 이 때 lo와 i에 있는 원소를 뒤바꾸는 정렬이 있다고 해 봅시다. 위에 있는 숫자는 숫자, 밑에 있는 숫자는 정렬 전 위치라고 해 봅시다. 만약에 숫자를 오름차순 정렬한다고 하면, 1이 0보다는 우선 순위..
자료알고/알고리즘 2019. 7. 14. 16:51