정렬

최악의 경우 $\Theta(n^2)$의 시간복잡도를 갖지만 $\Omicron(n\log n)$ 평균적으로 가장 좋은 성능을 보이고 구현이 쉬워 현업에서 가장 많이 쓰인다고 알려진 퀵 정렬을 알아보고 자바와 파이썬으로 구현해 봅시다. 자료구조, 알고리즘 시리즈 모아보기 퀵 정렬 `퀵 정렬(quick sort)`은 병합 정렬 알고리즘과 비슷하게 입력을 나누어 각각에 대해 재귀적으로 정렬하는 알고리즘입니다. 퀵 정렬과 병합 정렬의 차이점은 크게 두 가지가 있습니다. 퀵 정렬은 병합 정렬과 달리 합치는 과정이 없고 입력을 항상 반씩 균등하게 나누지 않습니다. 퀵 정렬은 기준값정하고 기준값보다 큰 값들과 작은 값들로 입력을 분할합니다. 이때 기준값을 `피벗(pivot)`이라 합니다. - Pseudocode qui..

지금까지 기본적인 시간 복잡도가 $\Omicron(n^2)$인 정렬 알고리즘들을 알아봤습니다. 선택 정렬, 삽입 정렬, 버블 정렬은 모두 평균 $\Theta(n^2)$의 시간 복잡도를 가졌고 삽입정렬과 개선된 버블 정렬은 최선의 경우 $\Theta(n)$의 시간 복잡도를 가졌습니다. 이번에는 평균 $\Theta(n\log n)$의 시간 복잡도인 고급 정렬 알고리즘들에 대해 알아봅시다. 자료구조, 알고리즘 시리즈 모아보기 병합 정렬 `병합 정렬(merge sort)`은 입력을 반으로 나누어 각각 정렬한 뒤 합치는 재귀 알고리즘입니다. "정렬하는 방법이 반으로 나눈 뒤 각각 정렬하는거면 각각은 어떻게 정렬하라는 거지?" 싶을 수 있습니다. 재귀적으로 입력을 반으로 나눠 정렬하다보면 어느 순간 입력의 크기는 ..

그 유명한 버블 정렬에 대해 알아보고 C++, 자바, 파이썬으로 구현해 봅시다. 자료구조, 알고리즘 시리즈 모아보기 버블 정렬 `버블 정렬(bubble sort)`은 선택 정렬처럼 가장 큰 원소를 끝으로 옮기는 작업을 반복하는 알고리즘입니다. 선택 정렬이 큰 값을 콕 찍어서 옯겼다면 버블 정렬은 한쪽 끝에서 긁어 올라가며 더 큰 값만 가지고 올라가는 방식입니다. 이렇게 논리적으로 아래에서부터 수면 위로 올라가는 모습을 컴퓨터 과학에서는 버블링이라고 합니다. DOM트리에서 일어나는 이벤트 버블링도 아래에서 위로 올라가는 의미의 버블링이죠. - Pseudocode 정렬해야 하는 배열 A[n]이 주어졌을 때 버블 정렬 알고리즘은 다음과 같습니다. bubbleSort(A[], n){ for( last ← n d..

정렬 알고리즘 중 삽입 정렬을 알아보고 C++, 자바, 파이썬으로 구현해봅시다. 자료구조, 알고리즘 시리즈 모아보기 삽입 정렬 `삽입 정렬(insertion sort)`은 정렬된 부분을 하나씩 확장해 가며 모든 수열을 정렬하는 알고리즘입니다. - Pseudocode 정렬해야 하는 배열 A[n]이 주어졌을 때 삽입 정렬 알고리즘은 다음과 같습니다. insertionSort(A[], n){ for( last ← 2 to n ) A[1 ⋯ last] 에 A[last]가 들어갈 곳을 찾아 넣는다; } 구체화하면 아래와 같습니다. insertionSort(A[], n){ for( last ← 2 to n ){ newElement ← A[last]; // 추가할 요소 i ← last-1; // newElement와..

정렬 알고리즘에서 가장 기본이 되는 선택 정렬을 알아보고 C++, 자바 그리고 파이썬으로 구현해봅시다. 자료구조, 알고리즘 시리즈 모아보기 선택 정렬 `선택 정렬(selection sort)`은 정렬할 수열에서 가장 큰 값(혹은 가장 작은 값)을 선택해 한쪽 끝으로 옮기는 행위를 반복하여 정렬하는 알고리즘입니다. - Pseudocode 정렬해야 하는 배열 A[n]이 주어졌을 때 선택 정렬 알고리즘은 다음과 같습니다. selectionSort(A[], n){ for( last ← n downto 2 ){ A[1 ⋯ last] 중 가장 큰 수 A[k]를 찾는다; A[k] ↔︎ A[last]; } } 조금 더 구체화하면 아래와 같습니다. selectionSort(A[], n){ for( last ← n dow..