이 글은 인프런의 영리한 프로그래밍을 위한 알고리즘 강좌를 듣고 정리한 내용입니다. Quick Sort(퀵 정렬)퀵 정렬은 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속한다.n개의 데이터를 정렬할 때, 최악의 경우에는 O(n^2)번 비교를 수행하고, 평균적으로 O(nlogn)번의 비교를 수행한다. 퀵 정렬은 분할 정복 방법을 통해 리스트를 정렬한다.1. 리스트 가운데 하나의 원소를 고른다. 이렇게 고른 원소를 피벗이라고 한다.2. 피벗 앞에는 피벗보다 작은 모든 원소들이 오고, 피벗 뒤에는 피벗보다 값이 큰 모든 원소들이 오도록 피벗을 기준으로 리스트를 둘로 나눈다. 이렇게 리스트를 둘로 나누는 것을 분할이라고 한다. 분할을 마친 뒤에 피벗은 더 이상 움직이지 않는다.3. 분할된 두 개의 작은..
이 글은 인프런의 영리한 프로그래밍을 위한 알고리즘 강좌를 듣고 정리한 내용입니다. Merge Sort(병합 정렬)분할 정복법(Merge Sort, Quick Sort)분할 : 해결하고자 하는 문제를 작은 크기의 동일한 문제들로 분할정복 : 각각의 작은 문제를 순환적으로 해결합병 : 작은 문제의 해를 합하여(Merge) 원래 문제에 대한 해를 구함 1. 리스트의 길이가 0 또는 1이면 이미 정렬된 것으로 본다. 그렇지 않은 경우2. 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.3. 각 부분의 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다.4. 두 부분의 리스트를 다시 하나의 정렬된 리스트로 합병한다. 의사코드 Merge Sort(A[], p, r) { // 배열 A[p...
이 글은 인프런의 영리한 프로그래밍을 위한 알고리즘 강좌를 듣고 정리한 내용입니다. Bubble Sort(거품 정렬)거품 정렬은 두 인접한 원소를 검사하여 정렬하는 방법이다. 시간 복잡도가 로 상당히 느리지만,코드가 단순하기 때문에 자주 사용된다. 출처 : 위키 백과 예제[4, 54, 2, 8, 63, 7, 55, 56] [4, 2, 8, 54, 7, 55, 56, 63] [2, 4, 8, 7, 54, 55, 56, 63] [4, 2, 54, 8, 63, 7, 55, 56] [2, 4, 8, 54, 7, 55, 56, 63] [2, 4, 7, 8, 54, 55, 56, 63]pass3[4, 2, 8, 54, 63, 7, 55, 56] [2, 4, 8, 7, 54, 55, 56, 63]pass 2[4, 2..
이 글은 인프런의 영리한 프로그래밍을 위한 알고리즘 강좌를 듣고 정리한 내용입니다. Selection Sort(선택 정렬)선택 정렬은 제자리 알고리즘의 하나로, 다음과 같은 순서로 이루어진다.1. 주어진 리스트 중에 최솟값 or 최대값을 찾는다.2. 그 값을 맨 앞 or 맨 뒤에 위치한 값과 교체한다.3. 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다. 비교하는 것이 상수 시간에 이루어진다는 가정 아래, n 개의 주어진 리스트를 이와 같은 방법으로 정렬하는 데에는 Θ(n2) 만큼의 시간이 걸린다. 출처 : 위키 백과 예제 [4, 54, 2, 8, 63, 7, 55, 56] -> initial array [4, 54, 2, 8, 56, 7, 55, 63] -> after 1st swap [4,..