2020/02/04 현재 kocw 를 통해 자료구조를 공부하고 있습니다.

정렬

정렬에 관하여 (설명은 오름차 기준으로 되어있습니다.)

  • Bubble Sort
    • 정렬 기준(오름차/내림차)을 바탕으로 기준에 맞지 않는 데이터를 위로 올립니다.
    • [1,3,2,4,7,6,9] : 1회전 => [1,2,3,4,7,6,9] // 기준에 맞지 않는 데이터 2를 Bubbling 하여 상위로 끌어 올림
  • Selection Sort
    • 정렬 기준(오름차/내림차)을 바탕으로 최소값, 최대값 기준으로 정렬 합니다.
    • [9,6,7,5,2,3,1] : 1회전 => [1,6,7,5,2,3,9] // 최소값인 1을 왼쪽으로 정렬 시도
  • Insertion Sort
    • 정렬 기준(오름차/내림차)을 바탕으로 차례 차례 하나씩 데이터를 삽입하면서 정렬합니다.
    • [9,6,7,5,2,3,1] : 1회전 => [6,9,7,5,2,3,1] // 6이 삽입되면서 9가 밀림.
    • [6,9,7,5,2,3,1] : 2회전 => [6,7,9,5,2,3,1] // 7이 삽입되면서 9가 밀림. (여기서 6도 검사)
  • Merge Sort
    • 정렬 기준(오름차/내림차)을 바탕으로 계속 반으로 자르면서 최소 단위로 쪼개 질 때까지 쪼갠 후(divide) 다시 합치면서(conquer) 데이터 비교하면서 정렬합니다.
    • [9,6,7,5,2,3,1] => [9,6,7,5] / [2,3,1] => [9,6] / [7,5] / [2,3] / [1] => [9] / [6] / [7] / [5] / [2] / [3] / [1] // 쪼갬(divide)
    • [9] / [6] / [7] / [5] / [2] / [3] / [1] => [6,9] / [5,7] / [2,3] / [1] => [5,6,7,9] / [1,2,3] => [1,2,3,5,6,7,9] // 합침(conquer)
  • Heap Sort (Heap: 자료구조 상 완전 이진 트리에 속하는 구조 & 우선 순위 큐는 특히 프로세스 순서 저장에 쓰임)
    • 정렬 기준(오름차/내림차)을 바탕으로 최소값 최대값을 기준으로하는 MIN/MAX Heap을 생성 후 max는 max값 순서대로 꺼내면서 보여주고 min은 min값 순서대로 꺼내면서 보여줍니다.
    • [9,6,7,5,2,3,1] => 트리구조로 저장되어있다고 가정 => 정렬 순서대로 보여줄 때 max 힙일 경우 => max 값 9를 꺼내고 delete => percolateDown(하위 노드에서 최대값을 루트로 올려주는 과정) 반복
  • Quick Sort
    • 정렬 기준(오름차/내림차)을 바탕으로 pivot을 하나 정해 pivot 보다 작은 값 pivot보다 큰 값으로 나눈 후(divide) 왼쪽 오른쪽 값이 생긴 것에 다시 pivot을 적용해 계속해서 작은 값 큰 값으로 변경 가장 작은 단위까지 나누면서 값을 왼쪽에는 작은 값 오른쪽에는 큰 값으로 정렬(conquer)합니다.
    • [9,6,7,5,2,3,1] => pivot 5 로 잡았다고 가정 => [2,3,1,5,9,6,7] 로 왼쪽에는 [2,3,1] 오른쪽에는 [9,6,7] 이 나누어짐.(divide)
    • 왼쪽[2,3,1] 오른쪽[9,6,7] => 각각 pivot 2, pivot 7을 잡음 => [1,2,3] [5] [6,7,9] => 왼쪽 오른쪽이 가장 작은 단위까지 나누어졌음. => 완료(conquer)

2020/02/24 업데이트 필요하지만 여기까지 정리하겠습니다.