개발하는데 다 이유가 있겠지

정렬 알고리즘(Sorting Algorithm)

---

선형 구조

2중 for문으로 구현

버블 정렬(Bubble Sort)

서로 인접한 2개의 원소를 비교해 정렬하는 알고리즘(크기가 순서대로 되어있지 않으면 서로 교환)

def bubbleSort():
    arr = [3, 4, 2, 5, 1]

    for i in range(0, len(arr)):
        for j in range(0, len(arr)-1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    print(arr)

bubbleSort()

출처 : https://gmlwjd9405.github.io/2018/05/06/algorithm-bubble-sort.html

• 구현이 매우 간단함
• 하나의 요소가 가장 왼쪽에서 가장 오른쪽으로 이동하기 위해서 배열에서 모든 요소들과 교환됨
• 시간 복잡도 O(n^2)

---

2. 선택 정렬(Selection Sort)

첫 번째 자료를 두 번째 자료부터 마지막 자료까지 차례대로 비교하여 가장 작은 값을 찾아 첫 번째에 놓고, 두 번째 자료를 세 번째 자료부터 마지막 자료까지와 차례대로 비교하여 그 중 가장 작은 값을 찾아 두 번째 위치에 놓는 과정을 반복하며 정렬을 수행

출처 : https://gmlwjd9405.github.io/2018/05/06/algorithm-selection-sort.html

• 자료 이동 횟수가 미리 결정됨
• 값이 같아도 상대적인 위치가 변경될 수 있음

---

3. 삽입 정렬(Insertion Sort)

두 번째 자료부터 이전(왼쪽)의 자료들과 비교해 삽입할 위치를 지정한 후 자료들을 뒤로 옮기고 지정한 자리에 자료를 삽입

• 레코드 수가 적을 경우 알고리즘 자체가 매우 간단해 다른 복잡한 정렬 방법보다 유리할 수 있음
• 대부분 정렬되있는 경우 매우 효율적
• 비교적 많은 레코드들의 이동이 발생

---

비선형 구조

재귀함수를 이용한 구현

1. 합병 정렬(Merge Sort)

분할정복을 사용해, 최소 단위로 리스트를 나누어 두 개의 부분 리스트들을 정렬하면서 합하여 정렬된 리스트를 만듬

출처 : https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html

• 데이터를 배열로 구성하면, 임시 배열이 필요
• 데이터가 많아지면 이동 횟수가 많아지므로 시간적 낭비가 발생
• 연결 리스트로 구성하면 링크 인덱스만 변경되므로 데이터의 이동은 무시할 정도로 작아짐(제자리 정렬)

---

2. 힙 정렬(Heap Sort)

완전 이진 트리의 일종으로 우선순위 큐를 위해 만들어진 자료구조

최대값, 최솟값을 쉽게 추출할 수 있는 자료구조 / 최대힙(Max Heap), 최소힙(Min Heap)

 

• 내림차순 정렬(최대힙), 오름차순 정렬(최소힙)

최대힙(Max Heap)

최대힙의 삽입

1. 정렬해야 할 n개의 요소들을 1차원 배열에 기억한 후 최대 힙 삽입을 통해 차례대로 삽입
2. 최대힙으로 구성된 배열에서 최대값부터 삭제

최대힙의 삭제

1. 최대힙에서 최대값은 루트노드이므로 루트 노드가 삭제됨(삭제 연산 : 최대값 삭제)
2. 삭제된 루트 노드에는 힙의 마지막 노드가 위치함
3. 힙을 재구성함(내림차순 정렬)

• 시간복잡도가 좋은 편 O(n log n)
• 전체 자료를 정렬하는 것이 아닌 가장 큰(작은)값 몇개만 필요할 때

출처 : https://gmlwjd9405.github.io/2018/05/10/algorithm-heap-sort.html

---

3. 퀵 정렬(Quick Sort)

하나의 리스트를 피벗(pivot)을 기준으로 두 개의 비균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법(리스트가 0이나 1이 될 때까지 반복)

출처 : https://gmlwjd9405.github.io/2018/05/10/algorithm-quick-sort.html

• 분할(Divide): 입력 배열을 피벗을 기준으로 비균등하게 2개의 부분 배열(피벗을 중심으로 왼쪽: 피벗보다 작은 요소들, 오른쪽: 피벗보다 큰 요소들)로 분할
• 정복(Conquer): 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출 을 이용하여 다시 분할 정복 방법을 적용
• 결합(Combine): 정렬된 부분 배열들을 하나의 배열에 합병
• 순환 호출이 한번 진행될 때마다 최소한 하나의 원소(피벗)는 최종적으로 위치가 정해지므로, 이 알고리즘은 반드시 끝난다는 것을 보장