삽입 정렬 알고리즘 삽입 정렬은 안정 정렬(중복된 값이 입력 순서 혹은 정렬 전 순서와 동일하게 정렬)에 속하며, 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬입니다. 알고리즘을 알아보기 전 대략적인 개념을 잡아보겠습니다. 퀵 정렬에서는 '이미 정렬된 배열' 이라는 개념을 사용하여 정렬을 수행합니다. 이미 정렬된 배열에 원소 하나를 삽입하는 것은 배열의 마지막 혹은 처음부터 순차적으로 탐색하여 알고리즘은 대략 다음과 같이 이루어집니다. 배열을 두 부분으로 나눕니다. 왼쪽 배열은 '정렬된 배열', 오른쪽 배열은 '정렬되지 않은 배열'입니다 최초 상태에서 정렬된 배열의 길이는 1입니다. '정렬되지 않은 배열'의 최좌측 원소를 선택하여 '정렬된 배열'에 삽입될 위치를 찾아 삽입합니다. 해당 과정에서 순..
Algorithm/정렬
퀵 정렬은 분할 정복 알고리즘(Divide and Conquer)의 하나이면서, 매우 중요하게 다뤄지는 정렬 방법입니다. 퀵 정렬 알고리즘 퀵 정렬은 불안정 정렬(중복된 값이 입력 순서 혹은 정렬 전 순서와 동일하게 정렬되지 않음)에 속하며, 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬입니다. 알고리즘은 대략 다음과 같이 이루어집니다. 리스트 안에 있는 하나의 요소를 선택합니다. 해당 요소는 Pivot 이라 부릅니다. (아무 원소나 선택해도 됩니다.) Pivot을 기준으로 Pivot보다 작은 원소는 모두 Pivot의 왼쪽으로, 큰 원소들은 모두 Pivot의 오른쪽으로 옮깁니다.(Divide) Pivot을 제외한 왼쪽과 오른쪽 부분의 리스트에 대해 다시 1,2 의 과정을 반복합니다. (Conquer..
