내가 공부하기 위한 공간 - [알고리즘] 12 - 정렬(선택, 버블, 삽입, 쉘)

[선택정렬]

최솟값을 찾고, 그 값과 주어진 범위 내 가장 왼쪽 값과 교환

8 5 9 1 3

i=0, 1과 8 교환, 1 5 9 8 3

i=1, 5와 3 교환, 1 3 9 8 5

…

1 3 5 8 9

 

<유사코드>

selectionSort( 배열 a )
{
	for i = 0 to n-2
	{
		minIndex = i
		for k = i to n-1
			if a[minIndex] >= a[k] then minIndex = k
		exchange a[i] and a[minIndex]
	}
	return a
}

시간복잡도 O(n^2)

 

 

[버블정렬]

두개씩 비교하여 둘 중 작은 값을 왼쪽으로 이동

8 5 9 1 3

i=4, 8과 5교환, 5 8 9 1 3

> 교환안함, 5 8 9 1 3

> 9와 1 교환, 5 8 1 9 3

> 9와 3 교환, 5 8 1 3 9

i=3, 교환안함, 5 8 1 3 9

> 8과 1 교환, 5 1 8 3 9

> 8과 3 교환, 5 1 3 8 9

i=2 ...

…

1 3 5 8 9

 

<유사코드>

bubbleSort( 배열 a )
{
	for i = n-1 to 1
	{
		for k = 0 to i-1
			if a[k] <= a[k+1] then exchange a[k] and a[k+1]
	}
	return a
}

시간복잡도 O(n^2)

 

 

[삽입정렬]

첫 원소부터 왼쪽편의 적절한 위치에 삽입

8 | 5 9 1 3

i=1, 5를 왼쪽편에 적절히 삽입, 5 8 | 9 1 3

i=2, 9를 왼쪽편에 적절히 삽입, 5 8 9 | 1 3

…

1 3 5 8 9

 

<유사코드>

InsertionSort( 배열 A )
{
	for i = 1 to n-1 {
		CurrentElement = A[i] // 현재 정렬할 원소
        j ← i – 1 // 현재 정렬할 원소의 왼쪽 인덱스
		while (j >= 0) and (A[j] > CurrentElement)
		{
			A[j+1] = A[j] // A[j]를 오른쪽으로 한 칸 이동
			j ← j-1
		}
		A [j+1] ← CurrentElement
	}
	return A
}

시간복잡도 O(n^2)

 

 

[쉘정렬]

일정한 간격으로 떨어진 데이터들의 집합을 대상으로 삽입정렬

작은 숫자들은 앞으로, 큰 숫자들은 뒤로 이동하여 대강 정렬된 형태를 만들고 마지막에 전체 삽입정렬

미리 큰값과 작은값을 구별하여 연산 줄임

간격으로는 보통 히바드 간격(2^k-1, …, 7, 3, 1)을 사용

 

<유사코드>

ShellSort( 배열 A )
{
	for each gap h = [h0, h1, ..., hk=1] //h0>h1>,,,>hk=1
	{
		for i = h to n-1
		{
			CurrentElement = A[i];
			j = i;
			while (j>=h) and (A[j-h] > CurrentElement) {
				A[j] = A[j-h];
				j = j-h;
			}
			A[j] = CurrentElement;
	}
	return 배열 A
}

시간복잡도 O(n^1.25)