Sort Algorithm - 정렬

01. 설명

• 자료 탐색에 있어서 필수적
• 비교 연산, 이동 연산을 최소화해야함
• 단순/비효율 : 삽입, 선택, 거품
• 복잡/효율 : 퀵, 힙, 합병, 기수

02. 선택정렬

• 해당 순서에 원소를 넣을 위치(index)는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘
• 입력 배열에서 최소값을 발견한 다음, 이 최소값을 배열의 첫 번째 요소와 교환한다.

03. 삽입정렬

• 자료 배열 안에서 매 순서마다 해당 원소의 앞의 이미 정렬되어 있는 모든 요소를 차례대로 비교하여, 자신의 위치를 찾아서 삽입하는 알고리즘
• 두 번째는 첫 번째를, 세번째는 두번째와 첫번째를 비교한 후 삽입할 위치를 찾고, 찾았으면 그 위치에 삽입하기 위해 자료를 한 칸씩 뒤로 이동시킨다.

04. 버블정렬

• 서로 인접한 두 원소를 검사하여 크기가 순서대로 되어 있지 않으면 서로 교환하는 비교-교환 과정을 배열의 왼쪽 끝에서 시작해 오른쪽 끝까지 진행하며 정렬하는 알고리즘
• 1회전을 수행하고 나면 가장 큰(작은)자료가 맨 뒤로 이동하므로 2회전에서는 맨 끝에 있는 자료는 정렬에서 제외된다.

05. 합병정렬

• 하나의 리스트를 두 개의 균등한 크기로 분할하고, 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법으로 분할 정복 알고리즘 중 하나
• 합병 정렬에서 실제로 정렬이 이루어지는 시점은 2개의 리스트를 합병(Merge)하는 단계
• 재귀 형식으로 구현 가능하며, 재귀 함수에서 재귀 함수로 타고 타고 들어가다가 더 이상 들어갈 수 없는 순간이 되면 리턴이 된 후 병합(정렬) 함수가 실행되면서 반환하고 반환되면서 정렬이 이루어진다.

06. 퀵정렬

• 하나의 리스트를 피벗(pivot) 기준으로 두 개의 비균등한 크기로 분할하고, 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법으로 분할 정복 알고리즘 중 하나
• 재귀 형식으로 구현 가능하며, 피벗(pivot) 기준으로 보다 작은 값은 왼쪽 리스트에 몰고, 보다 큰 값은 오른쪽 리스트에 몰은 다음에 각 두 리스트에 퀵 정렬 함수가 재귀로 실행되는 방식이다.