알고리즘 - 정렬

정렬 알고리즘

• 일정한 기준, 대소 관계에 따라 데이터 집합을 일정한 순서로 나열하는 작업
• 오름차순 : 최소값 → 최대값
• 내림차순 : 최대값 → 최소값
  정렬기반 👉 알고리즘 - 이분탐색, 다익스트라, 힙

버블 정렬

• 이웃한 두 요소의 대소관계를 비교하여 교환을 반복하는 알고리즘
• 처음부터 끝까지 이웃한 두 요소를 비교, 교환하여 가장 맨 오른쪽에 위치 시키는 정렬
• 시간 복잡도 : O(N^2)

선택 정렬

• 가장 작은 값을 찾아 맨 앞으로 이동 시키는 정렬을 반복하는 알고리즘
  1) (외부 루프)i = 0 to N-2, (내부 루프)j = i to N-1
  2) 최소값 갱신

삽입 정렬

• 선택한 요소의 알맞은 위치에 값을 삽입하는 정렬(교환X)
• 시간 복잡도(최선) : O(N) - 값들이 정렬된 상태에서 탐색하는 경우
• 시간 복잡도(최악) : O(N^2)

방법

1) 삽입 위치 탐색
- 해당 인덱스 값보다 작은 인덱스 값을 만나는 자리가 알맞은 위치
- 삽입하려는 값이 가장 최소값인 경우
2) 값 이동
- 삽입하려는 값을 백업 해놓기
- 삽입하려는 위치 다음으로 값들 한칸씩 이동

Pseudo-code

arr //배열
n //배열의 크기
for i = 1 to n-1
	temp = arr[i] //삽입값=최소값
    j = i-1
    while j>=0 && arr[j] > temp //arr[j] : 탐색값
    	arr[j+1] = arr[j]
        j--
    arr[j+1] = temp

퀵 정렬

• 분할 정복 (작게 쪼개서 문제 해결)
• 기준 값(pivot)을 기준으로 작은 값과 큰 값으로 나누어 작업을 반복하는 알고리즘
• 피봇(pivot) : 그룹을 나누는 기준
• 재귀 함수 호출 이용
• 시간 복잡도(평균) : O(N * logN)
• 시간 복잡도(최악) : O(N^2) - 값들이 정렬된 상태에서 탐색하는 경우

방법

1) 첫 번째 값 기준으로 기준 값(pivot) 설정 - 기준값은 정렬 완료
- 가장 왼쪽, 가장 오른쪽, 가운데
2) 기준 값(pivot) 보다 작은 값은 왼쪽, 큰 값은 오른쪽에 배치
3) 기준 값(pivot) 위치의 왼쪽부분과 오른쪽 부분의 위의 과정 반복

---

1) 첫 번째 값 기준 값(pivot), 나머지 배열에서 맨 왼쪽 left, 맨 오른쪽 right
기준값보다 큰 값 나올 때 까지 left 1 증가,
기준값보다 작은 값 나올 때 까지 right 1 감소

하나의 피봇값을 기준으로 왼쪽, 오른쪽 정렬

• [start, end]
  • [start, pivot-1]
  • [pivot+1, end]

병합 정렬

• 분할 정복 (작게 쪼개서 문제 해결)
• 배열을 분할하고 분할한 배열을 정복하며 정렬하는 알고리즘
• 주어진 배열을 분할하여 더 이상 나눌 수 없을 때까지 분할
• 인접한 부분 배열들을 정렬하면서 병합
  - 두개의 정렬된 부분 집합 👉 하나의 정렬된 집합
• 시간 복잡도 : O(N * log2N) - 안정적인 정렬

방법

두개의 정렬된 부분 집합 👉 하나의 정렬된 집합

mid, start, end
mid = (start+end)/2
부분 집합 범위 : [start, mid], [mid+1, end] 분할 반복(집합의 값이 1개 일때 까지)

Java 정렬 API

• Arrays.sort()