정렬_Sorting

정렬_Sorting

• Key를 항목값의 대소 관계에 따라 데이터 집합을 일정한 순서로 바꾸어 늘어놓는 작업
• 오름차순 ascend_order - 값이 작은 데이터를 앞쪽에 배치
• 내림차순 descend_order - 값이 큰 데이터를 앞쪽에 배치

정렬 알고리즘의 안정성

• 정렬 알고리즘은 안정적인(stable), 안정적이지않은(unstable) 정렬로 나뉜다.
• 안정적인 정렬알고리즘은 값이 같은 원소의 순서가 정렬 후에도 유지된다. 안정적이지 않은 정렬은 순서가 유지 된다는 보장을 할 수 없다.

내부정렬 외부정렬

• 내부정렬(internal sorting) - 정렬할 모든 데이터를 하나의 배열에 저장할 수 있는 경우 사용하는 알고리즘
• 외부정렬(external sorting) - 정렬할 데이터가 많아서 하나의 배열에 저장할 수 없는 경우 사용하는 알고리즘

정렬 알고리즘의 핵심은 교환, 선택, 삽입이다. 😊

버블정렬(BubbleSort)

• 이웃한 두 원소에 대소관계를 비교하여 필요에 따라 교환을 반복하는 알고리즘
• 단순 교환 정렬 이라고도 한다.
• 일련의 비교, 교환하는 과정을 패스(pass)라고 한다.
• 시간복잡도 O(n²), 공간복잡도 O(n)

단순 선택 정렬(StraightSelectionSort)

• 가장 작은 원소부터 선택해 알맞은 위치로 옮기는 작업

1. 아직 정렬하지 않은 부분에서 값이 가장 작은 원소 a[min]을 선택한다.
2. a[min]과 아직 정렬하지 않은 부분에 맨 앞에 있는 원소를 교환한다.

• 시간복잡도 O(n²), 공간복잡도 O(n)

단순 삽입 정렬(StraightInsertionSort)

• 주목한 원소보다 더 앞쪽에서 알맞은 위치로 삽입하며 정렬하는 알고리즘
• 아직 정렬되지 않은 부분의 맨 앞 원소를 정렬된 부분의 알맞은 위치에 삽입한다.

종료조건

1. 정렬된 배열의 왼쪽 끝에 도달한 경우
2. tmp보다 작거나 키값이 같은 원소 a[j-1]을 발견한 경우

계속조건

1. j가 0보다 큰 경우
2. a[j-1]의 값이 tmp보다 큰 경우

장단점

• 장점 - 이미 정렬을 마쳤거나 정렬이 거의 끝나가는 상태에서 속도가 아주 빠르다.
• 단점 - 삽입할 위치가 멀면 이동횟수가 많아진다.

셸 정렬(ShellSort)

• 단순 삽입 정렬의 장점은 살리고 단점은 보완하여 더 빠르게 정렬하는 알고리즘
• 먼저 정렬할 배열의 원소를 그룹으로 나눠 각 그룹 별로 정렬 수행
• 그 후 정렬된 그룹을 합치는 작업을 반복해서 원소의 이동횟수를 줄이는 방법
  • 2개 원소에서 4-정렬수행(4개 그룹 4번)
  • 4개 원소에서 2-정렬수행(2개 그룹 2번)
  • 8개 원소에서 1-정렬수행(1개 그룹 1번)

퀵 정렬(QuickSort)

• 가장 빠른 알고리즘
• pivot을 기준으로 배열을 두 그룹으로 나눈다.
• pivot을 선택하는 방법은 여러가지 크게 첫번째 요소, 중간요소, 마지막 요소, 랜덤으로 선택하는 방식

진행방식

1. 피벗을 선택한다.
2. 오른쪽에서 왼쪽으로 가면서 피벗보다 작은 수를 찾는다.
3. 왼쪽부터 오른쪽으로 가면서 피벗보다 큰 수를 찾는다.
4. 각 인덱스 i,j에 대한 요소를 교환한다.
5. 2,3,4 과정을 반복한다.
6. 2,3을 진행할 수 없다면 현재 피벗과 교환
7. 그 결과 피벗을 기준으로 왼쪽은 피벗보다 작은 수들이 존재하고, 오른쪽에 큰수들이 존재한다.

병합 정렬(MergeSort)

• 배열의 앞부분과 뒷부분의 두 그룹으로 나누어 각각 정렬한 후 병합하는 작업 반복

진행

1. 리스트 길이가 0 또는 1이면 이미 정렬된 것으로 본다.
2. 그렇지 않은 경우 정렬되지않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.
3. 각 부분 리스트를 재귀적으로 병합 정렬을 이용해 정렬한다.
4. 두 부분 리스트를 다시 하나의 정렬된 리스트로 병합한다.

• 분할(Divide) - 입력 배열을 같은 크기의 2개의 부분 배열로 분할
• 정복(Conquer) - 부분 배열을 정렬한다. 부분 배열 크기가 충분히 작지 않으면 순환 호출을 이용해 다시 분할 정복 방법을 적용한다.
• 결합(Combine) - 정렬된 부분 배열들을 하나의 배열에 병합

2개의 정렬된 리스트 병합 과정

1. 2개의 리스트 값들을 처음부터 하나씩 비교하여 두개의 리스트의 값중에서 더 작은값을 새로운 리스트로 옮긴다.
2. 둘 중 하나가 끝날 때 까지 반복한다.
3. 하나가 끝나면 남은 리스트를 새로운 리스트로 복사한다.
4. 새로운 리스트를 원래 리스트로 옮긴다.

힙 정렬(HeapSort)

• 완전 이진 트리의 일종 우선 순위 큐를 위하여 만들어진 자료구조
  • 최댓값 , 최솟값을 쉽게 추출할 수 있는 자료구조

힙 정렬 알고리즘 개념

• 최대 힙 트리나 최소 힙트리를 구성해 정렬을 하는 방법
• 내림차순을 위해서는 최대 힙 구현, 오름차순을 위해서는 최소 힙 구현
  • 정렬해야할 n개의 요소들로 힙을 만든다.
  • 한번에 하나씩 요소를 힙에서 꺼내서 배열의 뒤부터 저장한다
  • 삭제 되는 요소들은 값이 감소되는 순서로 정렬되게 된다.