algorithm(1) sort

Mar 7, 2023

Sorting

  • 정렬을 왜 할까?
    • 탐색할 때 좋다.
    • $\therefore$ Searching 과 Sorting 을 연관해서 생각하면 됨.

  • Terms

    • List: 하나 이상의 field 로 된 record 의 집합
    • Key: A Field used to specify the record

  • 순차 탐색(Sequential Search)

    • one-way 로 record 를 검사하는 것
    • $O(N)$ 의 시간이 걸림

  • 이진 탐색 (Binary Search)

    • 키에 따라 정렬되어 있다고 가정
    • $O(\log N)$ 로 시간을 줄일 수 있음
      • 한 번의 탐색마다 전체 space 가 절반이 되기 때문 $$ \begin{align} \frac{n}{2}, \frac{n}{2^2}, \cdots, \frac{n}{2^k} \newline 2^k = n \newline \therefore k = \log n \end{align} $$

  • Space 크기가 작다면 그냥 Sequential Search 를 하는게 효율적일 수 있다.

  • 보간법(Interpolation) 탐색

    • 리스트가 정렬되었다고 가정함
    • 탐색의 성질은 리스트에 있는 키의 분포에 달려있음
    • 리스트를 반복해서 탐색할 때 정렬 상태를 유지하는 것이 유리함

The Sorting Problem (Def)

  • Input, Output 이 정의된 뒤 방법이 소개되는 양식이 있다고 함

Input

  • A seq of n numbers: $a_1$

정렬의 필요성(?, misc)

  • 활용
    • 탐색에서 보조로 사용
    • 리스트의 엔트리를 비교
  • 방법
    • Internal methods
      • Space 가 작아서, On-Memory 가 가능할 때
    • External methods
      • Space 가 클 때
      • 즉, HDD 등의 보조 기억장치를 이용하는 정렬
      • File System 과목에서 배움

정렬 종류

$O(n^2)$

  • Bubble sort
  • Insertion sort
  • Selection sort

$O(N \log N)$

  • Quick Sort
  • Merge Sort
  • Heap Sort

반칙? (부가적인 자원을 가져와서 정렬한다고 함)

  • Radix Sort

bubble sort

  • 아이디어
    • List 의 인접한 원소를 자리바꿈하여 정렬함
    • ex) 가장 큰 값을 오른쪽으로 계속 보냄
    • 구현은 매우 쉽지만, Insertion Sort 보다 느림

Bubble-sort running time Calc 

BUBBLESORT(A)
	for i <- 1 to length[A]
		do for j - length[A] downto i+1
			do if A[j] < A[j - 1]
				then exchange A[j] <-> A[j-1]
  • line 2, 3, 4, 5 를 각각 $c_1, c_2, c_3, c_4$ 라고 하자
  • 전체 시간 $T(n)$ 을 아래와 같이 계산할 수 있다. $$T(n) = c_1(n+1) + c_2\sum_{i=1}^n (n - i + 1) + c_3\sum_{i=1}^n$$

아무튼, $n+1$ 에서 $+1$ 하는 이유는, for, while 등은 마지막으로 한번 더 돌기 때문에 붙여준다.

Insertion Sort

  • Unsorted List ---> Sorted List
  • 과정을 진행할 때, array 를 두 부분의 sub-array(unsorted, sorted) 로 구분함.
  • (Redundant 한 작업인 것 같아도, 일일이 다 비교해야함)
INSERTION_SORT(A)
	for j <- 2 to n
	do key <- A[j]
		// i: Sorted List 에서 비교 대상을 바꾸는 것
		i <- j - 1
		while i > 0 and A[i] > key
		do A[i + 1] <- A[i]
			i <- i - 1
		A[i + 1] <- key

Best Case Analysis

  • 만약 미리 정렬이 되었다면, 자리바꿈 없이 linear time $O(N)$ 내에 작업을 완료할 수 있음

Worst Case Analysis

  • 만약 반대로 정렬이 되어있다면, $O(N^2)$ 가 걸림

  • 즉, Ordering 이 중요함

Selection Sort

  • 정렬을 하면서 깃발을 꼽음

  • 깃발이 위치한 곳을 선택했다고 생각하면 됨

  • 아이디어:

    • list 에서 가장 작은/큰 원소를 찾음
    • 발견된 원소를 맨 앞/뒤 원소와 Swap
    • 정렬된 원소를 제외한 $N-1$ 개의 원소에 대해 위 두 과정을 반복함

  • Bubble sort 와 비슷하지만, 여기서는 한 번만 Swap 하면 됨

  • Ordering (Sorting) 이 잘 되어 있어도 별 효용은 없음

SELECTION_SORT(A)

n ← length[A]

for j ← 1 to n - 1
	// j: index (최저값의 위치)
	do smallest ← j
		for i ← j + 1 to n
			do if A[i] < A[smallest]
				then smallest ← i
		exchange A[j] ↔ A[smallest]
  • (Best, Worst case Analysis)
https://c0np4nn4.github.io/posts/feed.xml