Algoritm Week 3

Algorithm week 3

기초 정렬 알고리즘

Sorting

• 데이터를 특정 조건에 따라 일정한 순서가 되도록 다시 배열하는 일

• 탐색에 용이해지며, 데이터셋 비교 등에 사용되기도 함

  Selection Sorting

  Bubble Sorting

  Insertion Sorting

  Merge Sorting

  Quick Sorting

  Heap Sorting

  Radix Sorting

  Counting Sorting

Selection Sorting

• 단순한 정렬 기법 중 하나

• 특정 숫자를 선택하는 방식으로 정렬을 진행
  각 loop마다

  1. 남아 있는 원소 중, 최대(or 최소) 원소를 선택
  2. 최대 원소와 맨 오른쪽 원소를 교환
     

  하나의 원소만 남을 때까지 위의 Loop를 반복

• 제자리 정렬(in-place sorting) 알고리즘
  → 입력 배열 이외에 다른 추가 메모리를 요구하지 않음
  → 임시 저장 메모리가 필요하지 않음

• 표로 진행과정을 살펴보자.

  Initial Array :	29 10 14 37 13
  After 1st swap :	29 10 14 13 37
  After 2nd swap :	13 10 14 29 37
  After 3rd swap :	13 10 14 29 37
  After 4th swap :	10 13 14 29 37

  → 볼드 표시가 된 숫자가 swap 된 숫자

• pseudo code

  selectionSort(A[], n)
  {
  	for last ← n down to 2 {												... ㄱ
  		A[1...last] 중 가장 큰 수 A[k]를 찾는다;						... ㄴ
  		swap(A[k], A[last]); 													... ㄷ
  	}
  }
  

  1. 수행 시간
     ㄱ : n-1번 반복
     ㄴ : 가장 큰 수를 찾기 위한 비교 횟수(n-1, n-2, …, 2, 1)
     ㄷ : 교환 작업은 상수 시간
     
  2. 시간 복잡도
     → T(n) = (n-1) + (n-2) + … + 2 + 1 = O(n^2)
     
  3. 거의 정렬되어 있든, 역으로 정렬되어 있든, 랜덤하든 항상 일정한 시간 복잡도를 가짐
     → 입력에 민감하지 않은 알고리즘 (input insensitive)
     

Bubble Sorting

• 단순한 정렬 기법 중 하나

• 이웃하는 숫자를 비교하여 특정한 수(최대 or 최소)를 한 쪽으로 이동시키는 과정을 반복하여 정렬하는 알고리즘
  → 특정 조건을 만족하는 수를 한 쪽으로 보내는 것은 선택 정렬과 동일
  → 특정 조건을 만족하는 수를 찾는 방법은 상이함
  

• 표로 진행방법을 확인하자🧐

  Phase 1	Phase 2
  29 10 14 37 13	10 14 29 13 37
  10 29 14 37 13	10 14 29 13 37
  10 14 29 37 13	10 14 29 13 37
  10 14 29 37 13	10 14 13 29 37
  10 14 29 13 37

  → 볼드로 표현된 숫자들이 짝이 되게 되고, 우측 값이 작을 경우에만 swap을 진행한다.
  

  → Phase 1이 끝나면 37이 맨 뒤로 옮겨 가게 되고, Phase 2에서는 고정된 채로 진행된다.
  

  → 계속 진행…
  

• pseudo code

  bubbleSort(A[], n)
  {
    for last ← n down to 2															...ㄱ
      for i ← 1 to last-1																...ㄴ
        if (A[i] > A[i+1]) then swap(A[i], A[i+1]);			...ㄷ
  }
  

  1. 수행 시간
     ㄱ : n-1번 반복
     ㄴ : 각각 n-1, n-2, …, 2, 1 반복
     ㄷ : 상수 시간 작업
     

  2. 시간 복잡도
     → T(n) = (n-1) + (n-2) + … + 2 + 1 = O(n^2)
     

  3. 교환이 많이 발생하게 됨
     → 특히, 특정 요소가 최종 정렬 위치에 이미 있던 경우에도 교환되는 일이 발생 → 자료의 교환 작업(swap)이 자료의 이동 작업(move)보다 더 복잡 (실용성 X)

     
     

Insertion Sorting

• 단순한 기법 중 하나

• 배열을 정렬된 부분과 안 된 부분으로 나누고, 정렬되지 않은 부분의 가장 왼쪽 원소를 정렬된 부분의 적절한 위치에 삽입하여 정렬되도록 하는 과정을 반복
  → 내가 들어가야할 위치를 찾아서 들어가는 정렬 알고리즘
  → 앞 부분은 정렬이 되었다고 생각하는 알고리즘

• 표로 진행 과정을 살펴보자💩

  Array	동작 과정
  29 10 14 37 13	Copy 10
  29 29 14 37 13	Shift 29
  10 29 14 37 13	Insert 10; copy 14
  10 29 29 37 13	Shift 29
  10 14 29 37 13	Insert 14; copy 37; insert 37 on top of itself
  10 14 29 37 13	Copy 13
  10 14 14 29 37	Shift 37, 29, 14
  10 13 14 29 37	Insert 13

  → 볼드 표시는 정렬이 된 부분 (맨 처음은 정렬 되었다고 가정하는 것)
  → 붉은 표시는 현재 위치를 찾아 삽입을 진행할 숫자
  

• pseudo code

  insertionSort(A[], n)
  {
    for i ← 2 to n																	 ...ㄱ
      A[1...i]의 적당한 자리(조건에 맞는)에 A[i]를 삽입한다.	  ...ㄴ
  }
  

  1. 수행 시간
     ㄱ : n-1의 반복
     ㄴ : 최악의 경우 i-1 회 비교
     
  2. 시간 복잡도
     → T(n) = (n-1) + (n-2) + … + 2 + 1 = O(n^2)
     
  3. 정렬된 부분을 유지하며, 한 칸 씩 늘려가며 정렬
     → 정렬 안 된 부분의 숫자 하나가 정렬된 부분에 삽입됨으로써,
     • 정렬된 부분의 원소 수가 1개 늘어나고,
     • 동시에 정렬이 안 된 부분의 원소 수는 1개 줄어듦
  4. 삽입 정렬은 입력의 상태에 따라 수행 시간이 달라질 수 있다.
     → 거의 정렬된 입력에 대해서는 다른 정렬 알고리즘보다 빠름
     → 입력 자료가 역순일 경우 최악
  5. 비교적 많은 원소들의 이동을 포함
     → 원소의 수가 많고 특히 원소의 크기가 클 경우에 적합하지 않음