8-7) 정렬 요약 표

 

 

• 선택 정렬: 인덱스 0부터 시작하여 차례대로 뒤의 숫자들과 하나하나 비교해 가장 작은 수가 나오면 교체하여 앞으로 오도록 하는 방법 (추가적인 코딩으로 안정 정렬 가능)
• 삽입 정렬: 요소를 하나씩 꺼내서 요소 앞에 있는 것들과 비교하며 알맞은 위치에 삽입하는 방법 (이미 정렬된 경우에 유용, O(n))
• 셀 정렬: 삽입 정렬을 약간 변형한 정렬. 일정한 너비만큼 떨어진 요소를 가져와서 그 둘을 대소비교한 후 바꾸는 방법 (일정 너비만큼 모두 바꾸면 1round) 간격의 크기를 점점 줄이며 정렬하다 간격 크기가 1이 되면 삽입 정렬. 간격의 크기가 셸 정렬의 평균 시간 복잡도에 영향을 줌
• 합병 정렬: 요소가 하나만 남을 때가지 리스트를 쪼개고, 다시 합치는 과정에서 대소를 비교하여 정렬하는 방법
• 퀵 정렬: 중심점 - 피벗(Pivot Point)을 임의로 고른 후 이중심점보다 작은 수를 한 쪽으로 분류하고 큰 수들은 다른 쪽으로 분류하여 정렬하는 방법 (계속해서 가장 큰 수나 가장 작은 수를 중심점으로 고를 경우 O(n^2) )
• 기수 정렬: 자릿수 기준에 따라 숫자를 분류하여 정렬. 데이터의 각 자릿수를 기준으로 하여 낮은 자리수에서부터 숫자별로 분류, 자리수를 올려가면서 정렬 (복사하는 과정으로 인해 비효율)
• 힙 정렬: 임의의 숫자들을 나열하고 힙 규칙(최대 힙 - 부모 노드가 자식 노드보다 큼 / 최소 힙 -자식 노드가 부모 노드보다 큼)에 맞게 TrickleDown을 반복해 정렬 (힙의 가장 위에 있는 숫자 계속 제거하여 마지막 요소를 가장 위에 둠)