정렬(Sort)

clay·2023년 2월 3일

소프트웨어 개발

목록 보기

3/47

삽입 정렬은 가장 간단한 정렬 방식으로 이미 순서화된 파일에 새로운 하나의 레코드를 순서에 맞게 삽입시켜 정렬한다.

두 번째 키와 첫 번째 키를 비교해 순서대로 나열(1회전)하고, 이어서 세 번째 키를 첫 번째, 두 번째 키와 비교해 순서대로 나열(2회전)하고, 계속해서 n번째 키를 앞의 n-1개의 키와 비교해서 알맞은 순서에 삽입하여 정렬하는 방식이다.
평균과 최악 모두 수행 시간 복잡도는 O(n^2)이다.

쉘 정렬은 삽입 정렬을 확장한 개념이다.

입력 파일을 어떤 매개변수(h)의 값으로 서브파일을 구성하고, 각 서브파일을 Insertion 정렬 방식으로 순서 배열하는 과정을 반복하는 정렬 방식(보통 h = ∛n), 즉 임의의 레코드 키와 h값만큼 떨어진 곳의 레코드 키를 비교하여 순서화되어 있지 않으면 서로 교환하는 것을 반복하는 정렬 방식이다.
입력 파일이 부분적으로 정렬되어 있는 경우에 유리한 방식이다.
평균 수행 시간 복잡도는 O(n^1.5)이고, 최악의 수행 시간 복잡도는 O(n^2)이다.

선택 정렬은 n개의 레코드 중에서 최소값을 찾아 첫 번째 레코드 위치에 놓고, 나머지 (n-1)개 중에서 다시 최소값을 찾아 두 번째 레코드 위치에 놓는 방식을 반복하여 정렬하는 방식이다.

퀵 정렬은 레코드의 많은 자료 이동을 없애고 하나의 파일을 부분적으로 나누어 가면서 정렬하는 방법으로 키를 기준으로 작은 값은 왼쪽에, 큰 값은 오른쪽 서브파일로 분해시키는 방식으로 정렬한다.

위치에 관계없이 임의의 키를 분할 원소로 사용할 수 있다.
정렬 방식 중에서 가장 빠른 방식이다.
프로그램에서 되부름을 이용하기 때문에 스택(Stack)이 필요하다.
분할(Divide)과 정복(Conquer)을 통해 자료를 정렬한다.
분할(Divide): 기준값인 피봇(Pivot)을 중심으로 정렬할 자료들을 2개의 부분집합으로 나눈다.
정복(Conquer): 부분집합의 원소들 중 피봇(Pivot)보다 작은 원소들은 왼쪽, 피봇보다 큰 원소들을 오른쪽 부분집합으로 정렬한다.
부분 집합의 크기가 더 이상 나누어질 수 없을 때까지 분할과 정복을 반복 수행한다.
평균 수행 시간 복잡도는 O(nlog₂n)이고, 최악의 수행 시간 복잡도는 O(n^2)이다.

힙 정렬은 전이진 (Complete Bibary Tree)를 이용한 정렬 방식이다.

2-Way Merge Sort는 이미 정렬되어 있는 두 개의 파일을 한 개의 파일로 합병하는 정렬 방식이다. 그 방법은 다음과 같다

두 개의 키들을 한 쌍으로 하여 각 쌍에 대하여 순서를 정한다.
순서대로 정렬된 각 쌍의 키들을 합병하여 하나의 정렬된 서브리스트로 만든다.
위 과정에서 정렬된 서브리스트들을 하나의 정렬된 파일이 될 때까지 반복한다.
평균과 최악 모두 시간 복잡도는 O(nlog₂n)이다.

71, 2, 38, 5, 7, 61, 11, 26, 53, 42를 2-way 합병 정렬로 정렬하시오.
1회전: 두 개씩 묶은 후 각각의 묶음 안에서 정렬한다.
(71, 2) (38, 5) (7, 61) (11, 26) (53, 42)
⬇️
(2, 71) (5, 38) (7, 61) (11, 26) (42, 53)
2회전: 묶여진 묶음을 두 개씩 묶은 후 각각의 묶음 안에서 정렬한다.
((2, 71) (5, 38)) ((7, 61) (11, 26)) (42, 53)
⬇️
(2, 5, 38, 71) (7, 11, 26, 61) (42, 53)
3회전: 묶여진 묶음을 두 개씩 묶은 후 각각의 묶음 안에서 정렬한다.
((2, 5, 38, 71) (7, 11, 26, 61)) (42, 53)
⬇️
(2, 5, 7, 11, 26, 38, 61, 71) (42, 53)
4회전 묶여진 묶음을 두 개를 하나로 묶은 후 정렬한다.
(2, 5, 7, 11, 26, 38, 61, 71) (42, 53)
⬇️
2, 5, 7, 11, 26, 38, 42, 53, 61, 71