4주차 - 정렬

정렬

기초적인 정렬 알고리즘

• 평균적으로 \(θ(n^2)\)의 시간이 소요됨

종류

• 선택정렬
• 버블정렬
• 삽입정렬

선택 정렬

• 각 루프마다 최대값을 탐색함
• 최대원소와 맨 오른쪽 원소를 교환하고, 맨 오른쪽 원소를 제외함
• 하나의 원소만 남을 때까지 위의 루프를 반복함
• 수행시간: \(θ(n^2)\)

버블 정렬

• 인접한 2개의 값의 크기를 비교함
• 왼쪽의 값이 더 클 경우, 오른쪽의 값과 바꾼다
• 수행시간: \(θ(n^2)\)
• 가장 오른쪽의 값은 정렬 대상에서 제외함

삽입 정렬

• 선택/버블 정렬과 다르게, 이미 정렬된 배열의 크기를 1개씩 늘리는 것
• 해당 값의 위치에 값이 삽입한다
• 배열 A[1, n]까지 정렬된 경우, 행의 삽입에 의해 A[1, …, n+1]까지 정렬됨
• 수행시간: Worst Case / Average Case : \(θ(n^2)\)
  Best Case : \(θ(n)\)

고급 정렬 알고리즘

종류

• 평균적으로 \(θ(nlog^n)\)의 시간이 소요됨

• 병합정렬
• 퀵정렬
• 힙정렬

병합 정렬

• 배열을 절반으로 나눔
• 각 배열별로 재귀함수를 이용해 정렬 한 후, 병합함
• 수행시간: \(θ(nlog^n)\)