목록Computer Science/알고리즘 (10)
DNF LOVE
정렬 알고리즘의 세 번째 이야기, 퀵 정렬(Quick Sort) 3. 정렬 알고리즘(Sorting Algorithm)의 모든 것 ③ - 퀵 정렬(Quick Sort) : 퀵 정렬은 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속한다. 퀵 정렬은 분할 정복 방법을 통해 리스트를 정한다.1. 리스트 가운데서 하나의 원소를 고른다. 이렇게 고른 원소를 '피벗'이라고 한다.2. 피벗 앞에는 피벗보다 값이 작은 모든 원소들이 오고, 피벗 뒤에는 피벗보다 값이 큰 모든 원소들이 오도록 피벗을 기준으로 리스트를 둘로 나눈다. 이렇게 리스트를 둘로 나누는 것을 분할이라고 한다. 분할을 마친 뒤에 피벗은 더 이상 움직이지 않는다.3. 분할된 두 개의 작은 리스트에 대해 재귀(Recursion)적으로 이 과정을 ..
2. 정렬 알고리즘(Sorting Algorithm)의 모든 것 ② - 선택정렬 : 선택 정렬(Selection Sort)은 다음과 같은 순서로 이루어진다. (출처 - 위키백과)1. 주어진 리스트 중에 최소값을 찾는다.2. 그 값을 맨 앞에 위치한 값과 교체한다.3. 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다. - 선택정렬 역시 버블 정렬과 동일하게 최악의 경우일 때 O(n^2)만큼의 시간복잡도를 갖는다.- 버블정렬과 동일하게 쉬운 개념의 알고리즘이며, 사용할 수 있는 메모리가 제한적인 경우에 사용 시 성능 상의 이점이 있을 수 있다. > 인덱스 크기가 9이고 각 인덱스에 정렬되지 않은 정수가 들어있는 배열이 있다고 했을 때, 이런식으로 마지막 하나의 원소가 남을 때 까지 반복하다 보면 ..
정렬 알고리즘은 알고리즘 중에서도 가장 기초적인 개념이다. 정렬 알고리즘에는 다양한 것이 있는데 대표적으론 버블, 선택, 퀵, 힙, 병합정렬이 있다. 1. 정렬 알고리즘(Sorting Algorithm)의 모든 것 ① - 버블정렬 : 버블정렬은 정렬 알고리즘 중에 가장 이해하기 쉬운 개념이지만 시간복잡도가 O(n^2)이기도 하고 실전에서 좋은 성능을 내지 못하기 때문에 잘 사용되지 않는다. 그러나 학부생이라면 과제할 때 정렬이 필요하다면 외워놓고 바로바로 쓸 수 있는 쉬운 정렬이기 때문에 한 번쯤은 봐주면 좋을 것이다. > for문은 총 2번 돌기 때문에 시간 복잡도는 O(n^2)으로 굉장히 비효율적인 알고리즘이다. >** 장점 - 구현하기 쉽다- 이해하기 쉽다** 단점- 특정 요소가 최종 정렬 위치에 ..