정렬이란?
선형 자료구조(배열 등)의 원소들을 특정한 순서(오름차순 내림차순등)로 나열하는 것을 이야기 한다. 정렬 자체가 목적일 때도 있겠지만 대부분 검색등의 다른 알고리즘의 전처리 과정으로 사용되는 경우가 많다.
정렬알고리즘 종류
Permutaion Sort, Selection Sort , Bubble Sort , Quick Sort , Insertion Sort , Merge Sort 등 굉장히 많은 종류의 정렬알고리즘이 있다.
각 알고리즘의 방식과 구현방법, 시간복잡도를 알아보도록 하자.
이 글에서는 오름차순을 기준으로 설명하도록 하겠다.
Insertion Sort (삽입 정렬)
자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입하는 정렬 알고리즘이다.
배열의 압쪽은 정렬된 배열이고 뒤쪽은 정렬되지 않은 배열이 있고 정렬되지 않은 뒤쪽 배열의 원소를 순서대로 하나씩 들고와서 앞쪽 정렬된 배열의 알맞은 자리에 집어 넣어 준다고 생각하면 조금 더 이해하기 쉬울 것이다.
정렬되지 않은 배열에서 정렬된 배열로 삽입하는 원소를 key라고 한다. key 값과 정렬된 배열의 원소의 크기를 차례로 비교하며 key가 더 작다면 위치를 바꾼다. 모든 배열의 원소가 한번씩 key값이 되어야 하므로 배열의 길이 만큼 반복해야 한다.
687539를 이 방법을 사용해서 같이 한 번 정렬해 보도록 하자.
그림에서 노란색은 key값 붉은 색은 크기를 비교할 원소이며 초록색은 정렬된 부분이다.
배열의 첫 번째 원소는 key가 될 필요가 없다. (비교할 원소가 없으므로)
첫 번재 key는 8이다. 8과 그 앞의 값 6을 비교한다. 8이 더 크므로 자리를 바꿀 필요가 없다.
배열 앞 두 원소가 크기 순서대로 정렬되어 있다.
두 번째 key값은 7이다. 7과 앞의 원소 8과 비교한다. 7이 더 작으므로 자리를 바꾼다.
다음 값 6과 비교한다. 7이 더 크기 때문에 자리를 바꿀 필요가 없다.
배열 앞 세 원소가 오름차순으로 정렬되어 있다.
세 번째 key는 5이다. 5와 앞의 8을 비교한다. 5가 더 작으므로 자리를 바꾼다.
다음값 7과 비교한다. 역시 5가 더 작으므로 자리를 바꾼다.
그 다음값 3 보다는 5가 크기 때문에 자리를 바꿀 필요가 없다.
배열 앞 네 원소가 순서대로 정렬되어 있다.
네 번째 key는 3이다. 3과 앞의 8을 비교한다. 3이 더 작으므로 자리를 바꾼다.
다음값 7과 비교한다. 역시 3이 더 작으므로 자리를 바꾼다.
그 다음값 6 보다는 3이 작기 때문에 자리를 다시 바꿔 준다.
5보다도 3이 작기 때문에 다시 자리를 바꿔 준다.
이제 배열 앞 다섯개의 원소가 순서대로 정렬되어 있다.
마지막 key는 9이다. 9는 앞의 원소 8보다 크므로 자리를 바꿀 필요가 없다.
이로서 6개의 원소 모두 오름차순으로 정렬되었다.