2019-08-20
병합 정렬(merge sort)? 병합 정렬(merge sort)의 핵심은 분할과 정복이다. 정렬할 배열을 원소가 하나뿐인 배열 단위로 나뉠 때까지 분할하고, 반대로 이렇게 분할된 배열을 점점 더 큰 배열로 병합하면서 정렬을 완성한다. 분할/정복이라는 접근 방식은 재귀 호출을 통해 구현된다. 이 링크를 통해 병합 정렬이 어떻게 작동하는지 참고할 수 있다.…
2019-08-20
퀵 정렬(quick sort)? 퀵 정렬(quick sort)은 가장 애용되는 정렬 알고리즘이다. 복잡도는 O(n long n)이고, 복잡도가 동일한 여타 정렬 알고리즘보다 성능이 낮다. 병합 정렬과 마찬가지로 분할/정복 방식으로 접근한다(그러나 병합 정렬 과는 달리, 원소를 하나 가진 배열까지 잘게 쪼개지 않는다.) 이 링크를 통해 퀵 정렬이 어떻게 작…
2019-08-19
삽입정렬? 삽입 정렬(insertion sort)은 한 번에 한 원소씩 정렬된 배열을 만들어가는 알고리즘이다. 첫 번째 원소는 정렬이 끝났다고 가정하고, 두 번째 원소와 비교해 첫 번째 원소보다 더 작다면 첫 번째 원소 앞으로 옮긴다. 그래서 처음 두 원소의 정렬이 끝나면 다음엔 세 번째 원소와의 비교를 계속한다.(첫 번째, 두 번째, 세 번째 위치 중 …
2019-08-19
선택정렬? 선택정렬(selection sort)은 제자리(in-place) 정렬 알고리즘의 하나로, 최솟값을 찾아 맨 앞으로 보내고, 그 다음으로 작은 값을 찾아 2번째 위치로 보내는 식으로 정렬한다. 이 링크를 통해 선택 정렬이 어떻게 작동하는지 참고할 수 있다. 시간복잡도 시간 복잡도가 O(n^2) 이기 때문에 거의 사용되지 않는 알고리즘이다. 다만 …
2019-08-18
버블정렬(Bubble Sort)? 버블 정렬은 인접한 두 원소를 모두 다 비교하고 그 결과에 따라 두 원소의 위치를 서로 바꾼다. 원소가 정렬돼가는 모습이 마치 수면 위로 떠오르는 거품(버블) 같다고 하여 버블 정렬이란 이름이 붙었다. 이 링크를 통해 버블 소트가 어떻게 정렬되는지 참고할 수 있다. 시간복잡도 시간 복잡도가 O(n^2) 이기 때문에 거의 …