Code Playground

< h1 > Code Playground </ h1 >

Quick Sort 퀵 정렬은 1960년에 찰스 앤터니 리처드 호어(C.A.R hoare)가 처음 제안한 방법으로 이후 많은 사람들이 수정 보완하여 완성된 정렬 알고리즘이다. 이 알고리즘은 처음 소개된 이후로 반세기가 넘었지만 현존하는 가장 빠른 정렬 알고리즘 중에 하나이다. 퀵 정렬은 in place 방법과 in place가 아닌 방법 2가지가 있는데 실제로 많이 쓰이는 방법은 메모리 사용량이 적은 in place 방법이다. 그러나 in place가 아닌 방법이 더 직관적으로 이해하기 쉬우므로 이 방법을 먼저 정리하고 그 다음 in place 방법을 정리하겠다. Basic Quick Sort - Not In Place 퀵 정렬은 지난번 병합 정렬 포스팅에서 소개한 Divide and Conquer 전략..

Merge Sort 병합 정렬 혹은 합병 정렬이라고 불리는 Merge Sort는 데이터들을 잘게 쪼갠 다음에 하나로 합치는 과정에서 정렬하는 방법이다. 요즘은 데이터를 USB같은 장치로 저장하는 것이 일반적이었으나 아주 옛날에는 테이프를 이용해서 저장했다. 테이프 드라이브에 저장된 데이터를 정렬하는 일은 매우 어려운 일이었다. 왜냐면 테이프 드라이브는 항상 데이터를 처음부터 순차적으로 읽어야 한다는 특징이 있기 때문이다. 이러한 테이프 드라이브의 문제점 때문에 병합 정렬 알고리즘이 탄생하였다. 병합 정렬은 위의 그림처럼 데이터를 절반씩 쪼개는 divide 작업을 먼저 하는데 이 작업은 데이터가 하나만 남을 때까지 반복한다. 그 후에 하나씩 쪼개진 데이터를 정렬을 하면서 다시 그룹화한다. 이런 과정은 아래..

Sorting Algorithm 무작위로 섞여있는 데이터를 어떤 기준에 맞춰 정렬하는 알고리즘은 여러 가지가 있다. 정렬 알고리즘은 다양한 경우에 매우 유용하게 사용된다. 각종 데이터 목록을 정리하고 싶을 때 분포도의 중위값을 알아내고 싶을 때 데이터에서 중복값을 잡아내고 싶을 때 이진 탐색을 하고 싶을 때 사실 내가 공부하는 자바스크립트에 sort()라는 메소드가 이미 존재하듯이, 모든 프로그래밍 언어에는 자체적인 정렬 메소드가 있다. 그럼에도 불구하고 우리가 정렬 알고리즘을 배워야하는 이유는 시스템 정렬이 항상 좋은 퍼포먼스를 보장하지 않기 때문이다. 또한 내가 가진 데이터베이스의 양이나 상황에 따라 어떤 정렬을 사용하는 것이 좋을지 달라지기 때문에 우리는 기본적으로 유명한 정렬 알고리즘들은 반드시 ..