Algorithms, Part 1/3주차

Sorting applications Java system sorts 자바에도 정렬 함수가 내장되어 있습니다(파이썬도 당연히..! 심지어 성능도 좋아요). quick/merge sort 두 종류가 포함되어 있는데, 객체의 종류에 따라 다른 정렬을 사용한다고 합니다. 예를 들어 reference type에는 merge sort가 사용됩니다. 반대로 메모리가 적게 필요하고 in-place 변화가 적용되는 경우에는 quick sort가 사용됩니다. War story (C qsort function) Enginerring a system sort Tukey's ninther 중간값의 중간값을 고르는 방법을 제안한 학자입니다. 이 방식은 랜덤하게 값을 섞는것보다 구분 효과가 탁월하고 비용은 덜 소모한다고 합니다...

Duplicate keys 일반적으로 대량의 데이터에 대해 정렬을 수행하는 것은 중복되는 key를 기준으로 정렬을 적용하는 경우가 많습니다. 위처럼 '도시 - 시간' 형태의 데이터라면 도시를 기준으로 정렬하게 되는 것이죠. 원래는 중복된 key를 포함하는 데이터에 대해 퀵정렬을 수행하는 경우 quadratic(2차) 시간이 걸린다는 문제점이 있었으나, 병합 정렬을 이용하여 그 시간을 획기적으로 줄일 수 있게 되었죠. Duplicate keys: the problem 하지만 일반적인 병합 정렬 방식을 적용하게 되면, key가 모두 동일한 경우에 대해서는 quadratic 시간이 소요될 것입니다. 이를 방지하기 위해 paritioning item(기준 아이템)과 동일한 것이 확인되는 순간 작업을 멈춰서 Nl..

Selection 이번에는 '선택'과 관련한 문제입니다. 만약 어떤 배열에서 '최소/최대'의 값을 구해야 한다면 배열을 한 번만 쭉 훑으면서 최소/최대의 값을 저장하면 되기 때문에 선형 시간이 필요할 것입니다. 즉, N만큼의 시간이 소요되죠. 하지만 배열에서 k번째의 값을 구하려면 이는 단순히 한 번 훑어보는 것으로 판단할 수 있는 문제가 아니게 됩니다. 정렬 후 k번째 값을 가져오면 되지만 이는 linearithmic, 즉 NlogN만큼의 시간이 필요한 작업입니다. 뭔가 비슷한듯 비슷하지 않은 두 방식에 대해서, 후자도 선형 시간으로 처리할 수 있지 않을까? 라는게 과거 학자들의 궁금증이었습니다. Quick-select import random def partition(a, lo, hi): i, j =..

Quicksort 퀵정렬의 기본 개념은 다음과 같습니다. 우선 배열을 무작위로 섞고, 좌우 구간으로 나눕니다. 하나(i)는 왼쪽에서 오른쪽으로 이동하고, 나머지(j)는 오른쪽에서 왼쪽으로 이동합니다. i는 기준(partitioning element)보다 큰 값이 나오면, j는 기준보다 작은 값이 나오면 이동을 멈춥니다. 두 값을 교환합니다. 위 과정을 반복합니다. 퀵정렬은 합병 정렬이 그 자체로 수행되기 전에 분할하는 것과 달리, 퀵정렬은 분할마다 정렬이 수행된다는 차이점이 있습니다. Quicksort partitioning demo Quicksort: Java code for partitioning, Java implementation def partition(a, lo, hi): i, j = lo, ..

comparator는 comparable과 비교되는 자바의 인터페이스로 제가 이해하기엔 좀 어렵네요. 당장 자바로 알고리즘을 풀이할 것도 아니라서 과감히 패스하겠습니다! Stability 때로는 정렬 기준(key)이 여러 개가 될 수도 있습니다. 예를 들어 이름을 기준으로 정렬한 다음, 2번째 열의 숫자를 기준으로 정렬하고 싶을 수도 있다는 것이죠. 하지만 두 번째 열을 기준으로 정렬하는 순간 이름 기준의 정렬이 깨지는 것을 원하지 않을 수도 있습니다. 즉, 두 번째 정렬을 수행하더라도 기존의 정렬이 유지되길 원하는 경우 어떻게 이를 구현할 수 있을까요? Stability: insertion sort 삽입 정렬은 정렬이 수행되는 매 스텝(i)에서 이전에 정렬된 것들은 건드리지 않습니다. 비교 대상이 더 ..

Complexity of sorting 정렬 알고리즘의 계산 복잡도를 정리하는 내용입니다. 상한선은 당연히 최대치/최악의 경우를 나타내고 있으므로 guarantee라는 표현이 쓰였습니다. 하한선은 이보다 더 좋을 수 없는 최선의 경우가 증명된 것을 뜻합니다. 최적 알고리즘은 X라는 문제에 대해 최선의 것으로 증명된 경우에 해당하며 상한선과 하한선 사이에 위치합니다. Decision tree (for 3 distinct a, b, and c) 의사 결정 나무를 통해 정렬에 대한 결정을 시각화할 수 있습니다. 여기서는 각 비교를 합쳐 맨 마지막에 세 개의 값을 비교한 결과물을 얻어낼 수 있음을 보여주고 있습니다. 트리의 높이는 비교를 가장 많이 해야 하는 최악의 경우를 뜻하게 됩니다. Compare-base..