생성일: 2021년 12월 3일 오후 5:48

정렬 알고리즘 (ascending만 다룸)

Straight Selection Sort

• 제일 작은 아이템을 제일 위쪽(앞쪽)으로 올리는 방식 ⇒ 제일 작은 아이템과 제일 위쪽의 아이템 swap
• sorting이 된 부분과 그렇지 않은 부분을 구분
• 36 24 10 6 12 ⇒ 6 \ 24 10 36 12 ⇒ 6 10 \ 24 36 12 ⇒ 6 10 12 \ 36 24 ⇒ 6 10 12 24 36
• 복잡도
  • f(N) = (N-1) + (N-2) + (N-3) + ..... 3 + 2 + 1 = N(N-1)/2
  • O(N^2)

Bubble Sort

• 두개의 아이템을 서로 비교하여 작은 아이템을 앞쪽으로 밀어내는 방식
• sorting이 된 부분과 그렇지 않은 부분을 구분
• 정렬되지 않은 부분에 속한 아이템 중 가장 작은 아이템이 위쪽으로 올라가게 됨
• 36 24 10 6 12 ⇒ 6 \ 36 24 10 12 ⇒ 6 10 \ 36 24 12 ⇒ 6 10 12 \ 36 24 ⇒ 6 10 12 24 36
• O(N^2)

Insertion Sort

• 정렬이 안되있는 부분에 속한 첫번째 아이템부터 자기 자리를 찾아서 insert (구현은 swap 형태)
• 버블 소팅과 다른점
  • 버블 소팅에서는 비정렬 집단에서 가장 작은 아이템을 올리는 구조이지만 Insertion에서는 처음 지정된 아이템을 계속 비교해 가면서 자신의 위치를 찾아주는 구조
• O(N^2)

Heap Sort

1. unsorted Array를 heap으로 바꾼다.
2. heap에서는 가장 큰 아이템이 root에 위치해 있다.
3. root에 위치한 아이템을 어레이의 밑으로 내리고 다시 ReheapDown으로 heap 정렬
4. 이 작업을 반복하면 오름차순 정렬 완료

• 1번 작업에서 비정렬 어레이를 heap으로 바꿀때 중요한 점

  for (index = numValues/2 - 1; index >= 0; index--)
  	ReheapDown(values, index, numValues - 1);

  이 코드가 해당 기능을 구현한다. 이때 index = numValues/2 - 1 가 의미 하는 것은 non-terminal 노드 중 가장 마지막 노드부터 시작한다는 것이다. terminal 노드들은 어차피 그 자체로 heap인 상태이다. 따라서 child를 가진 non-terminal 노드들을 대상으로 ReheapDown을 통해 큰 아이템을 위로 올려주는 정렬을 해주면 Array 전체가 Heap이 된다.
• 복잡도

  1. (N/2) * O(logN) ⇒ Unsorted Array를 heap으로 바꿀 때

  2. (N-1) * O(logN) ⇒ Sorting loop

     1 + 2 ⇒ O(N * logN)

Quick Sort

• Divde and conquer

1. 어레이에서 첫번째(혹은 마지막) 아이템을 pivot으로 잡는다.
2. left와 right 변수로 pivot을 제외한 어레이의 가장 왼쪽 인덱스와 오른쪽 인덱스를 저장
3. left는 오른쪽으로 이동하면서 pivot보다 큰 수가 나오면 멈춤
4. right는 왼쪽으로 이동하면서 pivot보다 작은 수가 나오면 멈춤
5. left와 right 위치에 있는 아이템을 swap
6. 3번의 작업부터 다시 반복 (left < right 일 때 동안만)
7. pivot과 left가 트래킹하고 있던 아이템을 swap
8. pivot 이었던 아이템의 왼쪽 부분과 오른쪽 부분을 각각 재귀적으로 다시 1번부터 진행

• 복잡도
  • 이상적인 구조에서 O(N * logN)
  • 최악의 경우에서 O(N^2)
    • 이미 sorting 되어 있는 어레이를 정렬할 때가 최악의 경우이다. why? divide and conquer가 불가능 하기 때문

Merge Sort

• 어레이를 계속 반으로 쪼개서 크기가 1이 되도록 나눔
• 각각의 쪼개진 어레이들을 Merge하면서 정렬

• 복잡도
  • O(N*logN)
  • 메모리를 많이 사용한다는 단점 존재

Radix Sort

• 아이템끼리 비교해가면서 정렬하는 방식이 아니다.
• 같은 자릿수에서 같은 값을가지는 아이템들을 queue에 넣고 dequeue한다.
• 이 과정을 1의 자리부터 제일 큰 자릿수까지 반복하면 정렬이 된다.
• 복잡도
  • O(총자릿수 * N)
  • 메모리 공간이 매우 많이 필요하다 (queue가 많이 필요하기 때문)

Sorting Algorithms 복잡도 비교

Stability

• 정렬할 어레이에 중복된 아이템이 있을 때, 정렬 전에 앞에 있던 아이템이 정렬 후에도 동일한 아이템들 중에서 앞에 위치하도록 하는지 여부를 의미함
• Heap Sort와 Quick Sort는 Unstable이다. (중복된 아이템들 사이의 순서가 바뀜)

Searching

• Linear (or Sequential) Searching
  • 첫 아이템 부터 쭉 찾아나감
• High-Probability Ordering
  • 특정 아이템을 찾고자 할 확률이 높을때, 해당 아이템을 앞쪽에 배치시켜서 찾는 시간 단축
• Key Ordering
  • Sorting이 잘 되어있으면 찾기 쉬워진다 ⇒ 바이너리 서치 사용 가능해짐

Hashing

• 서칭의 복잡도를 O(1)로 만드는 방법
• Hash function (해시 함수)를 이용하여 넣고자 하는 아이템으로부터 인덱스 값을 만들거나 찾아낼 수 있게 함
  • 예를 들어, 해시함수 f는 다음과 같다. f(Item) = Item %100
    
• 문제점
  • COLLISON 발생 가능
    • 예를들어, 5502와 4702는 100으로 나눈 나머지가 2로 같기 때문에 같은 인덱스 번호인 2번에 들어가야 한다.
  • COLLISON 해결 방안

    1. Linear Probing

       1. 이미 아이템이 들어있는 인덱스 번호에 새 아이템을 넣어야 한다면 인덱스를 1씩늘려가며 비어있는 칸에 넣는다. (당연히 나중에 search할 때에도 당장 해당 인덱스에 찾고자 하는 아이템이 없다고 false를 리턴하는 것이 아니라 비어있는 칸이 나올때 까지 다음 인덱스 번호에 접근해서 확인해야 한다.)
       2. 이 방안에서는 아이템을 delete 하면 문제가 생간다. 아이템이 원하는 인덱스 번호에 들어가있지 못하고 밀려있는 상황에서 중간에 있는 아이템을 지우면 빈 공간이 생기면서 밑에 있는 아이템을 서치하게 되면 빈공간을 만나서 false(찾지 못함)를 리턴하게 된다. 이를 방지하기 위해서는 delete 후에는 밑에 있는 아이템을 알맞은 위치로 올려주어야 한다.

    2. Rehashing

       1. 알맞은 인덱스에는 이미 아이템이 들어가 있다면 다시 Hash function을 이용하여 해싱하여 새 인덱스 번호를 찾는다.

    3. Buckets

       

       • 그림처럼 한 인덱스 공간에 여러개의 아이템이 들어갈 수 있도록 구현한다.

    4. Chain

       

       • 그림처럼 한 인덱스 공간에 여러개의 아이템이 들어갈 수 있도록 링크드 형식으로 구현한다. (주로 많이 사용)