[알고리즘] 정렬(Sort) - 선택 정렬(Selection Sort), 삽입 정렬(Insertion Sort), 버블 정렬(Bubble Sort), 퀵 정렬(Quick Sort), 셸 정렬(Shell Sort), 병합 정렬(Merge Sort), 기수 정렬(Radix Sort), 힙 정렬(Heap Sort)

● 정렬 (Sort)

- 순서 없이 배열된 자료를 오름차순 혹은 내림차순으로 재배열하는 것이다.

 

● 버블 정렬 (Bubble Sort)

- 인접한 두 개의 원소를 비교하여 자리를 교환하는 방식

 

● 선택 정렬 (Selection Sort)

- 전체 원소 중에서 기준 위치에 맞는 원소를 선택해 자리를 교환하는 방식

① 아직 정렬하지 않은 부분에서 가장 작은 키의 값을 선택한다.

② 선택된 가장 작은 키 값을 정렬하지 않은 부분의 첫 번째 요소와 교한한다.

 

● 삽입 정렬 (Insertion Sort)

- 정렬되어 있는 부분집합에 새로운 원소의 위치를 찾아서 삽입하는 방식

① 정렬되지 않은 부분의 맨 앞 원소를 선택한다.

② 선택한 원소를 정렬된 부분의 원소들과 비교하여 적절한 위치를 찾는다.

③ 찾은 위치부터 원소를 한 칸 뒤로 이동시키고, 삽입한다.

 

● 퀵 정렬 (Quick Sort)

- 기준 값을 중심으로 왼쪽 부분 집합과 오른쪽 부분집합으로 분할하여 정렬하는 방식

① 리스트 안에 있는 한 요소를 선택한다. 선택한 요소를 피벗이라 한다.

② 피벗을 기준으로 피벗보다 작은 요소는 왼쪽으로, 큰 요소는 오른쪽으로 이동

 

● 셸 정렬 (Shell Sort)

- 정렬되어있는 부분 집합에 정렬할 새로운 원소의 위치를 삽입하는 방식

① 일정한 간격으로 떨어져있는 자료들끼리 부분집합을 구성한다.

② 각 부분 집합에 있는 원소들에 대해 삽입 정렬을 수행하는 작업을 반복한다.

 

● 병합 정렬 (Merge Sort)

- 2개 혹은 n개의 부분집합으로 나누어 각각 정렬한 후 병합하는 작업을 반복하는 방식

① 2개 혹은 n개의 부분집합으로 분할한다.

② 분할한 각 부분집합에 대해서 정렬한다.

③ 정렬된 부분집합을 병합한다.

 

● 기수 정렬 (Radix Sort)

- 원소의 키 값을 나타내는 기수를 이용한 정렬 방식 (큐를 사용한다.)

① 정렬할 원소의 키 값에 해당하는 버킷에 원소를 분배한다.

② 그 후 버킷의 순서대로 원소를 꺼내는 방법을 반복하면서 정렬한다.

 

● 힙 정렬 (Heap Sort)

- 힙을 사용하여 정렬하는 방식

① 정렬되지 않은 데이터들을 힙으로 만든다.

- 주어진 원소를 완전 이진 트리로 만든다.

- 하위 레벨의 서브 트리들을 힙으로 만들고, 그 다음 레벨의 서브 트리들도 힙으로 만든다.

- 이 과정을 루트 레벨까지 반복한다.

② 힙의 삭제 연산으로 루트 노드를 차례대로 꺼내서 정렬한다.

# 삭제 연산 이후 힙의 성질에 만족하도록 재구성해줘야한다.

 

 

 

힙이란?

[자료구조] 힙(Heap)과 우선순위 큐(Priority Queue)