선택정렬&삽입정렬
1)선택정렬
선택정렬은 앞서 배운 버블보다 더 간단합니다.
원래 정렬대상을 선택해서 별도 메모리 공간에 차근차근 넣어야 해요.
하지만 최근에 메모리 공간을 별도로 사용하지 않구 있어요
그러기 위해서
- 가장 우선순위가 높은 즉 최소값을 탐색을 해서 그것을 가장 왼쪽으로 이동 시킵니다.
- 가장 왼쪽에 있던 데이터는 빈 자리에 갖다 놓습니다.
- 반복 합니다.
이렇듯 교환처럼 보이지만 빈 자리를 이용한 다는 것을 알아야합니다. 그래서 선택정렬 인겁니다.
단순 교환이 아니지요
그림으로 확인해보죠
이런 식으로 최소값 1이 빈자리를 만들고 맨앞으로 가고 3이 그 빈자리를 채웁니다.
1은 고정입니다.
그 다음 최소값을 탐색하여 고정 자리 제외한 가장 왼쪽으로 이동시킵니다.
반복합니다.
이 과정을 코드로 봐볼까요
/*
선택정렬
*/
void select_sort(int arr[], int n) {
int i, j;
int minidx; //최소 값 담을 인덱스
int temp;
//n번(크기)만큼 돌아감
for (i = 0; i < n - 1; i += 1) {
minidx = i; //가장 맨 왼쪽 부터 시작하고 점점 늘어남
//비교대상 다음 부터 가야하기 때문에 i+1부터 마지막까지 스캔
//즉 첫 원소를 기준으로 다음 꺼 비교해서 다음 것이 작으면 작은 인덱스에 minidx넣고 계속 비교해감. minidx에는 최소값의 인덱스가 담김.
for (j = i + 1; j < n; j+=1) {
//최소값 탐색
if (arr[j] < arr[minidx]) {
minidx = j;
}
}
temp = arr[i];
arr[i] = arr[minidx];
arr[minidx] = temp;
}
}첫 for문은 인자로 전달 받은 크기 n 만큼 돌려야합니다. 따라서 0~n-1까지 돌려야하고
minIdx=i는 우선 위에서 설명한 것 처럼 맨 왼쪽 인덱스를 우선적으로 선택합니다.
그다음 for문에서는 맨 왼쪽 인덱스를 제외한 그 다음 인덱스부터 차례대로 arr[j]<arr[minIdx] 하면서 최소값을 탐색합니다.
그 다음 그값과 맨 왼쪽 인덱스를 서로 교체합니다.
즉
1) i=0일 때 minIdx=0 j는 1부터 3까지( 맨 왼쪽 인덱스 제외)
2-1) arr[1]<arr[0] 비교 시작
3) 만약 참이다면 minIdx에 j값을 대입
4) 교환
2-2)만약 비교하여 거짓이라면 그냥 진행
2)삽입정렬
삽입정렬은 이미 정렬된 부분을 정렬되지 않은 부분과 비교를 하면서 삽입을 하여 정렬하는 알고리즘입니다.
중요한 점은 정렬된 부분 다음이 정렬을 해야할 대상이라는 겁니다.
즉 정렬부분에 삽입 위치를 찾고자 정렬 부분을 뒤로 한칸씩 미루면서 삽입 하는 방법을 설명할게요
1 2 4 7 은 정렬이 된 부분입니다. 5 3은 아직 미정렬 부분이구요.
정렬 되지 않은 부분에서 3의 자리를 찾고자 7과 비교 후 7을 뒤로 미룹니다.
또한 3과 그다음 4를 비교합니다. 3이 더 작기때문에 4를 뒤로 미룹니다.
3과 2를 비교했지만 여기서는 2가 더 작기때문에 3이 들어갈 위치를 찾은겁니다. 따라서 3을 그위치에 집어넣으면 끝입니다.
아래와 같이 진행이 됩니다. 즉 삽입정렬은 위치를 찾아 그자리에 삽입을 시키는 겁니다.
* _ << 이것은 빈자리
1 2 4 7 5 3 =>3을 뗌
1 2 4 _ 7 5
1 2 _ 4 7 5
1 2 3 4 7 5
이 과정을 코드로 보도록 하죠
void insertsort(int arr[],int n)
{
int i,j;
int insData; //정렬 대상을 담을 변수
for(i=1; i<n; i++)
{
insData=arr[i]; //맨 왼쪽 인덱스 제외 하고 그 다음 인덱스를 정렬대상으로
for(j=i-1; j>=0; j--) //뒤에서 앞으로 비교하면서 간다.
{
if(arr[j]>insData) //정렬 대상이 앞에 대상과 비교하여 만약 앞에 대상이 크다면
arr[j+1]=arr[j]; //한칸 뒤로 미룸.
else
break;
}
//데이터 삽입부분
arr[j+1]=insData; //j는 0일때 for문 나오면 j는 -1이다. 따라서 자리가 빈 앞자리에 데이터를 삽입한다.
}
}
첫 for문에서 i는 1부터 시작하는 이유는 맨 왼쪽 인덱스는 정렬된 부분이라 치고 다음 인덱스부터 비교를 해가며 삽입을 하기위해서입니다.
처음 i=1일때의 인덱스에 해당하는 값을 정렬대상 변수에 넣습니다. 그 다음 for문에서는 j가 작아지면서 비교를 할 텐데 뒤에서 앞으로 비교하면서 갑니다.
j=0일 겁니다. 정렬 대상 부분이 j에 해당하는 인덱스(앞 데이터) 랑 비교하여 더 크다면 j에 해당하는 인덱스를 뒤로 미룹니다. 뒤로 미루면 빈자리가 생기는데 그 빈자리에 insData를 삽입시키는 겁니다. 데이터 삽입 부분에서 arr[ j+1]은 j가 for문을 나오면서 j--을 통해 감소된 상태로 나오게 되기 때문입니다.
즉 j가 0이면 for문을 나오면서 j는 -1이 되기 때문입니다.
감사합니다.
