배열의 기초와 Quick sort

Array (배열)

• sorting : O(nlog_n)
  • stable : 정렬 후 기존의 순서 유지 O
    • merge
  • unstable : 정렬 후 기존의 순서 유지 X
    • quick, heap
• search : O(n)
• binary search : O(log_n)

Quick sort (unstable)

• pivot을 정한 후 나머지 element를 partitioning 한다.
  • Pivot보다 큰 값은 오른쪽 작은 값은 왼쪽에 위치시킨다.
  • 다음 단계에서도 마찬가지로 pivot을 정한 후 partitioning 한다.
• pivot을 정하는 방법
  1. 중간 값 설정
  2. 중간에서 아무 값을 설정 후 맨 끝으로 이동
  3. 맨 끝값으로 설정
• time complexity
  • Best : O(nlog_n)
  • Worst : O(n²)

---

References

• 인터뷰 배열 기초 - YouTube

---

🏋🏻 개인적으로 공부한 내용을 기록하고 있습니다.
잘못된 부분이 있다면 과감하게 지적해주세요!! 🏋