정렬 알고리즘은 정해진 기준에 따라 데이터를 순서대로, 체계적으로 정리하는 알고리즘이다.
정렬의 목적은 탐색에 있다. 즉, 원하는 데이터를 빠르고 쉽게 찾는 것이다.
정렬 알고리즘은 시간 복잡도, 공간 복잡도, 재귀(recursion), 안정성(stability), 비교(comparison) 여부, 직렬(serial)과 병렬(parallel), 순응성(adaptability), 온라인(online) 등의 속성에 따라 분류된다.
[6, 3, 5, 4, 2, 1]
[1 | 3, 5, 4, 2, 6]
->[1, 2 | 5, 4, 3, 6]
-> [1, 2, 3 | 4, 5, 6]
-> 여기서 정렬된 상태가 됐지만 끝까지 진행 -> ...
-> 정렬 완료.[6, 3, 5, 4, 2, 1]
, 왼쪽에서 오른쪽 방향으로 오름차순 정렬.[(3, 6), 5, 4, 2, 1]
-> [3, (5, 6), 4, 2, 1]
-> [3, 5, (4, 6), 2, 1]
-> [3, 5, 4, (2, 6), 1]
-> [3, 5, 4, 2, (1, 6)]
-> 첫번째 요소부터 다섯번째까지 비교 반복 -> ...
-> 첫번째 요소부터 네번째까지 비교 반복 -> ...
-> 첫번째 요소와 두번째 요소를 비교할 때까지 반복하거나 그 전에 정렬이 완료된 상태가 되면 종료.[i - 1]
)가 현재 요소 보다 크다면 현재 요소보다 큰 값이 더 이상 나오지 않는 위치까지 해당 범위의 요소를 한 칸씩 이동시키는 방식으로 구현한다. 이 내부 반복문이 끝나면 현재 요소의 제 위치를 찾은 것이므로 그 위치의 값을 앞서 저장해놨던 현재 요소 값으로 바꾼다.[6, 3, 5, 4, 2, 1]
[3, 6 | 5, 4, 2, 1]
-> [3, 5, 6 | 4, 2, 1]
-> ...
-> 정렬 완료[7, 5, 9, 8, 4, 5, 7, 5]
[1, 3, 0, 2, 1, 1]
[1, 4, 4, 6, 7, 8]
{170, 45, 75, 90, 2, 802, 2, 66}
, 최대값: 802
0:{170, 90}, 2:{2, 802, 2}, 5:{45, 75}, 6:{66}
0:{02, 802, 02}, 4:{45}, 6:{66}, 7:{170, 75}, 9:{90}
0:{002, 002, 045, 066, 075, 090}, 1:{170}, 8:{802}
[85, 68, 65, 100, 88, 61, 82, 95]