Sort(정렬)

정렬

주어진 데이터를 일정한 기준에 따라 순서대로 나열하는 것

 

버블 정렬(Bubble Sort)

• 비교 기반 정렬, 교환 방식
• 인접한 두 원소를 비교, 자리를 교환하는 방식
• 끝(가장 큰 값)에서부터 채워짐

 

선택 정렬(Selection Sort)

• 비교 기반 정렬, 교환 방식
• 전체 원소들 중에서 기준 원소를 선택, 교환하는 방식
• 앞(가장 작은 값)에서부터 채워짐

 

삽입 정렬(Insertion Sort)

• 비교 기반 정렬, 삽입 방식
• 정렬된 부분 집합에 정렬할 새 원소의 위치를 찾아 삽입
• 전체 원소를 정렬된 부분 집합과 정렬되지 않은 부분 집합으로 분할

 

병합 정렬(Merge Sort)

• 비교 기반 정렬, divide & conquer 방식
• 정렬 대상을 먼저 쪼갠 뒤 각각을 정렬
• 정렬된 부분 집합들을 하나로 결합

 

힙 정렬(Heap Sort)

• 비교 기반 정렬, 트리 방식
• 정렬 대상 원소들을 Heap Tree에 삽입
• Heap Tree의 root를 꺼내와 순서대로 나열

 

퀵 정렬(Quick Sort)

• 비교 기반 정렬, divide & conquer 방식
• 피벗을 중심으로 왼쪽, 오른쪽 부분 집합을 분할
• 왼쪽에는 피벗보다 작은 원소를, 오른쪽에는 피벗보다 큰 원소를 이동