정렬

정렬 알고리즘은 앞선 게시물에서 다양하게 배웠고, 또한 그보다 많은 수의 알고리즘이 존재하기도 한다. 이러한 알고리즘을 사용해서 정렬을 수행하는 것도 좋지만 많은 경우에서 파이썬에서 기본적으로 제공하는 정렬 알고리즘을 사용하는 편이 유리할 수 있다. - 파이썬은 기본 정렬 라이브러리인 sorted() 함수를 제공한다. 이는 퀵 정렬과 비슷한 정렬 방식인 병합 정렬을 기반으로 만들었는데 일반적으로 퀵 정렬보다는 느리지만 최악의 경우에서도 O(NlogN)을 보장한다는 장점을 가지고 있다. sorted() 함수는 리스트, 딕셔너리, 집합 자료형 등을 입력받아서 정렬된 리스트를 반환한다는 특징을 가지고 있다. 리스트 = sorted(정렬하려는 자료형) - 이와는 조금 다르게 리스트에서 내부적으로 정렬을 수행하는..

계수 정렬 (Count Sort) 은 매우 빠른 정렬 알고리즘이다. 그러나 한 가지 치명적인 약점이 있는데 바로 특정한 조건이 부합할 때만 사용할 수 있다는 것이다. 그 약점은 바로 '데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때만 사용가능하다' 라는 것이다. 만약 데이터가 무한한 범위를 가질 수 있는 실수형 데이터라면 이 계수 정렬을 사용하기 힘들다는 것이다. 또한 일반적으로 가장 작은 데이터와 가장 큰 데이터의 값의 차이가 1,000,000을 넘지 않을 때 효과적으로 사용할 수 있다. 계수 정렬은 일반적으로 별도의 리스트를 선언하고 그 안에 정렬에 대한 정보를 담는다는 특징이 있다. 즉, 앞서 다루었던 정렬 알고리즘과는 다르게 직접 데이터의 값을 비교한 뒤에 위치를 변경하는 정렬 방식..

퀵 정렬 (Quick Sort) 는 매우 빠른 정렬 알고리즘으로 널리 알려져 있으며 대부분 프로그래밍 언어에서 정렬 라이브러리의 근간이 되는 알고리즘이다. 퀵 정렬이란 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방식으로 정렬을 진행하는 알고리즘이다. 퀵 정렬에서는 기준이 필요하다. 이 기준은 피벗 (Pivot) 이라고 부른다. 먼저 피벗을 설정하고 피벗보다 큰 수와 작은 수를 교환한 후 리스트를 반으로 분할하는 방식으로 진행된다. 피벗을 선정할 때는 명확한 기준이 필요하고 그 기준을 명시해야 한다. 리스트의 첫 번째 데이터를 피벗으로 설정하는 호어 분할 (Hoare Partition) 방법으로 퀵 정렬을 이해한다. 먼저 아래와 같은 데이터가 있다고 가정한다. 5 7 9 ..

삽입 정렬 (Insertion Sort) 는 데이터를 하나씩 확인하며 각 데이터를 적절한 위치에 삽입하여 정렬하는 알고리즘이다. 따라서 삽입 정렬 또한 선택 정렬과 마찬가지로 직관적으로 동작원리를 이해하기 쉬운 알고리즘이라고 할 수 있다. 삽입 정렬은 선택 정렬에 비해 구현 난이도가 다소 높은 편이지만 실행시간 측면에서 더 효율적인 알고리즘으로 알려져 있다. 또한 필요할 때만 위치를 바꾸기 때문에 '데이터가 거의 정렬 되었을 때' 사용하면 그 효율은 배가 된다. 삽입 정렬은 특정한 데이터가 적절한 위치에 들어가기 이전에 그 앞까지의 데이터는 이미 정렬되어 있다고 가정한다. 아래와 같은 데이터를 삽입 정렬을 통해서 정렬하는 모습을 보자. 7 5 9 0 3 1 6 2 4 8 삽입 정렬은 두 번째 데이터부터 ..

먼저 코딩 테스트의 중요 알고리즘 중 하나인 정렬에 대해서 알아보자. 정렬이란 말 그대로 데이터를 특정한 기준에 따라서 순서대로 나열하는 것을 의미한다. 프로그램에서 주어진 데이터를 정렬하고 사용하는 경우가 많기 때문에 프로그램을 작성할 때 자주 사용되는 알고리즘 중 하나이다. 또한 정렬 알고리즘이 중요한 이유 중 하나는 이진 탐색의 전처리 과정이기 때문이다. 선택 정렬 (Selection Sort) 란 데이터가 무작위로 나열되어 있을 때, 이 중에서 가장 작은(혹은 가장 큰) 데이터를 가장 앞의 데이터와 바꾸고, 두 번째로 작은 데이터를 두 번째에 위치한 데이터와 계속 바꾸는 방법으로 데이터를 정렬하는 알고리즘이다. 선택 정렬은 가장 원시적인 방법으로 매번 '가장 작은 데이터를 선택한다'는 의미에서 이..