정렬알고리즘 검색 결과

해당 글 7건
stable sort : 우선 순위가 같은 데이터들은 어떻게 정렬될까요?

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

정렬 알고리즘 시리즈를 쓰려고 합니다. 총 20 ~ 25편 정도로 구성이 될 듯 싶습니다. 먼저 O(n^2)짜리 알고리즘 3대장을 써 볼 건데요. 아마도, 알고리즘 교재에서는 맨 처음에 나올 듯 싶습니다. 오늘은 그 중, 삽입 정렬에 대해서 알아보겠습니다. 이 글을 이해하기 위해서는 memcpy와 memmove를 이해하면 더없이 좋을 겁니다. [관련글] 메모리 복사 함수는 어떻게 쓸까요? 삽입정렬 알고리즘은 Loop를 돌면서 해당 원소가 이미 정렬된 부분 배열에서 어디로 들어가면 좋은지를 구한 다음에, 그 위치에 넣는 식으로 동작합니다. [6, 3, 4, 2, 1, 3]을 오름차순으로 정렬한다고 해 봅시다. 수가 작을수록 우선 순위가 높을 겁니다. 먼저 1회전을 돌 겁니다. 6을 선택합니다. 제가 파란색..
자료알고/알고리즘 2019. 7. 11. 11:44