정렬과 탐색

🔑Table of Contents

1. 정렬 및 탐색 알고리즘
2. 정렬- 재귀적 접근1  
3. 정렬- 재귀적 접근2
4. 퀵 정렬
5. 퀵 정렬 분석
6. 퀵 정렬에 덧붙여..
7. 정리

---

📌 정렬 및 탐색 알고리즘

• 정렬
  • 삽입 정렬 → O(n²)
  • 선택 정렬  → O(n²)
  • 거품 정렬  → O(n²)
  • 퀵 정렬     → O(n²) O(n logn)
  • 합병 정렬  → O(n logn)
  • 힙 정렬      → O(n logn)
  • 이진 탐색 트리를 이용한 정렬  → O(n logn)
• 탐색
  • 이진 탐색 → O(logn)
  • 선형 탐색 → O(n)

📌 정렬- 재귀적 접근1

     [ 8 21 33 6 7 10 40 87 66 42 50 ]

 

   삽입 정렬

   6  7 8 10 21 33 40 42 66 87 

  • 앞에서 부터 수를 정렬에 맞게 삽입 / n개 n번탐색 O(n²)

 

   선택 정렬

   8 21 33 6 7 10 40 50 66 42 

  • n 번째로 작은 수가 뭔지 n번 탐색 (n²)

 

T(n) ≤ T(n - 1) + cn = O(n²)

1️⃣Max 정하고 Temp n번  ,2️⃣ Max 정하고 Temp n-1  ....  )) → n번          ∴n² 

 

 

📌 정렬- 재귀적 접근2

 

     [ 8 21 33 6 7  | 10 40 87 66 42 50 ]

 

     거의 반으로 나눠서 정렬

 6     7     8    21   33

10   16   40   42   50   87

 

6  7 8 10 ....

 

  T(n) ≤ 2 · T(ⁿ⁄₂) + cn = O(n log n)

 

 

 

📌퀵 정렬

    분할정복법으로  다음과 같이 리스트를 정렬한다 

1. 리스트에서 원소 하나를 고른다. 이것을 피벗(pivot)이라고 부른다  → 어떻게 선정하는지가 중요 
2. 피벗과 다른 n - 1개 원소 각각을 비교해 피벗보다 작은 것, 큰 것으로 분할한다
3. 분할된 두개의 작은 리스트를 재귀적으로 정렬한다 

     8 21 33 6 7 10  40 87 66 42 50 65           → 기준

                  정렬 ←    →   정렬

 

8	21	33	6	7	10	40	87	66	42	50	65
6	7	8	21	33	10	40	87	66	42	50	65
6	7	8	21	33	10	40	87	66	42	50	65
6	7	8	10	21	33	40	66	42	50	65	87
6	7	8	10	21	33	40	42	50	65	66	87
6	7	8	10	21	33	40	42	50	65	66	87
6	7	8	10	21	33	40	42	50	65	66	87

 

    피벗 선택 방법

     1. 리스트의 맨앞 원소를 선택한다                            → 상수시간

     2. 랜덤 선택  : 리스트에서 임의의 원소를 선택한다    → 상수시간  

     3. median-of-three : 리스트의 맨앞, 중간, 맨뒤에 있는 세 원소의 중앙값을 선택한다 → 피벗 원소 고르는데 시간은 많이 안씀 

 

    최선피벗

    중앙값이 피벗으로 선택되면 리스트가 둘로 균등하게 분할된다 

 

   최악의 피벗

    최솟값이나 최댓값이 피벗으로 선택되면 길이가 n-1과 0인 두 리스트로 분할된다 

    이미 정렬되어있는 리스트에서 맨앞의 원소

 

 

 

📌퀵 정렬 분석

 

     피벗 선택이 실행시간에 큰 영향을 미침 

     피벗 중앙값인 최선의 경우에 걸리는 시간

         T(n) ≤ 2 · T(n⁄2) + cn = O(n log n)           → 평균 시간 복잡도 O(n log n)

     피벗이 최악의 경우(최소 or 최대인경우) 시간 복잡도는 

         T(n) ≤ 2 · T(n-1) + cn = O(n²)

       재귀 호출을 위한 스택이 필요한데 스택의 크기는 최악의 경우 O(n) , 최선의 경우 O(n log n)

 

📌퀵 정렬에 덧붙여..

      퀵 정렬은 실제 구현에서 다른 정렬 알고리즘 보다 빠르다고 알려져있음

      O(n) 시가네 중앙값을 찾는 알고리즘에서 찾은 중앙값을 피벗으로 사용하면 퀵 정렬의 최악의 경우 시간 복잡도가 O(n log n) 

      중앙값 알고리즘은 O(n)시간이지만 n에 붙는 상수가 크기 때문에 거의 사용되지 않는다 

 

      QuickSelect( )

     n개의 원소로 이루어진 리스트에서 k번째 원소를 찾는 문제를 k-선택이라고 한다

     이 문제에 대해 QuickSort( )와 유사한 방식으로 알고리즘을 설계한것 

 

📌이진탐색

     정렬된 리스트에서 주어진 값의 위치를 찾는다 

      분할 정복법 

      T(n) ≤ T(n/2) + c = O(log n)