정렬

삽입정렬

✔ 이미 순서화된 파일에 새로운 하나의 레코드를 순서에 맞게 삽입시켜 정렬하는 방식

✔ 평균과 최악 모두 수행 시간 복잡도는 O(n²)이다.

✔ 삽입정렬은 비교한 값을 넣고 나머지를 한자리씩 뒤로 이동시킨다.

✔ 1회전: 2번째값 -> 1번째값 비교, 2회전 : 3번째값 -> 1,2번째값 비교, 3회전 : 4번째값 -> 1,2,3번째값 비교...

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

✔ 평균과 최악 모두 수행시간 복잡도는 O(n²)이다.

✔ 선택정렬은 비교한 값과 위치를 변경한다. (삽입정렬처럼 뒤로 미루지 않음)

✔ 1회전 : 1번째값 -> 2,3,4,5번째값 비교, 2회전 : 2번째값 -> 3,4,5번째값 비교

✔ 버블 정렬은 주어진 파일에서 인접한 두개의 레코드 키 값을 비교하여 그 크기에 따라 레코드의 위치를 서로 교환하는 정렬 방식이다.

✔ 평균과 최악 모두수행시간 복잡도는 O(n²)이다.

✔ 쉘 정렬은 입력 파일을 어떤 매개변수의 값으로 서브 파일을 구성하고, 각 서브파일을 Insertion 정렬 방식으로 순서 배열하는 과정을 반복하는 정렬 방식이다.

✔ 삽입정렬을 확장한 개념이다

✔ 평균 수행시간 복잡도는 O(n^1.5)이고, 최아그이 수행 시간 복잡도는 O(n²)이다.

✔ 퀵 정렬은 키를 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽 서브 파일에 분해 시키는 과정을 반복하는 정렬 방식이다.

✔ 평균 수행 시간 복잡도는 O(nlog₂n)이고, 최악의 수행 시간 복잡도는 O(n²)이다.

✔ 힙 정렬은 전이진 트리를 이용한 정렬 방식이다.

✔ 평균과 최악 모두 시간 복잡도는 O(nlog₂n)이다.

✔ 2-Way합병 정렬은 이미 정렬되어 있는 두 개의 파일을 한개의 파일로 합병하는 정렬 방식이다.

✔ 평균과 최악 모두 시간 복잡도는 O(nlog₂n)이다.

✔ 기수정렬은 큐를 이용하여 자릿수별로 정렬하는 방식이다.

✔ 레코드의 키 값을 분석하여 같은 수 또는 같은 문자끼리 그 순서에 맞는 버킷에 분배하였다가 버킷의 순서대로 레코드를 꺼내여 정렬한다.

✔ 평균과 최악 모두 시간 복잡도는 O(dn)이다.