선택정렬
: 가장 작은 항목을 선택하고, 제자리로 바꾸는 과정을 반복함.
선택 정렬 의사 코드
- 가장 작은 카드를 찾아서 첫 번째 카드와 바꾼다.
- 두번째로 작은 카드를 찾아서 두 번째 카드와 바꾼다.
- 세번째로 작은 카드를 찾아서 세 번째 카드와 바꾼다.
- 배열이 정렬될 때까지 위의 과정을 반복한다.
- [13,19,18,4,10] 에서 가장 작은 숫자는 4이므로 인덱스는 3이다. 이때, 인덱스 3에 있는 값과 인덱스 0과 바꿔서 [4,19,18,13,10]으로 만든다. 이때, 인덱스 1부터 시작하는 배열의 일부분에서 가장 작은 값을 찾아야하므로 이 것을 하위 배열의 선택이라고한다. 그 다음은 인덱스가 1인 숫자 19와 가장 작은 수 10을 바꿔서 [4,10,18,13,19]로 만든다.
- 만약 배열의 크기가 8이라면, 최소값을 찾는 반복문이 실행되는 회수는 8+7+6+5+4+3+2+1 =36이다.
+) 1부터 n까지 수의 합 계산하기
- 가장 작은 수와 가장 큰 수끼리 짝지어 서로 더하기
- 짝지은 수의 개수로 곱해주기 .
- 이와 같은 수열을 등차급수라고 한다. 수가 총 n개 만큼 있다면 2/n개의 쌍을 만들 수 있다. 따라서 1부터 n까지의 합은 (n+1)(n/2)로 나타낼 수 있다.
삽입정렬
: 1번 인덱스부터 시작하여 배열에 따라 순환하면 알맞은 자리를 찾는 방법.
삽입 정렬 의사 코드
- 인덱스 0의 정렬된 하위 배열에 인덱스 1부터 시작하는 요소를 삽입합니다.
- 인덱스 0에서 1까지 정렬된 하위 배열에 인덱스 2부터 시작하는 요소를 삽입합니다.
- 인덱스 0부터 2까지 정렬된 하위 배열에 인덱스 3부터 시작하는 요소를 삽입합니다.
…- 마지막으로 인덱스 0에서 n-2n−2n, minus, 2까지 정렬된 하위 배열에 인덱스 n-1n−1n, minus, 1부터 시작하는 요소를 삽입합니다.
병합정렬
...
버블정렬
...
