개발/C 언어 (2) 썸네일형 리스트형 [알고리즘] 퀵 정렬 (Quick Sort) 1. 퀵 정렬(Quick Sort)이란? Pivot(축) 값을 기준으로 연속적으로 분할하며 정렬하는 기법으로 pivot 값을 중심으로 pivot보다 작은 값은 왼쪽으로, pivot보다 큰 값은 오른쪽에 배열시키며 정렬이 완료될 때까지 반복적으로 수행한다. 2. 알고리즘 1) 리스트 가운데서 하나의 원소를 고른다. 이렇게 고른 원소를 피벗이라고 한다. 2) 피벗 앞에는 피벗보다 값이 작은 모든 원소들이 오고, 피벗 뒤에는 피벗보다 값이 큰 모든 원소들이 오도록 피벗을 기준으로 리스트를 둘로 나눈다. 이렇게 리스트를 둘로 나누는 것을 분할이라고 한다. 분할을 마친 뒤에 피벗은 더 이상 움직이지 않는다 3) 분할된 두 개의 작은 리스트에 대해 재귀(Recursion)적으로 이 과정을 반복한다. 재귀는 리스트의.. [알고리즘] 선택 정렬 (Selection Sort) 1. 선택 정렬(Selection Sort)이란? 전체 데이터들 중에서 기준 위치에 맞는 데이터를 선택하여 자리를 교환하는 방식의 정렬 기법이다. 2. 알고리즘 1) 주어진 리스트 중에 최소값을 찾는다. 2) 그 값을 맨 앞에 위치한 값과 교체한다. 3) 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다. 4) 위 과정을 (데이터 수 - 1)번 반복 비교하는 것이 상수 시간에 이루어진다는 가정 아래, n개의 주어진 리스트를 이와 같은 방법으로 정렬하는 데에는 Θ(n2) 만큼의 시간이 걸린다. 선택 정렬은 알고리즘이 단순하며 사용할 수 있는 메모리가 제한적인 경우에 사용시 성능 상의 이점이 있다. 3. 선택 정렬 예제 배열에 9, 5, 7, 3, 1이 들어 있다고 가정하고 정렬해 보자. 첫번째 :.. 이전 1 다음
