CS

[Algorithm] Sort #6 - 퀵 정렬 Quick Sort

퀵 정렬이란? Pivot을 기준으로 작은 값, 큰 값들로 나눠 정렬하는 알고리즘 시간 복잡도 최상 : \( O(n \log n) \) 최악 : \( O(n^2) \) 관련 글 [Algorithm] Sort #1 - 버블 정렬 Bubble Sort [Algorithm] Sort #2 - 선택 정렬 Selection Sort [Algorithm] Sort #3 - 삽입 정렬 Insertion Sort [Algorithm] Sort #4 - 병합 정렬 Merge Sort [Algorithm] Sort #5 - 힙 정렬 Heap Sort 평균 시간 복잡도가 \( O(n \log n) \)인 정렬 알고리즘 중 마지막은 퀵 정렬입니다. Pivot을 정한 후 두 그룹으로 나눈다는 것에서 병합 정렬과 비슷하게 보이지만..

[Algorithm] Sort #5 - 힙 정렬 Heap Sort

힙 정렬이란? 힙 자료구조의 루트를 뽑아 정렬하는 알고리즘 시간 복잡도 최상 : \( O(n \log n) \) 최악 : \( O(n \log n) \) 관련 글 [Algorithm] Sort #1 - 버블 정렬 Bubble Sort [Algorithm] Sort #2 - 선택 정렬 Selection Sort [Algorithm] Sort #3 - 삽입 정렬 Insertion Sort [Algorithm] Sort #4 - 병합 정렬 Merge Sort [Algorithm] Sort #6 - 퀵 정렬 Quick Sort 병합 정렬에 이어서 평균 시간 복잡도가 \( O(n^2) \)인 정렬 알고리즘 중 두번째는 힙 정렬입니다. 자료구조 중에서 힙(heap)의 특성을 이용해 정렬을 구현한 알고리즘입니다. 선..

[Algorithm] Sort #4 - 병합 정렬 Merge Sort

병합 정렬이란? 리스트를 분할하고 다시 역순으로 병합하면서 정렬하는 알고리즘 시간 복잡도 최상 : \( O(n \log n) \) 최악 : \( O(n \log n) \) 관련 글 [Algorithm] Sort #1 - 버블 정렬 Bubble Sort [Algorithm] Sort #2 - 선택 정렬 Selection Sort [Algorithm] Sort #3 - 삽입 정렬 Insertion Sort [Algorithm] Sort #5 - 힙 정렬 Heap Sort [Algorithm] Sort #6 - 퀵 정렬 Quick Sort 이전 글에서 소개한 버블 정렬, 선택 정렬, 삽입 정렬은 모두 평균 시간 복잡도가 \( O(n^2) \)인 알고리즘들입니다. 이제부터 소개해드릴 정렬 알고리즘들은 \( O(..

[Algorithm] Sort #3 - 삽입 정렬 Insertion Sort

삽입 정렬이란? 기준 숫자를 정렬된 리스트에 삽입해 정렬하는 알고리즘 시간 복잡도 최상 : \( O(n) \) 최악 : \( O(n^2) \) 관련 글 [Algorithm] Sort #1 - 버블 정렬 Bubble Sort [Algorithm] Sort #2 - 선택 정렬 Selection Sort [Algorithm] Sort #4 - 병합 정렬 Merge Sort [Algorithm] Sort #5 - 힙 정렬 Heap Sort [Algorithm] Sort #6 - 퀵 정렬 Quick Sort 정렬 알고리즘에 있어 기본인 버블 정렬, 선택 정렬 다음으로는 삽입 정렬입니다. 알고리즘 삽입 정렬의 알고리즘은 다음과 같습니다. 기준 값을 정한다.. 기준 값을 정렬된 원소들과 하나씩 비교해 알맞은 자리에 ..

[Algorithm] Sort #2 - 선택 정렬 Selection Sort

선택 정렬이란? 최소값 탐색 후 가장 앞 자리로 옮기며 정렬하는 알고리즘 시간 복잡도 최상 : \( O(n^2) \) 최악 : \( O(n^2) \) 관련 글 [Algorithm] Sort #1 - 버블 정렬 Bubble Sort [Algorithm] Sort #3 - 삽입 정렬 Insertion Sort [Algorithm] Sort #4 - 병합 정렬 Merge Sort [Algorithm] Sort #5 - 힙 정렬 Heap Sort [Algorithm] Sort #6 - 퀵 정렬 Quick Sort 알고리즘의 기본이라고 할 수 있는 정렬에서 두 번째는 선택 정렬입니다. 알고리즘 선택 정렬의 알고리즘은 다음과 같습니다. 리스트에서 최소값 원소를 찾는다. 최소값과 첫번째 원소의 위치를 바꾼다. (이미..

[Algorithm] Sort #1 - 버블 정렬 Bubble Sort

버블 정렬이란? 첫 번째 원소부터 인접한 두 원소를 검사하여 정렬하는 알고리즘 시간 복잡도 최상 : \( O(n^2) \) 최악 : \( O(n^2) \) 관련 글 [Algorithm] Sort #2 - 선택 정렬 Selection Sort [Algorithm] Sort #3 - 삽입 정렬 Insertion Sort [Algorithm] Sort #4 - 병합 정렬 Merge Sort [Algorithm] Sort #5 - 힙 정렬 Heap Sort [Algorithm] Sort #6 - 퀵 정렬 Quick Sort 알고리즘의 기본이라고 할 수 있는 정렬에서 첫 번째는 버블 정렬입니다. 알고리즘 버블 정렬의 알고리즘은 다음과 같습니다. 현재 원소를 기준으로 다음 원소와 비교한 뒤 정렬한다. 1의 과정을 ..