[알고리즘] 정렬- 선택정렬, 삽입정렬, 버블정렬, 쉘정렬

선택 정렬

• 정렬하기 전 데이터에서 가장 작은 값을 추출해 자리를 교환하고 그 다음 값을 추출해 자리를 교환하는 방식으로 정렬

수행 방법

1. 전체 원소 중에서 가장 작은 원소를 찾아 첫번째 원소와 자리를 교환한다
2. 그 다음 두 번째로 작은 원소를 찾아 두 번째 원소와 자리를 교환한다
3. 반복..

 

왼쪽과 오른쪽에 두 개의 리스트가 있다고 가정해보자.

왼쪽 리스트에는 정렬한 값을 넣을 것이고 오른쪽 리스트는 정렬하기 전의 값이 있다.

가장 작은 원소를 찾아 왼쪽 리스트에 넣고 그 다음 작은 값을 찾아 왼쪽 리스트에 또 넣는다. 

오른쪽 리스트가 공백이 될 때까지 반복한다.

 

만약 위와 같은 방식으로 배열로 구현한다고 하면, 똑같은 크기의 배열이 2개나 필요하다.

메모리 공간 절약을 위해 하나의 배열을 사용하며 가장 작은 값을 첫 번째 인덱스에 있는 값과 교환하는 방식으로 정렬을 실행한다.

해당 과정을 배열의길이-1 만큼 실행하면 숫자들이 추가적인 배열을 사용하지 않고도 전체 숫자가 정렬된다.

 

{5, 2, 1, 0, 7, 9}

배열 a가 있다고 가정해보자. 가장 작은 값은 a[3]이다.

a[3]값을 임시 공간에 넣어놓게 되면 a[3]의 값은 변경되어도 문제가 없다.

{5, 5, 2, 1, 7, 9}

 자리를 한자리씩 밀게 되면 위처럼 배열이 만들어진다.

 

{0, 5, 2, 1, 7, 9}

그 후 임시 공간에 넣어놨던 0을 a[0]에 넣어준다.

 

위 과정을 반복하면 된다.

 

선택 정렬 코드

 

#define SWAP(x, y, t)  ((t)=(x), (x)=(y), (y)=(t)) 
void selection_sort(int list[], int n) {
	int i, j, least, temp; 
    // i는 정렬한 값을 삽입할 인덱스
    // j는 배열을 돌며 작은 값을 탐색할 인덱스
    //least는 탐색이 완료된 가장 작은 값의 인덱스
	for (i = 0; i < n - 1; i++) {
		least = i; // 초기의 가장 작은 값의 인덱스는 0이다.
		for (j = i + 1; j < n; j++) //최소값 탐색 
			if (list[j] < list[least]) least = j; 
           		 //만약 탐색한 인덱스 자리에 있는 값이 작으면 least를 j로 바꾼다.
            
		SWAP(list[i], list[least], temp);
	}
}

 

선택 정렬의 효율 분석

메모리 사용 공간: n개의 원소에 대하여 n개의 메모리 사용

비교 횟수: O(n^2)

교환 횟수: 한 번 교환하기 위해 3번의 이동이 필요하므로 3(n-1)

• 3(n-1)의 이동횟수는 굉장히 큰 편이다. 이를 줄이기 위해서 불필요한 이동은 지양하는 것이 좋다.
• if(i != least)
  SWAP(list[i], list[least], temp); 코드를 사용해 자기 자신과의 이동을 막을 수 있다.
• 비교 연산 1개가 이동 연산 3개보다 시간이 적게 걸리므로 더 효과적이다.

선택 정렬의 장점: 자료 이동 횟수가 미리 결정된다는 점.

선택 정렬의 단점: 안정성을 만족하지 않는다.

• 같은 데이터가 2개 이상이면 상대적인 위치가 변경될 수 있다.

 

삽입 정렬

정렬되어 있는 부분 집합에 정렬할 원소의 위치를 찾아 삽입하는 정렬

 

{2, 3, 7, 1, 4}

위와 같은 배열 a가 있다고 가정해보자. 인덱스 0부터 차례대로 정렬한다고 생각하면 된다.

 

첫 번째로 2를 정렬해보자. 비교할 대상이 없으니 정렬이 완료되었다.

두 번째로 3을 정렬해보자. 2와 비교했을 때 2보다 크니 옳은 자리에 들어가있다.

세 번째로 7을 정렬해보자. 역시 옳은 자리에 들어가있다.

네 번째로 1을 정렬해보자. 현재 정렬된 값은 {2, 3, 7}이다. 1은 이 중 가장 작은 값이므로 인덱스 0 위치에 들어간다.

마지막으로 4를 정렬해보자. 현재 정렬된 배열은 {1, 2, 3, 7}이다. 4는 4번째로 작은 값이므로 3 다음에 들어간다.

최종 정렬된 배열은 {1, 2, 3, 4, 7}이 된다.

 

삽입 정렬 코드

void insertion_sort(int list[], int n)
{
	int i, j, key;
	for (i = 1; i < n; i++) { //2개 이상부터 비교해야하니 인덱스 1부터 시작
		key = list[i]; //임시 공간에 자리를 찾아야할 데이터를 넣어둠.
		for (j = i - 1; j >= 0 && list[j] > key; j--) 
        // j는 1씩 감소시키며 뒤에서부터 탐색한다. key값이 list[j]보다 큰 값이 나올때까지
			list[j + 1] = list[j]; 
            // key값이 list[j]보다 작다면 원래 key값이 있던 자리로 한 칸 밀어준다
            // 임시 공간에 list[i]값을 넣어놨기 때문에 밀어서 해당 칸의 데이터 값이 사라져도 괜찮다.
		list[j + 1] = key; 
        // 만약 자리를 찾았다면 for문에 의해 인덱스 j가 1 감소했을것이니 j+1 자리에 넣어준다.
	}
}

 

삽입 정렬의 효율 분석

메모리 사용 공간: n개의 원소에 대하여 n개의 메모리 사용

 

최상의 경우 O(n)

- 비교: n-1번

- 이동: 2(n-1)

 

최악의 경우 O(n^2) 

- 비교: n^2

- 이동: n^2

 

평균의 경우 비교 횟수는 n(n-1)/4이다.

평균 시간 복잡도는 O(n^2)

 

버블 정렬

인접한 두 개의 원소를 비교하여 자리를 교환하는 방식

 

{3, 5, 24, 4, 6, 7}

위와 같은 배열이 있다면 인접한 두 원소를 비교하여 작은 값을 왼쪽에 두면 된다

1. 3과 5 비교. 3이 작으니 유지
2. 5와 24 비교. 5가 작으니 유지
3. 24와 4 비교. 4가 작으니 24와 교환 -> 교환 후 배열 {3, 5, 4, 24, 6, 7}
4. 24와 6 비교. 6이 작으니 24와 교환 -> 교환 후 배열 {3, 5, 4, 6, 24, 7}
5. 24와 7 비교. 7이 작으니 24와 교환 -> 교환 후 배열 {3, 5, 4, 6, 7, 24}
6. 이로써 가장 큰 값은 맨 마지막에 정렬됐다. 이제 24를 제외한 나머지 버블 정렬 반복
7. 3과 5 비교. 3이 작으니 유지
8. 5와 4 비교. 4가 작으니 5와 교환 -> 교환 후 배열 {3, 4, 5, 6, 7, 24}
9. 반복..

 

 

버블 정렬 코드

#define SWAP(x, y, t) ( (t)=(x), (x)=(y), (y)=(t) ) 
void bubble_sort(int list[], int n)
{
	int i, j, temp;
	for (i = n - 1; i > 0; i--) {
		for (j = 0; j < i; j++)
			if (list[j] > list[j + 1])
				SWAP(list[j], list[j + 1], temp);
	}
}

i는 정렬된 값의 배열 인덱스이다. 초기에는 아무것도 정렬되어 있지 않으니 n-1의 값을 가지게 된다.

for문을 한 번 돌 때마다 배열의 끝이 정렬되니 i를 감소시켜준다.

 

j는 탐색을 위한 배열 인덱스이다. 만약 list[j] > list[j+1]이면 두 값을 swap 해준다.

 

버블 정렬 효율 분석

메모리 사용 공간: n개의 원소에 대하여 n개의 메모리 사용

연산 시간

• 비교 횟수: 최상, 평균, 최악의 경우 항상 일정 n^2
• 이동 횟수
  • 최악: 역순 정렬 이동 -> 3*비교
  • 최상: 이미 모두 정렬 -> 0
  • 평균: O(n^2)

 

쉘 정렬

- 일정한 간격으로 떨어져있는 자료들끼리 부분집합을 구성하고, 각 부분집합에 있는 원소들에 대해 삽입 정렬을 수행하는 작업을 반복하며 전체 원소를 정렬한다.

 

쉘 정렬은 일정한 간격으로 부분 집합을 구성한다. 부분집합의 기준이 되는 간격을 매개변수 h에 저장하고, 한 단계가 수행될 때마다 간격 h를 반으로 줄인다. h가 1이 될 때까지 반복한다.

 

쉘 정렬은 삽입 정렬의 단점을 고안하여 탄생한 알고리즘이다.

삽입 정렬의 단점은 원소들이 삽입될 때, 인접한 위치로만 이동한다는 것이다. 만약 삽입될 위치가 멀리 떨어져 있다면 많은 이동이 필요하다. 이러한 단점을 보안하여 간격을 두어 삽입 정렬을 진행하는 것이 쉘 정렬이다.

해당 값을 가진 배열이 있다고 가정하자. 간격이 5일때 각각의 같은 색의 동그라미가 부분 집합을 갖는다. 동그라미가 없는 값은 간격을 유지하고 있는 값이 없어 부분집합으로 구성되지 못했다.

부분집합 끼리의 삽입정렬이 진행되면 간격은 반으로 줄어든다. 그 후 간격에 맞게 부분 집합을 다시 구성하고 정렬을 진행한다.

 

정렬 된 후 간격을 반으로 줄여 3이 되었다. 부분집합을 다시 구성하고 삽입 정렬을 수행한다.

 

이제 간격이 1이 되었다. 위 배열을 삽입 정렬을 해주면 쉘 정렬 방식이 완료된다.

 

쉘 정렬 코드

//간격을 포함한 삽입 정렬
void inc_insertion_sort(int list[], int first, int last, int gap)
{
	int i, j, key;
	for (i = first + gap; i <= last; i = i + gap) {
		key = list[i];
		for (j = i - gap; j >= first && key < list[j]; j = j - gap)
			list[j + gap] = list[j];
		list[j + gap] = key;
	}
}
// 쉘 정렬
void shell_sort(int list[], int n)  // n = 배열의 크기
{
	int i, gap;
	for (gap = n / 2; gap > 0; gap = gap / 2) {
		if ((gap % 2) == 0) gap++;
		for (i = 0; i < gap; i++)       // 부분 리스트의 개수는 gap
			inc_insertion_sort(list, i, n - 1, gap);
	}
}

 

쉘 정렬 효율 분석

-쉘 정렬은 간격을 가지고 삽입 정렬을 수행하기 때문에, 교환되는 값들이 삽입 정렬보다는 최종 위치에 더 가깝게 위치할 가능성이 크다. 

 

메모리 사용 공간: n개의 원소에 대하여 n개의 메모리와, 매개변수 h에 대한 메모리 사용

연산 시간

• 비교 횟수: 간격에 의해 결정
• 평균적인 시간 복잡도: O(n^1.5)