쉘 정렬 - 삽입 정렬을 이용하여 배열 뒷부분의 작은 숫자를 앞부분으로 빠르게(작은 숫자들이 마치 '점프하여' 앞으로 이동)이동시키고, 동시에 앞부분의 큰 숫자는 뒷부분으로 이동시키며, 가장 마지막에는 삽입 정렬을 수행 - 버블 정렬과 삽입 정렬의 단점을 보완 ex) 30 60 90 10 40 80 40 20 10 60 50 30 40 90 80 간격(gap)이 5인 그룹으로 나누어 정렬하면 정렬한 결과 80과 90 같은 큰 숫자는 뒷부분, 20과 30 같은 작은 숫자는 앞부분으로 이동한 것을 확인할 수 있음 >>다음에는 gap을 5보다 작게 하여, 정렬을 수행 단, 마지막에는 반드시 간격을 1로 놓고 수행해야 함(다른 그룹에 속하여 서로 비교되지 않은 숫자가 있을 수도 있기 때문에) => 모든 원소를 ..
삽입 정렬(Insertion Sort) -배열을 정렬된 부분(앞부분)과 정렬 안 된 부분(뒷부분)으로 나누고, 뒷부분의 가장 왼쪽 원소를 앞부분의 적절한 위치에 삽입하여 정렬되도록 하는 과정을 반복 -정렬된 부분의 원소 수가 1개 늘어나고, 동시에 정렬이 안 된 부분의 원소 수는 1개 줄어듦 -반복하면, 뒷부분에는 아무 원소도 남지 않고, 입력이 정렬됨 알고리즘 입력: 크기가 n인 배열 A 출력: 정렬된 배열 A for i=1 to n-1 CurrentElement = A[i] j =0) and (A[j] > CurrentElement) A[j+1]=A[j] A[j+1] 1+2+3+...+(n-2)+(n-1)=n(n-1)/2 루프 내부는 O(1) >> n(n-1)/2*O(1)=O(n^2) 2. 최선 경우..
선택 정렬(Selection Sort) - 입력 배열 전체에서 최솟값을 선택하여 배열의 0번 원소와 자리를 바꾸고, 다음엔 0번 원소를 제외한 나머지 원소에서 최솟값을 선택하여, 배열의 1번 원소와 자리를 바꿈 >> 마지막에 2개의 원소 중 작은 것을 선택하여 자리를 바꿈 알고리즘 입력: 크기가 n인 배열 A 출력: 정렬된 배열 A for i=0 to n-2 min = i for j=i+1 to n-1 if A[j] < A[min] min=j A[i] A[min] return A 시간 복잡도 외부 for루프는 (n-1)번 수행 -i=0일 때 내부 for루프는 (n-1)번 수행 -i=1일 때 내부 for루프는 (n-2)번 수행 ... -마지막으로 1번 수행 내부의 for루프가 수행되는 총 횟수 -(n-1)..
내부 정렬(Internal sort) -입력의 크기가 주기억 장치의 공간보다 크지 않은 경우에 수행되는 정렬 ex) 버블 정렬, 선택 정렬, 삽입 정렬, 합병 정렬, 퀵 정렬, 힙 정렬, 쉘 정렬, 기수 정렬, 이중 피봇 퀵정렬. Tim sort 외부 정렬(External sort) -입력의 크기가 주기억 장치의 공간보다 큰 경우에 보조 기억 장치에 있는 입력을 여러 번에 나누어 주기억 장치에 읽어 들인 후, 정렬하여 보조 기억 장치에 다시 저장하는 과정을 반복 버블 정렬 -이웃하는 숫자를 비교하여 작은 수를 앞쪽(오름차순)으로 이동시키는 과정을 반복하여 정렬 -배열을 상하로 그려보면 정렬하는 과정에서 작은 수가 마치 거품처럼 위로 올라가는 것을 연상케 함 패스: 입력을 전반적으로 1번 처리하는 것 1번..
