[자료구조 복습 8] 기초 정렬 알고리즘 정리 ( 선택, 삽입, 버블, 쉘)

 

1. 선택 소트 

void selection_sort(int list[], int n) {
	int least=0, i=0, j=0;
	for (i = 0; i < n-1; i++) {
		least = i;
		for (j = i + 1; j < n; j++) {
			if (list[j] < list[least]) least = j;
            //가장 작은 값 찾기
		}
		swap(list, i, least);
	}
}

1) 인덱스 0 부터 n-1까지 차례대로 해당 인덱스에 올 i번째로 작은 값을 찾는다.

2) 이를 위해 내부 루프는 i보다 1큰 인덱스부터 시작하여 맨 끝 인덱스까지 본다. 

 

선택 소트는 , 인접요소들 끼리 차례대로 정렬하는 것이 아니라, 앞의 인덱스에 있는 요소와 뒤의 랜덤의 요소 (가장 작은 값)을 정렬하는 것으로 , 안정적이지 않다. 

예시로 2  2  1 배열을 선택 소트로 정렬한다고 하면

두 개의 2의 위치가 바뀌게 된다. 

 

 

2. 삽입 소트

void insert_sort(int list[], int n) {
	int i=0, j=0, key=0;
	for (int i = 1; i < n; i++) {
		key = list[i]; //key값이 들어갈 자리 앞에서 찾기
		for (j = i - 1; j >= 0 && key < list[j]; j--)
			list[j + 1] = list[j]; //첫 list[j+1]는 key값이 저장된 자리
		list[j + 1] = key;
          //for문의 조건식 j < 0 이거나 key > list[j]일때,
           //식 2 j--이 이미 수행된 상태이므로, key의 자리는 list[j+1]이다.
	}
}

1) 인덱스 1부터 시작해서 마지막 인덱스까지 보는데, 해당 인덱스의 요소가 들어갈 자리를 앞의 자리에서 찾는다.

2)  따라서 j는 i-1로 시작하여 0이될때까지 진행되고, 이 때 만약 위의 요소보다 작은값이 존재하는 경우 이미 정렬이 되었다고 판단하여 (같은 과정을 반복했거나, 첫 루프일 것이므로) 루프를 끝내고, 그 값보다 1 큰 인덱스에 요소를 넣는다.

 

 

 

3. 삽입소트를 응용한 쉘 소트 

void shell_sort(int list[], int first, int last, int gap) {
	int i=0, j=0, key=0;
	for (i = first+gap; i <= last; i += gap) {
		key = list[i];
		for (j = i - gap; j >= first && key < list[j]; j -=gap)
			list[j + gap] = list[j];
		list[j + gap] = key;
	}
}


int main(void) {
	int list[10] = { 5,1,0,6,8,10,9,4,3,2 };
	int n = 10;
	for (int gap = n / 2; gap > 0; gap /= 2) {
		if ((gap % 2 == 0)) gap++;
		for (int i = 0; i < n-2; i++) {
			shell_sort(list, i, n - 1,gap);
		}
	}
 }

이는 삽입 소트를 이용했다 .삽입 소트가 차례대로 모든 요소를 검사하는 대신, 쉘 소트는 gap을 정해서 해당 gap 만큼 떨어진 요소들을 먼저 정렬하고 -> gap을 줄여서 또 gap 만큼 떨어진 요소들을 정렬 ... (gap이 0보다 클 때까지 정렬) 하는 방식이다. 이렇게 하면 gap이 최소 1이 될 때까지 정렬하게 되므로, 모든 최종적으로 모든 요소가 정렬된다. 

이는 삽입 소트의 특징 중 , "정렬 된 배열은 시간 복잡도가 O(n)" 을 이용한 소트이다.

일단 gap 차이가 나는 서브 배열을 먼저 정렬해놓음으로써 시간복잡도를 줄이는 것이다. (배열이 정렬 되어있는 경우 두번째 for문이 덜 돌기 실행되므로) 

 

4. 버블 소트

void bubble_sort(int list[], int n) {
	int i=0, j=0;
	for (int i = n - 1; i > 0; i--) {
		for (int j = 0; j < i; j++) { //맨 뒤부터 정렬, 가장 큰 값들을 맨 뒤에 옮겨놓는다.
			if (list[j] > list[j + 1])
				swap(list, j, j + 1);
		}
	}
}

 버블소트는 맨 뒤에서부터 정렬하는 소트라고 생각하자.

인덱스 0부터 계속해서 연속하는 두 값씩 비교하여 더 큰 값을 맨 뒤로 보낸다 -> 이것을 반복한다. 

 

 

 

위 정렬들의 시간복잡도는 모두 O(n^2) 이다.