[TIL] Today I Learned - 221110

[TIL] Today I Learned - 221110

 

221110 기록

 

 자료구조

 

[Data Structure] 스택(stack), 큐(Queue) (tistory.com)

[Data Structure] 스택(stack), 큐(Queue)

 

알고리즘 - 정렬

 

알고리즘 중 정렬을 다루던 부분이었다. 자료구조를 정리하다보니 글로 세세하게 기입하지는 못하였다.

 

정렬 - 데이터를 원하는 순서대로 기준을 정해서 나열하는 방법을 의미

• bubble sort
  • 시간복잡도는 o(n^2)
  • 옆에 원소랑 대소 비교를 하면서 자리를 교환하는 방식
• selection sort
  • 시간복잡도는 o(n^2)
  • 앞에 있는 인덱스를 가장 작은 원소라고 임의로 지정
  • 내부에 있는 for 반복문을 사용하여 만약 지정한 원소보다 작은 경우가 존재한다면 해당 경우를 교체
• insertion sort
  • 시간복잡도는 o(n^2)
  • 이중 반복문으로 구현
    • 첫번째 반복문 i 은 정렬하고자 하는 배열의 두번째에서 끝을 조회
    • 두번째 반복문 j의 경우 i의 반복문 
    • 원소들을 앞에서부터 비교를 하며 이미 정렬된 부분과 비교를 한다.
    • 비교를 하면서 자신의 위치를 찾압 삽입한다.
• merge sort
  • 합병정렬
  • 주어진 배열을 쪼개어서 진행
  • 크기를 하나까지 쪼갠 후 합치면서 정렬을 한다.

정렬의 경우 예전에도 쪼개서 이해하자니 힘든 부분이었다. 이번에는 예전보다 편하게 듣긴했지만 아직 내것이라는 생각은 들지않는다. 정렬의 경우 추후에 계속 공부를 하며 따로 정리하고 글로 남겨둘 생각이다.