기본적인 정렬(선택정렬, 버블정렬, 삽입정렬)

기본적인 정렬(선택정렬, 버블정렬, 삽입정렬)

선택정렬

1. 가장 큰 값을 찾는다.
2. 맨 마지막 자리의 값과 자리를 바꾼다
   1. 가장 큰 값이 마지막에 위치한다.

selectionSort(A[], n) { -> 배열 A[1...n]을 정렬한다.

for last <- n downto 2 { ----- 1
    A[1...last] 중 가장 큰 수 A[k]를 찾는다; ---2
    A[k] <-> A[last]; -> A[k]와 A[last]의 값을 교환 ---3
}

1의 for 루프는 n-1 번 반복.
2에서 가장 큰 수를 찾기 위한 비교횟수 : n-1, n-2, ... , 2, 1 (last개 최대값 last-1)
3의 교환은 상수시간 작업
-> 시간 복잡도 T(n) = (n-1)+(n-2)+...+2+1 = O(n^2)

버블소트

1. 첫번쨰 값과 다음 인덱스의 값을 비교해 첫번째 값이 크면 스왑.
2. 두번째 값과 다음 인덱스의 값을 비교해 두번쨰 값이 크면 스왑.
   ... 가장 큰 값이 마지막에 위치
3. 가장 마지막에 위치한 값을 제외하고 1,2번 반복

bubbleSort(A[], n) { -> 배열 A[1...n]을 정렬한다.

for last <- n downto 2 { ----- 1
    for i <- 1 to last-1 ---2
        if(A[i]>A[i+1]) then A[i] <-> A[i+1];  -> 교환 --- 3
}

1의 for 루프는 n-1 번 반복.
2의 for 루프는 각각 n-1, n-2, ... , 2, 1번 반복
3의 교환은 상수시간 작업
-> 시간 복잡도 T(n) = (n-1)+(n-2)+...+2+1 = O(n^2)

삽입정렬

1. k-1 개의 데이터가 이미 정렬돼있다.
2. k번쨰 데이터를 1번 문제에 끼워넣어 정렬한다
   1. 결론적으로 k개의 데이터가 정렬된다
3. 반복

자세하게

1. {2,3,5,6,7,8,4,1} -> 4를 정렬할 차례.
2. 4를 temp 변수에 복사한다.
3. 4의 바로 앞 인덱스에 위치한 8과 비교한다.
4. 8 > 4 이니 8을 뒤로 shift한다. {2,3,5,6, ,8,1}
5. 다음으로는 6과 4를 비교한다
6. 6 > 4 이니 6을 뒤로 shift한다. {2,3,5, , 6,8,1}
7. 반복
   결과적으로 {2,3,4,5,6,8,1} 이 된다.

insertionSort(A[], n] { -> 배열 A[1...n]을 정렬한다.
    for i <- 2 to n ---- 1
        A[1...i]의 적당한 자리에 A[i]를 삽입한다. ---- 2
}

1의 for 루프는 n-1번 반복
2의 삽입은 i-1번 비교
-> 시간 복잡도 T(n) = (n-1)+(n-2)+...+2+1 = O(n^2) (최악의 경우)