본문 바로가기

정렬6

합병 정렬(=병합 정렬) 이란? 1. 합병 정렬 1-1. 합병 정렬? 병합 정렬? 1-2. 합병 정렬이란? 1-3. 움짤로 보는 예시 1-4. 글로 보는 예시 1-5. 소스코드 1-6. 합병 정렬의 시간 복잡도 1-7. 합병 정렬은 얼마나 빠를까? 1. 합병 정렬 1-1. 합병 정렬? 병합 정렬? 처음에 이름이 굉장히 헷갈렸다. (합병이 병합이고 병합이 합병 아닌가...? 🥴) 결론부터 말하자면 둘 다 맞는 말이다. 둘 다 사용해도 된다. 개인적으로 궁금해서 둘의 그 미묘한 차이를 알고 싶어 알아봤는데 합병: A와 B가 합쳐져 C가 만들어짐 병합: A가 B의 일부가 되거나 B가 A의 일부가 됨 이 블로거에 의하면 위와 같은 차이가 있다고 한다. 만약 이게 사실이라면 음,,, 나는 합병 정렬이 오늘 배울 내용과 더 적합하지 않을까..?라.. 2021. 5. 30.
퀵 정렬이란? 1. 퀵 정렬 1-1. 퀵 정렬이란? 1-2. 예시 1-3. 소스코드 1-4. 퀵 정렬의 시간 복잡도 1-5. 퀵 정렬은 얼마나 빠를까? 1. 퀵 정렬 1-1. 퀵 정렬이란? 이름값 하는 정렬 방법이다. 평균적으로 꽤나 빠른 속도를 보여준다. 여기서 평균적으로라고 한 이유는 [목차 1-4]에서 설명할 예정이다. 아무튼 이렇게 빠르게 정렬할 수 있는 이유는 분할 정복 방법을 사용했기 때문이다. 분할 정복 방법이란 큰 문제를 작은 문제로 쪼개어 문제를 해결하는 방식이다. 한 번에 먹기에 너무 큰 음식이 있으면 잘라먹듯이 한 번에 들기에 너무 무거운 짐이 있으면 나눠 들듯이 큰 문제를 해결하기 쉬운 작은 문제로 쪼개자는 것이다. 퀵 정렬은 이 개념을 도입한 방법인데 어떻게 정렬되는 건지 다음 목차에서 알아보자.. 2021. 5. 27.
셸 정렬이란? 1. 셸 정렬 1-1. 셸 정렬이란? 1-2. 예시 1-3. 소스코드 1-4. 셸 정렬의 시간 복잡도 1-5. 셸 정렬은 삽입 정렬보다 얼마나 빠를까? 1. 셸 정렬 1-1. 셸 정렬이란? 셸 정렬은 삽입 정렬의 개선판 정도로 생각할 수 있다. 삽입 정렬은 거의 정렬되어 있는 수열이 주어졌을 때 좋은 효율을 보여준다는 장점이 있었지만 그 반대로 역순에 가까운 수열이 주어지면 그만큼 좋지 못한 효율을 보여주었다. 그래서 옛날에 도널스 셸이라는 사람이 "흠.. 수열을 어느 정도 정렬되게 바꾼 다음 삽입 정렬을 쓰면 좋지 않을까?" 해서 나온 게 셸 정렬이다. 실제로도 셸 정렬을 할 때 삽입 정렬을 사용한다. 그러니 삽입 정렬을 아직 모른다면 먼저 배우고 오자. 1-2. 예시 위와 같이 내림차순에 가까운 수열.. 2021. 5. 15.
삽입 정렬이란? 1. 삽입 정렬 1-1. 삽입 정렬이란? 1-2. 예시 1-3. 소스코드 1-4. 삽입 정렬의 시간 복잡도 1. 삽입 정렬 1-1. 삽입 정렬이란? 정렬 방법 중 가장 느린 버블 정렬 버블 정렬보다 조금 빠른 선택 정렬 그리고 선택 정렬보다 조금 빠른 것이 오늘 배울 삽입 정렬이다. 이미 정렬되어있는 수열 중 자신이 들어가야 할 위치를 찾아 삽입한다 하여 삽입 정렬이라는 이름이 붙었다. 말로만 들어서는 이해가 잘 안 가니 다음 예시를 통해 알아보자. 1-2. 예시 위와 같은 숫자를 정렬한다고 치자. 첫 번째 바퀴 [5]와 [7]을 비교해보자. 자리 바꿈이 필요할까? NO! 그렇다면 다음으로 넘어가자. 두 번째 바퀴 [7]와 [8]을 비교해보자. 자리 바꿈이 필요할까? NO! 그렇다면 다음으로 넘어가자. .. 2021. 5. 13.
선택 정렬이란? 1. 선택 정렬 1-1. 선택 정렬이란? 1-2. 움짤로 보는 예시 1-3. 글로 보는 예시 1-4. 소스코드 1-5. 선택 정렬의 시간 복잡도 1. 선택 정렬 1-1. 선택 정렬이란? 정렬 방법 중 가장 느린 것은 버블 정렬. 그리고 그다음으로 느린 방법이 바로 선택 정렬이다. 버블 정렬과 마찬가지로 구현이 단순하며 메모리 공간을 추가로 필요로 하지 않는다. 버블 정렬은 자리 바꿈(swap)이 자주 일어나지만 선택 정렬은 평균적으로 그 횟수가 더 적기 때문에 버블 정렬보다 선택 정렬이 항상 더 나은 효율을 보여준다. 움짤을 통해 어떻게 하는 정렬 방법인지 알아보도록 하자. 1-2. 움짤로 보는 예시 숫자들 중 가장 작은 값을 선택해서 맨 왼쪽에 있는 값과 교환하는 것이 기본적인 개념이다. 가장 작은 값.. 2021. 5. 12.