[자료구조 및 알고리즘] CH9. Sorting and Searching

 

Sorting

---

Bubble sort

Bubble sort

Selection sort

Selection sort

Insertion sort

Insertion sort

Shell sort

Shell sort

Quick sort

Quick sort

Merge sort(분할->병합정렬)

Merge sort

Heap sort

각 sorting 알고리즘의 시간복잡도는?

• Bubble - O(n^2)
• Selection - O(n^2)
• Insertion - O(n^2)
• Shell sort
• Quick sort
  • worst : O(n^2)
  • best : O(nlogn)
  • avg : O(nlogn)
• Merge sort
• Heap sort

 

Searching

---

Linear search는 언제 쓰면 좋은가?

• item이 sorted 되어있지 않거나 unsortable할 때

Linear search의 단점?

• 찾는 아이템이 없거나 뒤쪽에 있는 경우 비효율적

Binary search는 언제 쓰면 좋은가?

• item이 sorted 되어있을 때 효율적

Tree와 Graph에서의 searching 방법은?

• Tree
  • Inorder
  • Preorder
  • Postorder
• Graph
  • DFS
  • BFS

각 searching 알고리즘의 시간복잡도는?

• Linear - O(n)
• Binary - O(logn)
• BST - O(logn)