정렬 알고리즘 썸네일형 리스트형 [정렬 알고리즘] 퀵 소트(Quick Sort) 퀵 소트는 이름 그대로 빠른 성능을 제공하는 정렬 알고리즘입니다.평균적으로 O(n log n)으로, 최악의 경우 O(n2)의 시간 복잡도를 보입니다.기본적인 방식은 아래와 같습니다. 리스트에서 원소를 한 개 선택하는데 이 원소를 피벗(Pivot)이라고 부릅니다. 피벗이 선정되면 피벗보다 작은 값들은 피벗의 좌측에, 큰 값들은 우측에 위치시킵니다. 피벗은 자신의 자리를 찾았으므로 고정되며 좌우의 작은 값들과 큰 값들을 다시 재귀로 반복합니다. 이런 식으로 피벗의 위치를 전부 찾아주게 되면 결과적으로 정렬된 리스트가 됩니다.피벗은 다양한 방법으로 선택이 가능한데 보통 가장 앞의 원소나 가장 뒤의 원소를 선택해서 진행합니다.다음 코드는 가장 뒤의 원소를 피벗으로 선택하는 퀵 소트 코드입니다. #include .. 더보기 [정렬 알고리즘] 삽입 정렬(Insertion Sort) 정렬 알고리즘인 삽입 정렬입니다.배열의 앞쪽부터 시작해서 순회하면서 정렬을 합니다.그리고 앞 부분의 정렬된 부분에서 선택된 값의 위치를 찾아서 이동시키는 알고리즘입니다.기본적으로 버블 소트나 선택 정렬보다 성능이 좋고 구현이 간편한 장점이 있는 정렬입니다.또한 추가적인 메모리가 크게 필요 없는 In-Place 알고리즘입니다.반복문을 돌리기 위한 변수와 swap을 위한 변수 정도가 추가로 필요합니다.그리고 같은 값이 있을 때 그 순서가 변경되지 않는 안정 정렬입니다.Wiki에서 확인할 수 있는 삽입 정렬의 정렬 방식입니다.http://en.wikipedia.org/wiki/Insertion_sort이 영상이 삽입 정렬의 모든 것을 보여주고 있습니다.두 번째 값부터 시작해서 각각의 값들이 앞부분의 정렬된 부.. 더보기 [정렬 알고리즘] 버블 소트(거품정렬) 버블 소트는 정렬 알고리즘의 한 종류입니다. 정렬 알고리즘은 무작위로 있는 정보를 순차적으로 재배치 시키는 것이 목적입니다. 버블 소트는 각종 정렬 알고리즘 중에서도 기본으로 여겨지는 알고리즘입니다. 정렬 알고리즘은 퀵 정렬, 삽입 정렬, 힙 정렬, 선택 정렬 등 여러가지 방법이 존재합니다. 보통은 속도가 빠른 퀵소트를 많이 사용합니다. 퀵소트를 구현하는데는 재귀 함수 방식이 많이 활용됩니다. 재귀 함수에 대한 설명은 아래 링크에서 확인 가능합니다.2014/12/04 - [Programming/C&C++] - 재귀 함수 & 재귀적 함수호출(recursive function call)그럼 본격적으로 버블 소트에 대해서 알아보도록 하겠습니다. 만약 버블 소트의 코드만 필요하다만 가장 하단의 코드를 참조하시면.. 더보기 이전 1 다음
