알고리즘

정렬알고리즘 – 선택정렬, 삽입정렬, 버블정렬, 합병정렬, 퀵정렬, 힙정렬

• 단순하지만 비효율적인 방법 : 삽입 정렬, 선택 정렬, 버블 정렬
• 복잡하지만 효율적인 방법: 퀵 정렬, 힙 정렬, 합병 정렬, 기수 정렬

---

선택 정렬

• 해당 순서에 원소를 넣을 위치는 이미 정해져 있고 어떤 원소를 넣을지 선택하는 알고리즘
• 장점 : 자료 이동 횟수가 미리 결정된다.
• 단점 : 값이 같은 레코드가 있는 경우에 상대적인 위치가 변경될 수 있어서 안정성을 만족하지 않는다.
• 시간 복잡도는 최선 n^2, 평균 n^2, 최악 n^2

삽입 정렬

• 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입하는 알고리즘
• 장점 : 안정한 정렬 방법이고 레코드의 수가 적을 경우 알고리즘 자체가 매우 간단하므로 다른 복합한 정렬방법보다 유리할 수 있다. 대부분의 레코드가 이미 정렬되어 있는 경우에는 매우 효율적.
• 단점 : 비교적 많은 레코드들의 이동을 포함, 레코드 수가 많고 레코드 크기가 클 경우에는 부적합
• 시간 복잡도는 최선은 이미 정렬되어 있는 경우O(n), 최악은 역순인 경우 O(n^2) 평균 O(n^2)

버블 정렬

• 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘
• 장점 : 구현이 매우 간단
• 단점 : 순서에 맞지 않은 요소를 인접한 요소와 교환하고 하나의 요소가 가장 왼쪽에서 가장 오른쪽으로 이동하기 위해서는 배열에서 모든 다른 요소들과 교환되어야 한다. 특히 특정 요소가 최종 정렬 위치에 이미 있는 경우라도 교환되는 일이 일어난다.
• 시간 복잡도는 최상 평균 최악 모두 O(n^2)

합병 정렬

• 분할 정복 알고리즘의 하나이다.
• 분할 정복이란 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략. 분할->정복->결합
• 장점 : 안정적인 정렬 방법이라는 것. 데이터의 분포에 영향을 덜 받는다. 만약 연결 리스트로 구성하면 링크 인덱스만 변경되므로 데이터의 이동은 무시할 정도로 작아진다. 따라서 크기가 큰 레코드를 정렬할 경우에 연결 리스트를 사용한다면, 합병 정렬은 퀵 정렬을 포함한 다른 어떤 정렬보다 효율적.
• 단점 : 만약 레코드를 배열로 구성한다면, 임시 배열이 필요하다. 레코드들의 크기가 큰 경우에는 이동 횟수가 많으므로 매우 큰 시간적 낭비를 초래
• 시간 복잡도는 최상 최악 평균 o(nlogn)

퀵 정렬

• 분할 정복 알고리즘의 하나로 평균적으로 매우 빠른 속도를 자랑한다. 합병 정렬과 달리 리스트를 비균등하게 분할한다. 리스트 안에 있는 피봇을 선택한다. 피봇을 기준으로 피봇보다 작은 요소들은 모두 피봇의 왼쪽으로 옮겨지고 피봇보다 큰 요소들은 모두 피봇의 오른쪽으로 옮겨진다. 피봇을 제외한 왼쪽 리스트와 오른쪽 리스트들을 다시 정렬한다. 부분 리스트들이 더 이상 분할이 불가능할 때 까지 반복한다.
• 장점 : 속도가 빠르다는 것과 추가 메모리 공간을 필요로 하지않는다.
• 단점 : 정렬된 리스트에 대해서는 퀵 정렬의 불균형 분할에 의해 오히려 수행시간이 더 많이 걸린다.
• 최악의 경우 O(n^2) 최선과 평균은 O(nlogn)

힙 정렬

• 최대 힙이나 최소 힙을 구성해 정렬하는 방법이다. 내림차순 정렬을 위해서는 최대 힙을 구성하고 오른차순 정렬을 위해서는 최소 힙을 구성하면 된다. 정렬해야할 n개의 요소들로 힙을 만들고 한 번에 하나씩 요소를 힙에서 꺼내서 배열의 뒤부터 저장하면 된다.
• 장점 : 시간 복잡도가 좋은편이고 힙정렬이 가장 유용한 경우는 전체 자료를 정렬하는 것이 아니라 가장 큰 값 몇 개만 필요할 때이다.
• 시간복잡도는 O(nlogn)이다.

---

MST(최소 신장 트리)

• 스패닝 트리중에서 사용된 간선들의 가중치 합이 최소인 트리, 구현 방법으로는 크루스칼과 프림이 있다.
• 크루스칼 알고리즘
  • greedy를 이용 가장 낮은 가중치를 선택, 사이클을 형성하는 간선은 제외
• 프림 알고리즘
  • 시작 정점에서부터 출발하여 단계적으로 확장, 단계별로 만들어진 트리에 인접한 정점들 중에서 최소 간선을 선택

---

최단경로 알고리즘

다익스트라

• 음의 간선이 없을 때

플로이드워샬